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

We say that c2I (B ) (c2II (B )) is the optimal solution of the type I (type II) 2-lpiercing problem on B, respectively. We note that c2 (B ) = lex min{c2I (B ), c2II (B )}. Let D2I (B ) (D2II (B )) be a solution deﬁning set for the type I (type II) 2-piercing problem on B (solution of type I (type II) deﬁning set, in short), respectively. In this way c2I (D2I (B )) = c2I (B ) and c2II (D2II (B )) = c2II (B )). We note that even though the solution of type I (type II) 2-lpiercing problem is unique, its solution deﬁning set is not necessarily unique, respectively.

To illustrate these deﬁnitions let us look at the following Example B.2.2 Let B = {bT, bB, bR, bL, b1, b2, b3, b4 } be a set of 8 axis-parallel rectangles as drawn in Figure B.1. We ﬁrst note that the “names” of bT, bT, bR and bL are consistent with our deﬁnitions in the sense that bT = bT (B), bB = bB (B), bR (B) = bR and bL (B) = bL. The solution for the type I 2-lpiercing problem on B is the two small black points. A solution of type I deﬁning set for B is D2I (B) = {bT, bR, b1, b2 }.

This solution deﬁning set is the unique inclusion-minimal type I solution deﬁning set for B. The only valid decomposition of D2I (B) is {bT, bR } and {b1, b2 }. The solution for the type II 2-lpiercing problem on B is the two big black points. We observe that the solution of the 2-lpiercing problem on B is realized by this solution. The inclusion-minimal solution of type II deﬁning set for B is D2II (B) = {bT, bR, bB, b3, b4 }.

{bT, b3 } deﬁnes the top left big black point and {bR, b4 } deﬁnes the bottom right big black point. We note that the type II solution on any proper subset of D2II (B) is lsmaller than on B. If the subset does not contain either bT or b3, its top left piercing point is lsmaller. If the subset does not contain either bR or b4 its bottom right piercing point is lsmaller. Finally, the 4-member subset of D2II (B) which does not contain bB yields an lsmaller type II solution since its top left piercing point is the bottom left corner of bT and the remaining 3 rectangles are pierced by a point which lies on the left edge of bR and the bottom edge of b3.

The inclusion-minimal deﬁning set of B is D2 (B) = {bT, bR, bB, b1, b3, b4 }. Any of its proper subsets which does not contain D2II (B), has an lsmaller solution. Its only proper subset that contains D2II (B) is D2II (B) itself and has an lsmaller solution (of type I, where the bottom left point is the bottom left corner of bB ). In this way we conclude that h∗ (2, 2) ≥ 6 (see Theorem 2.3.4).

We ﬁrst prove several lemmas which will serve us in proving cases (iii) and (iv) of Theorem 2.3.4.

Proof: The lemma is correct for p = 1 due to Theorem 2.3.4(i). We now prove the lemma for p 1.

We note that if B ⊆ B is A-p-pierceable, the intervals resulted by intersecting B with the line y = l are p-pierceable. Using the above for every 2p-membered subfamily of B we get by Theorem 2.1.2(ii) that the intervals resulted by intersecting B with the line y = l are p-pierceable, and consequently B is p-pierceable.

By Observation B.0.2 it remains to prove the case where B is not (p − 1)-pierceable. By Theorem 4.1.6 it is suﬃcient to show that for every B ⊆ B there exists a solution deﬁning set of cardinality at most 2p. We give an inductive proof. We ﬁrst deﬁne several special rectangles needed for the formulation of the induction hypothesis. We intersect B with the line y = l and get a family I of intervals which is not (p − 1)pierceable and all of its 2p-membered subfamilies are p-pierceable. By Theorem 2.1.2(ii) I is p-pierceable.

