# «Discrete and Lexicographic Helly Theorems and their Relations to LP-Type Problems Thesis submitted for the degree of “Doctor of Philosophy” by ...»

The bound in the above lemma must be at least 11 as seen in Example B.2.11 Let B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} be the set of rectangles as described in Figure B.4.

One can verify that the solution on every proper subset of B is lexicographically smaller than on B. (The solution of the 3-lpiercing problem on subsets of 10 rectangles not containing one of {1, 2, 3, 4, 5, 6} is lsmaller than the one on B. The solution on the subset of the 10 rectangles not containing 10 is lsmaller since the middle point can move up to pierce 6 and then the upper point will be lsmaller than before. The solution on the subset of the 10 rectangles not containing 9 is lsmaller since the middle point can move left to become the lsmallest. The solution on the subset of the 10 rectangles not containing 8 is lsmaller since the lower point can move up to pierce 9 and then the middle point will be the lsmallest. The solution on the subset of the 10 rectangles not containing 11 is lsmaller since the lower point can move left to become the lsmallest. The solution on the subset of the 10 rectangles not containing 7 is lsmaller since the middle point can move up to pierce 11 and then the lower point will be the lsmallest.) B.3 Proving Case (iii) Proof: (of Theorem 2.3.4(iii), i.e., h∗ (2, 2) = 6) We ﬁrst show that h∗ (2, 2) ≤ 6. From Theorem 4.1.6 it is suﬃcient to construct for every subset B ⊆ B a solution deﬁning set of cardinality at most 6. Due to ** Theorem 2.3.**

4(i), Lemma B.2.3 and Lemma B.2.5 it remains to study the case where B is not 1-pierceable and no axis-parallel line traverses it. Let bT, bB, bL, bR ∈ B be as deﬁned in Deﬁnition B.2.1 (see Figure B.1). Consider the closed top halfplane H T bounded by the horizontal line, lT, containing the bottom edge of bT, the closed bottom halfplane H B bounded by the horizontal line, lB, containing the top edge of bB, the closed left halfplane H L bounded by the vertical line, lL, containing the right edge of bL and the closed right ∼ halfplane H R bounded by the vertical line, lR, containing the left edge of bR. Let H X denote the closure of the complement of H X, for X = L, R, T, B. As no axis-parallel line traverses B, H L is disjoint from H R, and ∼ H T is disjoint from H B, and thus B0 = ∩X∈{L,R,T,B} H X is a compact rectangle with nonempty interior.

We call B0 the location domain of B (see [SW96]). Let cT L, cBR, cT R and cBL be the upper left, lower right, upper right and lower left corners of B0. [SW96] note that if B is 2-pierceable, then there exists a solution where both piercing points are on the boundary of B0. For such a solution they observe that the 2 piercing points must be either cBL, cT R or cT L, cBR. Using this observation, we formulate in Deﬁnition B.2.1 two types of conﬁgurations for the possible solutions of 2-piercing and 2-lpiercing problems. In Figure B.1 the 4 dashed rectangles determine the location domain B0 whose corners are the big white balls. The bottom-left and top-right small black balls determine the optimal solution of type I. The top-left and bottom-right big

Figure B.4: An instance of the 3-piercing problem where a vertical line traverses all the rectangles.

black balls determine the optimal solution of type II, which is also the optimal solution for the 2-lpiercing problem on the 8 rectangles drawn. Due to the deﬁnitions in this paragraph we obtain Observation B.3.1 Let B be a 2-pierceable ﬁnite set of compact axis-parallel rectangles. If B is not 1pierceable and no axis-parallel line intersects all its rectangles, then every rectangle in B contains at least one of cT L, cBR, cT R and cBL (the corners of its location domain).

By using the observation above we get Observation B.3.2 Let B be as deﬁned in Observation B.3.1.

**Every rectangle b in B satisﬁes the following 4 properties:**

• If cBL does not pierce b then no point which lies not above and not to the right of cBL pierces b.

• If cT L does not pierce b then no point which lies not below and not to the right of cBL pierces b.

• If cBR does not pierce b then no point which lies not above and not to the left of cBL pierces b.

• If cT R does not pierce b then no point which lies not below and not to the left of cBL pierces b.

We are now ready to build a solution deﬁning set of the 2-lpiercing problem on B as follows. Suppose that there exists a solution for the type I 2-piercing problem on B (i.e., (cBL, cT R ) is a feasible 2-piercing vector of B). We move cBL left and down as much as possible while 2-piercing B as follows. Let b1 = bR (B \ P (cT R )) be a rectangle with the rightmost left edge amongst the rectangles in B which are not pierced by cT R. Let b2 = bT (B \ P (cT R )) be a rectangle with the highest bottom edge amongst the rectangles in B which are not pierced by cT R. From these deﬁnitions it follows that the left edge of b1 intersects the bottom edge of b2. Let cBL be the intersection point of these two edges, and let cT R = cT R. We note that (cBL, cT R ) is the ∗ ∗ ∗ ∗ optimal solution for the type I for the 2-lpiercing problem on B. We now show that

