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

In this way c3XX (D3XX (B )) = c3XX (B ). We note that even though the solution of type XX 3-lpiercing problem is unique, its solution deﬁning set is not necessarily unique.

In our proof we decompose the type XX 3-lpiercing problem on B into the 1-lpiercing problem on B, and a 2-lpiercing problem on B 2 of a type to be speciﬁed below, where B = B 1 B 2. (In this way

By cases (i)-(iii) of Theorem 2.3.4 we bound the sizes of a deﬁning set D1 (B 1 ), for the 1-lpiercing problem on B 1 and of a deﬁning set, D2Z (B 2 ), for the type Z 2-lpiercing problem on B 2. We include B∗ in D3XX (B) so that the location domains of D3XX (B) and of B will be identical. We include B ∗ in D3XX (B) in order to make D3XX (B) non 2-pierceable. We note that when XX = T L or XX = BL, the solution of the type XX 3-lpiercing problem on B∗ ∪ B ∗ ∪ D1 (B 1 ) ∪ D2 (B 2 ) may be lsmaller than the one on B. For this reason we will include in D3XX (B) a last subset B3 ⊂ B which will negate such a possibility.

The proof outline is as follows. The main part of the proof is building solution deﬁning sets D3T R (B), D3BR (B), D3T L (B) and D3BL (B) for the 3-lpiercing problems of the 4 types above, with the structure presented in (B.31). Having this at hand, we will use Observation B.4.1 Let D3T R (B), D3BR (B), D3T L (B), D3BL (B) be solution deﬁning sets for the 3-lpiercing problems of the 4 types above. A possible solution deﬁning set for the 3-lpiercing problem on B is

Since we study the case where B is 3-pierceable and not 2-pierceable, the solution of the 3-lpiercing problem on B is of one of the 4 types, say Y Y. Due to the fact that D3Y Y (B) is a deﬁning set for the type Y Y 3-lpiercing

is a type T R solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 11. (See (B.29) and (B.30) for the deﬁnitions of B∗ and B ∗. This shows that B3 = ∅ in (B.31) when XX = T R.). We start by calculating its cardinality. Since D1 (B 1 ) ∩ D2 (B 2 ) = ∅, |D3T R (B) \ (B∗ ∪ B ∗ )| = |D1 (B 1 ) \ (B∗ ∪ B ∗ )| + |D2 (B 2 ) \ (B∗ ∪ B ∗ )|. Since D1 (B 1 ) ⊂ B∗, D1 (B 1 ) \ (B∗ ∪ B ∗ ) = ∅. Since bB ∈ (D2 (B 2 ) ∩ B∗ ), we get that |D2 (B 2 ) \ (B∗ ∪ B ∗ )| ≤ 6 − 1. Hence |D3T R (B) \ (B∗ ∪ B ∗ )| ≤ 5 and |D3T R (B)| ≤ 11. We now show that D3T R (B) is a type T R deﬁning set for B. Due to (B.34) it is enough to show that (D1 (B 1 ), 1); (D2 (B 2 ), 2) is a valid decomposition for the type T R solution of the 3-lpiercing problem on D1 (B 1 )∪D2 (B 2 ). Moving some elements from D2 (B 2 ) to be pierced by the piercing point of D1 (B 1 ) is not possible due to Observation B.3.2 coupled with the fact that all the rectangles in D2 (B 2 ) are not pierced by cT R. On the other hand, when we look for a T R type solution, all the rectangles of D1 (B 1 ) must be pierced by the same piercing point.

Suppose that there exists a feasible solution for the type BR 3-piercing problem on B. (We note that among the solutions of this type the lsmallest point which pierces both bB and bR is either cBR = (xBR, y BR ) or a point (xBR, y) with y y BR.) From the deﬁnition of the rectangles composing B∗, for every valid decomposition of the type BR 3-lpiercing problem on B, ((B 1, 1); (B 2, 2)), the lexicographically greatest point among the 3 piercing points is the piercing point which pierces both bB and bR, i.e., c1 (B 1 ) L c1 (B 2 ) and c1 (B 1 ) L c2 (B 2 ). We now deﬁne such a valid decomposition. Let B 2 = B \ P (cBR ) be the set of all the rectangles of B which are not pierced by cBR. We let c2 (B 2 ) = (c1 (B 2 ), c2 (B 2 )) ∈ I 4 be the solution of the R 2-lpiercing problem on B 2 and D2 (B 2 ) be a solution deﬁning set for this problem. By Corollary B.3.7 we choose D2 (B 2 ) such that |D2 (B 2 )| ≤ 6 and bT (B 2 ) = bT ∈ D2 (B 2 ). Let B 1 = B \ P (c2 (B 2 )) be the set of all the rectangles in B which are pierced by neither c1 (B 2 ) nor c2 (B 2 ). We let c1 (B 1 ) ∈ I 2 be the solution R of the 1-lpiercing problem on B, and D1 (B ) be a solution deﬁning set for this problem. By the remark written after the proof of Lemma B.2.3 (we can use this lemma here since B 1 is 1-pierceable so an horizontal line traverses all its rectangles), we choose D1 (B 1 ) such that |D1 (B 1 )| ≤ 2 and bR (B 1 ) = bR ∈ D1 (B 1 ). We note that by the construction we get that

is a type BR solution deﬁning set of cardinality at most 12. (This shows that B3 = ∅ in (B.31) when XX = BR.) We start with the cardinality calculations. Since bR ∈ (D1 (B 1 ) ∩ B∗ ) and bT ∈ (D2 (B 2 ) ∩ B∗ ) we get |D3BR (D) \ (B∗ ∪ B ∗ )| ≤ (2 − 1) + (6 − 1) = 6, so |D3BR (D)| ≤ 12. We now show that D3BR (B) is a solution deﬁning set for the type BR 3-lpiercing problem on B. Due to (B.35) it is enough to show that (D1 (B 1 ), 1); (D2 (B 2 ), 2) is a valid decomposition for the type BR solution for the 3-lpiercing problem on D1 (B 1 ) ∪ D2 (B 2 ). Moving some elements from D2 (B 2 ) to be pierced by the piercing point of D1 (B 1 ) is not possible due to Observation B.3.2 coupled with the fact that all the rectangles in D2 (B 2 ) are not pierced by cBR. We cannot decrease the solution on D1 (B 1 ) by moving elements from D1 (B 1 ) to be pierced by the piercing points of D2 (B 2 ) (without changing the value of the 2-lpiercing problem to be more than the solution on D2 (B 2 )) as all the rectangles in D1 (B 1 ) are not pierced by c2 (B 2 ).

Suppose that there exists a solution for the type T L 3-piercing problem on B. Hence there exists a valid decomposition (B 1, 1); (B 2, 2I) for the type T L 3-lpiercing problem on B as explained above. To identify such a valid decomposition, we will next successively generate a sequence of decompositions on B, where one of them is the one mentioned above. We note that among the solutions of type T L for the 3-piercing problem on B, the lexicographically smallest point which pierces both bT and bL is either cT L = (xT L, y T L ) or a point (x, y T L ) with x xT L. We observe that we have monotonicity in the sense that P ((x1, y T L )) ⊆ P ((x2, y T L )) ⊆ P (cT L ) for every x1 ≤ x2 ≤ xT L. Let

Let m = |B 1,0 \ {bT, bL }|. We sort the rectangles in B 1,0 \ {bT, bL } = {b1,..., bm } by their left edge such that b1 is a rectangle with the rightmost left edge, and bm is a rectangle with the leftmost left edge. This sorting is not necessarily unique (e.g., when there are several rectangles which have an identical projection of the left edge on the x-axis). For i = 1,..., m let

We let c1 (B 1,i ) ∈ I 2 be the solution of the 1-lpiercing problem on B 1,i. We will later on deﬁne a solution R deﬁning set D1 (B 1,mi ) for the 1-lpiercing problem on B 1,i which satisﬁes

In this way we ensure that all the rectangles in D2I (B 2,j ) must be pierced by two points. Thus we proved that D3T L (B) is a solution deﬁning set for the type T L 3-lpiercing problem on B. |D1 (B 1,j ) \ (B∗ ∪ B ∗ )| ≤ 3 − 2 = 1, |D2I (B 2,j ) \ (B∗ ∪ B ∗ )| ≤ 4 − 1 = 3, and |B3 \ (D1 (B 1,j ) ∪ B∗ ∪ B ∗ )| ≤ (5 + 1) − (2 + 1) = 3 so |D3T L (B) \ (B∗ ∪ B ∗ )| ≤ 1 + 3 + 3 = 7, so |D3T L (B)| ≤ 13.

c1 (B 1,j ) L c1 (B 2,j ): If k = m then we let 2I

Since we are dealing with a type T L solution, these two rectangles must be pierced by the same piercing point. In this case we deﬁne B L = ∅. Otherwise (j = m), because of optimality there exists a rectangle b ∈ {bj+1,..., bk+1 }, such that b is pierced by none of the points in c2I (B 2,j ), and

remaining elements. Otherwise (the solution of the 1-lpiercing problem on D1 (B 1,j ) \ {bj+1 }(= {bT, bL }) is lsmaller than c1 (B 2,j )), due to optimality, B \ P (c1 ({bT, bL })) = B 2,m is not type I 2-pierceable. Hence, 2I by Corollary B.3.10 there exists a subset B L ⊆ B 2,m of at most 5 elements which contains bR (B 2,m ) = bR, bB (B 2,m ) = bB and is not type I 2-pierceable. Thus we can not decrease the solution on D1 (B 1,j ) ∪ D2I (B 2,j ) ∪ B∗ ∪ B ∗ ∪ B L by decomposing it into a 1-lpiercing problem on a proper subset of D1 (B 1,j ) and a 2-lpiercing problem on the remaining elements. We include B L in B3 deﬁned below. By that we guarantee that all the rectangles in D1 (B 1,j ) must be pierced by one point.

We now force all the rectangles in D2I (B 2,j ) to be pierced by two points using the following construction of D2I (B 2,j ). From the monotonicity of the sequence (B 2,i ) we have c2I (B 2,j ) ≥L c2I (B 2,0 ). From optimality we have (c1 (B 2,j ), c2 (B 2,j )) = c2I (B 2,j ) ≤L c2I (B 2,0 ) = (c1 (B 2,0 ), c2 (B 2,0 )) so c2I (B 2,j ) = c2I (B 2,0 ). By 2I 2I 2I 2I monotonicity, since bR, bT, bL, bB (deﬁned as the rectangles with the rightmost left, highest bottom leftmost right and lowest top edge in D2I (B 2,0 ), respectively) are not pierced by cT L, they are not pierced by any c1 (B 1,i ); i = 1,..., m. We let D2I (B 2,j ) = D2I (B 2,0 ) where D2I (B 2,0 ) is deﬁned in (B.36). Since none of the rectangles in B 2,0 is pierced by any c1 (B 1,i );

i = 1,..., m; we conclude that all the rectangles in D2 (B 2,j ) must be pierced by two piercing points. We let

Thus we proved that D3T L (B) is a solution deﬁning set for the type T L 3-lpiercing problem on B. Making the same cardinality calculations as in the previous case we get that |D3T L (B) \ (B∗ ∪ B ∗ )| ≤ 1 + 3 + 3 = 7, so |D3T L (B)| ≤ 13.

From the arguments above D3T L (B) is a deﬁning set of the solution of type T L for the 3-lpiercing problem on B, of cardinality at most 13.

Suppose that there exists a solution for the type BL 3-piercing problem on B. Among the solutions of this type the lexicographically smallest point which pierces both bB and bL is either cBL = (xBL, y BL ) or a point (x, y) with x ≤ xBL and y ≤ y BL. We note that due to Observation B.3.2 we get monotonicity in the sense that P ((x1, y1 )) ⊆ P ((x2, y2 )) ⊆ P (cBL ) for every x1 ≤ x2 ≤ xBL and y1 ≤ y2 ≤ y BL. Let (cx, cy ) = c1, c1, c2 ∈ I 2 be the 3 piercing points in the solution of the type BL 3-lpiercing problem on B, R where c1 pierces both bB and bL. Let c2 = (c1, c2 ). From the existence of a solution of type BL, there exists a valid decomposition (B 1, 1); (B 2, 2II) for the type BL 3-piercing problem on B.

Let B 1 = P (c1 ) be the set of all rectangles in B which c1 pierces (bB, bL ∈ B 1 ). Let B 2 = B \ B 1. Clearly c2 is a 2-piercing vector for B 2 and bT, bR ∈ B 2. Let Br ⊆ B 1 be the set of rectangles with the rightmost left edge which are pierced by c1 (i.e., the projection of their left edge on the x axis is cx ) and not by c2.

Similarly, let Bt ⊆ B 1 be the set of rectangles with the topmost bottom edge which are pierced by c1 (i.e., the projection of their bottom edge on the y axis is cy ) and not by c2. We will next deﬁne {br, bt }, a solution deﬁning set for the 1-lpiercing problem on B 1 which satisﬁes the following properties: The projection of the left edge of br on the x axis is identical to the one of c1 (B 1 ) (so br “deﬁnes” the x coordinate of c1 (B 1 )), and the projection of the bottom edge of bt on the y axis is identical to the one of c1 (B 1 ) (so bt “deﬁnes” the y coordinate of c1 (B 1 )).

We will next deﬁne B3, D1 (B 1 ) and D2I (B 2 ) for (B.31) where XX = BT L, We note that c1 L c2 and that the relative position between c1 and c1 can be one of the following two cases.

c1 L c1 : By Corollary B.3.11 we choose D2II (B 2 ), a solution deﬁning set for the type II 2-lpiercing problem on B 2, such that |D2II (B 2 )| ≤ 5 and bR (B 2 ) = bR, bT (B 2 ) = bT ∈ D2II (B 2 ).

We now deﬁne D1 (B 1 ) and some auxiliary sets BL, BB. If bB ∈ Br (this implies that the solution of the

set for the type II 2-piercing problem on B 2 ∪ Br which satisﬁes the following properties. BL contains 4 rectangles which deﬁne its location domain and a ﬁfth rectangle which negates the existence of a type II solution. Thus |BL | ≤ 5 and bR (B 2 ∪ Br ) = bR, bT (B 2 ∪ Br ) = bT ∈ BL. BL must contain an element from Br which we denote by bl.

Similarly, if bL ∈ Bt (this implies that the solution of the 1-lpiercing problem on B 1 \ Bt ∪ {bB, bL } is not lower than c1 ) we deﬁne bb = bL and BB = ∅. If bL ∈ Bt and bB ∈ Bt we deﬁne bb = bB and BB = ∅.

/1 1 Finally, if bL, bB ∈ Bt then the solution of the 1-lpiercing problem on B 1 \ Bt is lsmaller than c1. Hence, /1 1 because of the optimality, B ∪ Bt is not type II 2-pierceable. Let BB be a solution deﬁning set of the type II 2-piercing problem on B 2 ∪Bt. Due to Corollary B.3.12 we choose BB, a solution deﬁning set for the type II 2-piercing problem on B ∪ Bt r which satisﬁes the following properties. BB contains 4 rectangles which deﬁne its location domain and a ﬁfth rectangle which negates the existence of a type II solution. In this way |BB | ≤ 5 and bR (B 2 ∪ Bt ) = bR, bT (B 2 ∪ Bt ) = bT ∈ BB. BB must contain an element from Bt which we denote by bb. By the deﬁnition of bb, bl ;

and let D3T L (B) = D1 (B 1 ) ∪ D2II (B 2 ) ∪ B3 ∪ B∗ ∪ B ∗.

Thus we proved that D3BL (B) is a deﬁning set for the solution of the type BL 3-lpiercing problem on B.

Clearly |D3BL (B) \ (B∗ ∪ B ∗ )| ≤ (4 − 2) + (5 − 2) + ((5 − 3) + (5 − 3) + 1) = 10, so |D3BL (B)| ≤ 16.

c1 L c1 : Let B 2,0 = B \ P (cBL ) be the set of all the rectangles in B which are not pierced by cBL. Let c2II (B 2,0 ) = (c1 (B 2,0 ), c2 (B 2,0 )) ∈ I 4 be the solution of the type II 2-lpiercing problem on B 2,0. By R 2II 2II Corollary B.3.11 we choose D2II (B 2,0 ) ⊆ B 2,0, a solution deﬁning set for the type II 2-lpiercing problem on B 2,0, such that |D2II (B 2,0 )| ≤ 5 and bR, bT ∈ D2II (B 2,0 ). Since c1 must pierce bB and bL it is not above and not to the right of cBL. Hence, by monotonicity (Observation B.3.2) we get that B 2 ⊇ B 2,0 and c2 ≥L c2II (B 2,0 ). From the optimality of the solution of the 3-lpiercing problem on B, c2 ≤L c2II (B 2,0 ).