Let (x1,..., xp ) be the solution of the p-lpiercing problem on I. By the proof of Theorem 2.3.4(ii) there exists a subset of p pairwise disjoint intervals of I, Dp (I) = {i1,..., ip }, which is a solution deﬁning set for the p-lpiercing problem on I and where for all j = 1,..., p the leftmost point in ij is xj. For each j = 1,..., p we let Bj ⊂ B be the set of rectangles whose intersection with the line y = l is an interval with a left endpoint equal to the left endpoint of ij. Let bj ∈ Bj be the lexicographically (leftmost right, highest bottom, lowest X top)-most rectangle amongst the rectangles in Bj. Thus the chosen bj is unique. Let Bp = {bj | j = 1,..., p} X (we note that the rectangles in Bp are pairwise disjoint).

To complete the proof of this lemma, we will prove by induction that if B is p-pierceable and is not (p − 1)-pierceable, then there exists a solution deﬁning set, Dp (B), for the p-lpiercing problem on B, of X cardinality at most 2p, which contains Bp.

b2

Figure B.1: An instance of the 2-piercing problem where no axis parallel line traverses all the rectangles.

The induction basis (p = 1) is valid due to Theorem 2.3.4(i) and an appropriate selection of the deﬁning set.

We assume the correctness of the induction hypothesis for p − 1 and prove it for p. We let lR be the vertical line x = x2 and note

Let B L be the set of rectangles of B which are strictly to the left of lR. All b ∈ B L are pierced by (x1, l) and b1 is a rectangle with the rightmost left edge in B L. Let b1 = bT (B L ) be a rectangle with the highest bottom edge among the rectangles in B L (see Figure B.2). Let c1 (B L ) be the solution of the 1-lpiercing problem on B L. We note that D1 (B L ) = {b1, b1 } is a solution deﬁning set for the 1-lpiercing problem on B L so

Remark: We note that bT ∈ Dp (B) (it is also possible to change the above proof by replacing bp with bR so bR ∈ Dp (B)). We note as well that it is easy to choose B such that the solution of the p-lpiercing problem on Dp (B) as deﬁned in the above proof, is lgreater than any solution on any of its proper subsets, so the bound 2p in Lemma B.2.3 is tight.

Since in the lexicographic order the x-coordinate is more important than the y-coordinate, the case where a vertical line intersects all the rectangles is not analogue to the case where a horizonal line intersects all the rectangles.

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

Since bB ∈ D2 (B 2 ), by applying Claim B.2.6 on D2 (B 2 ) we get that the upper piercing point in the solution of the 2-lpiercing on D2 (B 2 ) pierces D1 (B T ) and the lower piercing point pierces D1 (B B ). By (B.9) the upper piercing point in the solution of the 2-lpiercing on B 2 pierces B T and the lower piercing point pierces B B. From monotonicity c2 (D2 (B 2 )) ≤L c2 (B 2 ). If c2 (D2 (B 2 )) L c2 (B 2 ) we get that either c1 (D1 (B T )) L c1 (B T ) or c1 (D1 (B B )) L c1 (B B ), in contradiction to (B.7) and (B.8). Hence

be the set of all the rectangles in B which are pierced by the lexicographically smaller piercing point in the solution of the 2-lpiercing problem on B 2. We note that if c1 (B T ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B T ) is a solution deﬁning set for the 1-lpiercing problem on B∗. We also note that if c1 (B B ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B B ) is a solution deﬁning set for the 1-lpiercing problem on B∗. Hence

B ∗ is 1-pierceable by a point on the line x = l. Let c∗ be the intersection point of the line x = l with the line among {lT, lB } which does not pass through c1 (B 2 ). Since the line x = l intersects all the rectangles in B we get that c∗ intersects all the rectangles in B ∗. Let D1 (B ∗ ) = {bT (B ∗ ), bR (B ∗ )} be a solution deﬁning set for the 1-lpiercing problem on B ∗, so