** D2I (B) = {bT, bR, b1, b2 }**

deﬁnes that optimal solution, i.e., D2I (B) is a solution deﬁning set for the type I 2-lpiercing problem on B.

Intuitively, the type I 2-lpiercing problem on B is decomposed into a 1-lpiercing problem on P (cT R ) (for which {bT, bR } is a solution deﬁning set) and a 1-lpiercing problem on B \ P (cT R ) (for which {b1, b2 } is a solution deﬁning set). The solution deﬁning set for the type I 2-lpiercing problem is simply the union of the deﬁning sets of the two 1-lpiercing problems. It remains to prove that D2I (B) is a solution deﬁning set for B, i.e., the solutions of the type I 2-lpiercing problems on B and on D2I (B) are identical. Due to monotonicity c2I (B) ≥L c2I (D2I (B)). The only possibility that c2I (B) L c2I (D2I (B)) is when at least one of b1, b2 is pierced by the point which pierces both bT, bR. Due to Observation B.3.2 neither b1 nor b2 can be pierced by a point which pierces {bT, bB }, since such a point must lie not below and not to the left of cT R. We note Claim B.3.3 Let B ⊆ B be such that D2I (B) ⊆ B and suppose there exists a solution for the type I 2-lpiercing problem on B. The solutions of the type I 2-lpiercing problems on B and on D2I (B) are equal.

We emphasis that {bT, bR, b1 } deﬁnes the ﬁrst coordinate (out of the 4 coordinates) of the optimal solution of the type I 2-lpiercing problem on B.

Claim B.3.4 Let B ⊆ B be such that {bT, bR, b1 } ⊆ B and suppose there exists a solution for the type I 2-lpiercing problem on B. The ﬁrst coordinate of the solution of the type I 2-lpiercing problem on B is equal to the one on D2I (B).

Claim B.3.5 Let B ⊆ B be such that D2II (B) ⊆ B and suppose there exists a solution of the type II 2-lpiercing problem on B. The solution of this problem on B is equal to the one on D2II (B).

We emphasis that {bT, bR, bB, b3 } deﬁnes the ﬁrst coordinate (out of the 4 coordinates) of the solution of the type II 2-lpiercing problem on B.

Claim B.3.6 Let B ⊆ B be such that {bT, bR, bB, b3 } ⊆ B and suppose there exists a solution of the type II 2-lpiercing problem on B. The ﬁrst coordinate of the type II 2-lpiercing problem on B is equal to the one on D2II (B).

If there doesn’t exist a solution for the type I (type II) 2-piercing problem on B, there exists bI ∈ B (bII ∈ B) that is not pierceable by either cBL or cT R (either cT L or cBR ), respectively.

To summarize, we now formulate D2 (B), the solution deﬁning set for the 2-lpiercing problem on B, according to the cases below.

Case 1 If B is not 2-pierceable then we let D2 (B) = {bT, bB, bL, bR, bI, bII }. Clearly D2 (B) is not 2-pierceable.

Due to monotonicity any B ⊇ D2 (B) is not 2-pierceable, so D2 (B) is a solution deﬁning set.

Case 2 If B is 2-pierceable but is not type II 2-pierceable (so it is type I 2-pierceable), then we let D2 (B) = D2I (B) ∪ {bII }. Due to Claim B.3.3 the solutions of the type I 2-lpiercing problems on B and on D2 (B) are equal. D2 (B) is not type II 2-pierceable since due to Observation B.3.2, bII cannot be pierced by any point which either lies not below and not to the right of cT L, or lies not above and not to the left of cBR.

Case 3 If B is 2-pierceable but is not type I 2-pierceable (so it is type II 2-pierceable), then we let D2 (B) = D2II (B) ∪ {bI }. Due to Claim B.3.5 the solutions of the type II 2-lpiercing problems on B and on D2 (B) are equal. D2 (B) is not type I 2-pierceable since due to Observation B.3.2, bI cannot be pierced by any point which either lies not below and not to the left of cT R, or lies not above and not to the right of cBL.

Case 4 If B is type I 2-pierceable as well as type II 2-pierceable, we compare their values. If c2I (B) L c2II (B) then we let D2 (B) = {bT, bR, bB, b1, b2, b3 }. By Claim B.3.3 the solutions of the type I 2-lpiercing problems on B and on D2 (B) are equal. By Claim B.3.6 the solution of type II 2-lpiercing problem on D2 (B) is inferior to the one of the type I 2-lpiercing problem on the same set. If c2I (B) L c2II (B) then we let D2 (B) = {bT, bR, bB, b1, b3, b4 }. By Claim B.3.5 the solutions of the type II 2-lpiercing problems on B and on D2 (B) are equal. By Claim B.3.4 the solution of the type I 2-lpiercing problem on D2 (B) is inferior to the one of the of the type II 2-lpiercing problem on the same set.

In all cases above the cardinality of D2 (B) is not more than 6 so h∗ (2, 2) ≤ 6. This bound is tight due to Example B.2.2 above.