We note that (c1 (B 2 ), c∗ ) is a feasible solution for the 2-piercing problem on B so (c1 (B), c2 (B)) = c2 (B) ≤L (c1 (B 2 ), c∗ ). B ⊇ B 2, so by monotonicity c2 (B) ≥L c2 (B 2 ) = (c1 (B 2 ), c2 (B 2 )). Hence

By Claim B.2.6, in the solution of the 2-piercing problem on B L, {bT, bR (B T )} must be pierced by the upper piercing point and {bB, bR (B B )} must be pierced by the lower piercing point. Hence, by (B.14) we get Claim B.2.7 Let B ⊆ B be such that B L ⊆ B. The solution of the 2-lpiercing problem on B is of type I if and only if the solution of the 2-lpiercing problem on B L is of type I.

We say that B L deﬁnes the type of the solution of the 2-lpiercing problem on B and that the solutions of the 2-lpiercing problem on B L and on B are of the same type. (We note that if c2 (B) is a solution of type I, then bT, bR ∈ B ∗ so c1 (B) is the lower piercing point. If c2 (B) is a solution of type II, then bT ∈ B∗ and bR ∈ B ∗ so c1 (B) is the upper piercing point).

We now show that D2 (B) = B L ∪ D1 (B∗ ) ∪ D1 (B ∗ ) is a solution deﬁning set for the 2-lpiercing problem on B of cardinality at most 6. We ﬁrst prove that c2 (D2 (B)) = c2 (B).

We recall that either D1 (B∗ ) = D1 (B T ) or D1 (B∗ ) = D1 (B B ) so the rectangles in D1 (B∗ ) are either both not below lT or both not above lB. By applying Claim B.2.6 on D2 (B), the rectangles in D1 (B∗ ) are covered by the same piercing point. By Claim B.2.7 the solutions of the 2-lpiercing problem on B and on D2 (B) are of the same type. Hence c1 (D2 (B)) pierces D1 (B∗ ) (and possibly more rectangles from D2 (B)). By monotonicity c1 (D2 (B)) ≥L c1 (D1 (B∗ )) so from (B.16) we get c1 (D2 (B)) = c1 (D1 (B∗ )). By the former equation and the deﬁnition of B ∗, the rectangles in D1 (B ∗ ) are not pierced by c1 (D2 (B)). Hence c2 (D2 (B)) ≥L c1 (D1 (B ∗ )), so from (B.16) we get c2 (D2 (B)) = c1 (D1 (B∗ )). Thus By (B.12), (B.13) and (B.15) we get that c2 (D2 (B)) = c2 (B).

It remains to prove that |D2 (B)| ≤ 6. We ﬁrst note that bT ∈ B L ∩ (D1 (B∗ ) ∪ D1 (B ∗ )) so |D2 (B)| ≤ (4+2+2)−1 = 7. In order to give a smaller bound we need to look at two diﬀerent cases. If c1 (B T ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B T ) ⊂ B L, so |D2 (B)| ≤ 6. Otherwise (c1 (B B ) = c1 (B 2 )) D1 (B∗ ) = D1 (B B ) so bR (B B ) ∈ D1 (B∗ ) ∩ B L and thus |D2 (B)| ≤ 6.

Remark: We note that bT, bB, bR ∈ D2 (B). We note as well that

(if {bT, bR } is not 1-pierceable then we deﬁne P (c1 ({bT, bR })) = B) is a solution deﬁning set for the type I 2-lpiercing problem on B. Hence bT, bR ∈ D2I (B) and |D2I (B)| ≤ 4. We also note that

is a solution deﬁning set for the type II 2-lpiercing problem on B. Hence bT, bR, bB ∈ D2II (B) and |D2II (B)| ≤ 5 (we will use the representations of D2I (B), D2II (B) in the proof of Theorem 2.3.4 (iv)).

In Figure B.3 we have B = {1, 2, 3, 4, 5, 6}, B T = {3, 4}, B B = {5, 6} and B T B = {1, 2}. bT = 3, b (B B ) = 5, bB = 5, bR = 2, bR (B T ) = 4 and bR (B B ) = 6. The solution of the 2-lpiercing problem on B is T the two small black points. Thus B∗ = {3, 4}, B ∗ = {1, 2, 5, 6} and c∗ is the big white point. Example 2.3.6 demonstrates that the bound 6 in the above lemma is tight.