By Lemma B.2.3 (and the remark below it), Lemma B.2.5 (and the remark below it) and the proof above we conclude with Corollary B.3.7 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is 2-pierceable then there exists a solution deﬁning set for the 2-lpiercing problem on B, D2 (B), such that |D2 (B)| ≤ 6 and bT, bR, bB ∈ D2 (B).

Corollary B.3.8 Let B be a set of rectangles with edges parallel to the coordinate axes such that B is not 2-pierceable. There exists D2 (B), a solution deﬁning set for the 2-lpiercing problem on B such that |D2 (B)| ≤ 6 and bT, bR, bB, bL ∈ D2 (B).

Corollary B.3.9 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is type I 2-pierceable, then there exists a solution deﬁning set for the type I 2-lpiercing problem on B, D2I (B), with |D2I (B)| ≤ 4 and bT, bR ∈ D2I (B).

Corollary B.3.10 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is not type I 2-pierceable, then there exists a solution deﬁning set for the type I 2-lpiercing problem on B, D2I (B), with |D2I (B)| ≤ 5 and bT, bR, bB, bL ∈ D2I (B).

Corollary B.3.11 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is type II 2-pierceable, then there exists a solution deﬁning set for the type II 2-lpiercing problem on B, D2II (B), with |D2II (B)| ≤ 5 and bT, bR, bB ∈ D2II (B).

Corollary B.3.12 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is not type II 2-pierceable, then there exists a solution deﬁning set for the type II 2-lpiercing problem on B, D2II (B), with |D2II (B)| ≤ 5 and bT, bR, bB, bL ∈ D2II (B).

The solution of the 2-lpiercing problem on B as described in Example 2.3.6 (|B| = 6) is lgreater than on any proper subset of B, so h∗ (2, 2) ≥ 6. In Example 2.3.6 B is a set which is traversed by a vertical line. Example B.2.2 illustrates that also when B is not traversed by any axis-parallel, any subset of up to 5-members of B has a lsmaller solution than on B.

B.4 Proving Case (iv) Proof: (of Theorem 2.3.4(iv), i.e., 16 ≤ h∗ (2, 3) ≤ 34) Due to Observation 2.3.12 h∗ (2, 3) ≥ 16. It remains to prove the upper bound. From Theorem 4.1.6 it is suﬃcient to construct for every set B of axisparallel rectangles a solution deﬁning set of cardinality at most 34. Due to Theorem 2.3.4(ii), Lemma B.2.3, Lemma B.2.8 and Theorem 2.1.2 it remains to study the case where B is 3-pierceable but is not 2-pierceable and no axis-parallel line traverses it. Let bT, bB, bL, bR ∈ B be as deﬁned in Deﬁnition B.2.1. Let B0 be the location domain as deﬁned in the proof above. Let cT L, cBR, cT R and cBL be the top left, bottom right, top right and bottom left corners of B0, respectively. Let

such that |B ∗ | ≤ 2 and B∗ ∪ B ∗ is not 2-pierceable (|B∗ ∪ B ∗ | ≤ 6|).

Let (c1, c2, c3 ) ∈ I 6 be a feasible 3-piercing vector for a subset B ⊆ B. We classify the feasible solutions R for the 3-piercing and 3-lpiercing problems on B into 4 types deﬁned as follows (i.e., (c1, c2, c3 ) must be of one of these 4 types).

Type TR: One point (e.g., cT R ) pierces both bT (B ) and bR (B ). The other two points pierce bB (B ) and bL (B ) (either each point pierces exactly one of these rectangles, or one point pierces both and the other point pierces rectangles diﬀerent from bT (B ), bR (B ), bB (B ), bL (B )).

Type BR: One point (e.g., cBR ) pierces both bB (B ) and bR (B ). The other two points pierce bT (B ) and bL (B ) (either each point pierces exactly one of these rectangles, or one point pierces both and the other point pierces rectangles diﬀerent from bT (B ), bR (B ), bB (B ), bL (B )).

Type T L: One point (e.g., cT L ) pierces both bT (B ) and bL (B ). Each one of the other two points pierces exactly one of bB (B ) and bR (B ).

Type BL: One point (e.g., cBL ) pierces both bB (B ) and bL (B ). Each one of the other two points pierces exactly one of bT (B ) and bR (B ).

A ﬁnite set of compact rectangles is 3-pierceable if it is type XX 3-pierceable for XX having value either T R, BR, T L or BL. From now on in this paragraph, we write XX instead of any of T R, BR, T L and BL.

We let c3XX (B ) denote the lexicographically smallest solution of the type XX 3-piercing problem on B, if one exists, and ∞ otherwise. We say that c3XX (B ) is the optimal solution of the type XX 3-lpiercing problem on B. We note that c3 (B ) = lex min{c3T R (B ), c3BR (B ), c3T L (B ), c3BL (B )}. Let D3XX (B ) be a solution deﬁning set for the type XX 3-piercing problem on B (solution of type XX deﬁning set, in short).