Lemma B.2.8 Let B be a ﬁnite family of at least 13 compact rectangles in the plane, all traversed by a vertical line x = l and let A ∈ I 3,2. If every 13-membered subfamily of B is A-3-pierceable then B is R A-3-pierceable.

Proof: If B is 2-pierceable then by Lemma B.2.5 above we are done. We assume from now on that B is not 2-pierceable. From Theorem 4.1.6 it is suﬃcient to prove that for every B ⊆ B there exists a solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 13. Let I be the set of intervals resulted by intersecting B with the line x = l. If I is not 3-pierceable then by Theorem 2.1.2(ii) there are 4 intervals which are not 3-pierceable and hence there is a D3 (B) ⊆ B of cardinality 4 that is not 3-pierceable. Else (I is 3-pierceable) B is 3-pierceable.

must be pierced by the lower piercing point. Hence, by (B.25) we get Claim B.2.10 Let B ⊆ B be such that B L ⊆ B. The lexicographically smallest piercing point in the solution of the 3-lpiercing problem on B is the upper (middle, lower) piercing point if and only if the lexicographically smallest piercing point in the solution of the 3-lpiercing problem on B is the upper (middle, lower) piercing point, respectively.

We say that B L deﬁnes the type of the solution of the 3-lpiercing problem on B and that the solutions of the 3-lpiercing problem on B L and on B are of the same type.

We now show that D3 (B) = B L ∪ D1 (B∗ ) ∪ D2 (B ∗ ) is a solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 13.

We ﬁrst prove that c3 (D3 (B)) = c3 (B). By monotonicity c3 (D3 (B)) ≤L c3 (B). From (B.23), (B.24) and (B.26) we get that c3 (B) = (c1 (D1 (B∗ )), c2 (D2 (B ∗ ))), so

** c3 (D3 (B)) ≤L (c1 (D1 (B∗ )), c2 (D2 (B ∗ ))). (B.28)**

We recall that D1 (B∗ ) equals either D1 (B T ), D1 (B M ), or D1 (B B ), so the rectangles in D1 (B∗ ) are either both not below lT, or both below lT and above lB, or both not above lB. By applying Claim B.2.9 on D3 (B), the rectangles in D1 (B∗ ) are covered by the same piercing point. Using Claim B.2.10 with B = D3 (B), we get that the solutions of the 3-lpiercing problem on B and on D3 (B) are of the same type. Hence c1 (D3 (B)) pierces D1 (B∗ ) (and possibly more rectangles from D3 (B)). By monotonicity c1 (D3 (B)) ≥L c1 (D1 (B∗ )) so from (B.28) we get c1 (D3 (B)) = c1 (D1 (B∗ )). By the former equation and the deﬁnition of B ∗ the rectangles in D2 (B ∗ ) are not pierced by c1 (D3 (B)). Hence by monotonicity (c2 (D3 (B)), c3 (D3 (B))) ≥L c2 (D2 (B ∗ )), so from (B.28) we get (c2 (D3 (B)), c3 (D3 (B))) = c2 (D2 (B∗ )). Thus by (B.23), (B.24) and (B.26) we get that c3 (D3 (B)) = c3 (B).

It remains to prove that |D3 (B)| ≤ 13. We choose D2 (B ∗ ) as constructed in the proof of Lemma B.2.5, so |D2 (B ∗ )| ≤ 6. By (B.20) and (B.26) there are 3 cases to handle.

and B T B = {1, 2}. The optimal solution on B is indicated by the 3 black points. Thus B∗ = {5, 6}, B ∗ = {1, 2, 3, 4, 7, 8, 9, 10, 11} and c∗ is the 2 white points.