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

The projection of P+ on the x-axis results an interval [slmin, slmax ] of non-negative slopes with which there exists a line transversal for D. Similarly, the projection of P− on the x-axis results an interval [slmin, slmax ] of non-positive slopes with which there exists a line transversal for D. We call [slmin, slmax ] ∪ [slmin, slmax ] the slope range corresponding to D. The 2 rectangles dl (P− ), dl (P− ) determine slmin, the minimal non-positive slope of a line transversal for D. Similarly, dr (P+ ), dr (P+ ) determine slmax, the maximal non-negative slope of a line transversal for D. For example, let D1 be the set consisting of the 4 pairwise disjoint translates of a square as drawn in Figure A.3. Rectangles 1 and 2 determine the maximal non-negative slope of a line transversal, and rectangles 3 and 4 determine the minimal non-positive slope of a line transversal. In this example the range of non-positive slopes of line transversals for D1 is [slmin, slmax ] = [−0.2, 0] and the range of non-negative slopes is [slmin, slmax ] = [0, 0.2]. Any subset of D1 containing only 3 rectangles has a slope range strictly containing the slope range corresponding to D1. We note moving the squares in Figure A.3 towards the origin, may cause their slope range to strictly contain the slope range corresponding to D1. Let D2 be the set consisting of the 4 squares in a ﬁgure such as Figure A.3 rotated by Π radians relatively to the origin.

The slope range corresponding to D2 is [slmin, slmax ] = [−∞, −5] and [slmin, slmax ] = [5, ∞]. Any subset of D2 containing only 3 rectangles has a slope range strictly containing the slope range corresponding to D2.

Again, we note that moving the squares towards the origin may result a slope range strictly containing the original one. We note that D1 ∪D2 does not admit a line transversal, since the intersection of the slope ranges corresponding to D1 and D2 is empty. We now show that it is not possible to move the squares in D1 ∪ D2 towards the origin, while keeping the squares pairwise disjoint, such that the slope range corresponding to the 8 translated squares is not empty and is diﬀerent from the slope range corresponding to any subset of 7 squares. We will show that the above holds even if we take translates of a rectangle instead of a square.

Let y denote the height of the rectangle O and let x denote its width. In Figure A.4(a) the 4 rectangles are moved as much as possible towards the origin. Let D1 be the set consisting of these 4 rectangles, and let y α be the maximal angle of a line transversal for D1. We get that α = arctan 2x. Similarly, in Figure A.4(b) the 4 rectangles are moved as much as possible towards the origin. Let D2 be the set consisting of these 4 rectangles, and let β be the angle between the y-axis and the line transversal for D2 with the minimal positive x slope. We get that β = arctan 2y. (We note that a rectangle in D1 may have a non-empty intersection with a rectangle in D2 ). In order to get that D1 ∪ D2 admits a line transversal, we must have α + β ≥ Π. To 2 conclude our proof it is therefore suﬃcient to show that α + β Π. 2

We get f (1) 0 so f (z) attains its minimum in z = 1 (f (1) = 2 arctan 2 Π ). We note that for any other positive ﬁnite value for z we still get α + β = f (z) Π as needed.

We now determine a solution deﬁning set for D. If P+ ∪ P− does not intersect any of the vertical lines in D(S ) we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), dr (P+ ), dr (P+ )}.

Otherwise, let x = a the vertical line in D(S ) with the minimal a which P+ ∪ P− intersects. We let d∗ ∈ D be a rectangle such that the lowest (w.r.t. the y-axis) intersection point (a, y ), of the polygon D(d∗ ) with the line x = a, has the highest y. If P− intersects the line x = a we set D = {dl (P− ), dl (P− ), d∗ }.

Otherwise P+ intersects the line x = a and we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), d∗ }.

If D does not admit a line transversal, then due to Theorem 2.1.8(v) there are at most 5 translates in D which do not admit a line transversal. We set D to consist of these rectangles.

In all cases, (D, S ) is a solution deﬁning set for (D, S ) with cardinality at most 7, as needed.

**The following example shows that the Helly number cannot be reduced to 6**

Example A.2.6 Let D = {a, b, c, d, e, f, g} consists of the 4-units length open squares such that a is centered at (2,2); b is centered at (−2 4, 0); c is centered at (−2 9, 4); d is centered at ( 4, 8), e is centered at (−1 2, −4);

f is centered at (−1, 12); and g is centered at ( 7, −8). Let a = b = 100.

max = 8, a and c determine slmin = −18, d and e determine We observe that a and b determine sl min = 4 17, and f and g determine slmax = −7. Hence the corresponding slope range is [−18, −7] ∪ [4 17, 8].

sl Let S = {−18 −, −7 +, 4 17 −, 8 + } (all of these slopes are smaller than a ). Since D is ﬁnite it is possible to choose 0 small enough such that D does not have a line transversal with direction in S but any of its proper subsets does.

(We note that there exists δ 0 small enough such that we can modify this example to closed squares of length 4 − δ, so the corresponding slope range will not change signiﬁcantly, and consequently the set of slope directions will be similar to S) We note that Theorem 2.4.6(iii),(iv) implies Theorem 2.2.10(iii),(iv) in the following way. Due to Observation 2.4.8, the Helly number in Theorem 2.2.10(iii),(iv) is bounded from above by 7, the Helly number in** Theorem 2.4.**

6(iii),(iv). Due to Example A.2.6, it is at least 7, so it is 7.

Figure A.4: 8 rectangles and their corresponding line transversals slope ranges.

A.3 Discrete and lex variants of Theorem 2.1.6 (Theorems 2.2.9, 2.3.9 and 2.4.5) We start by proving a lexicographic version of Theorem 2.1.6 Proof: (of Theorem 2.3.9) We consider the corresponding dual problem. Due to Observation A.2.4, each rectangle d ∈ D in the primal is transformed into a polygon D(d) such that its intersection with the x non-negative halfplane is a convex polygon p(d). Due to Observation A.2.2, D admits a line transversal y = ax + b with a non-negative slope a and (a, b) ≤L (a, b ) if and only if the convex polygon ∩d∈D p(d) contains a point which is not lexicographically greater than (a, b ). We conclude the proof by applying the lexicographic version of Helly’s theorem (Theorem 2.3.2) on the convex polygons p(d), ∀d ∈ D.

We now prove a lex-discrete version of Theorem 2.1.6 by using Theorem 4.2.5 Proof: (of Theorem 2.4.5) We will use the duality transformation D from Deﬁnition A.2.1. Let ω : 2D ×2S →I 2 ∪{∞} be a function such that for every (D, S ) ∈ 2D ×2S, ω(D, S ) is the lexicographically R smallest point in ∩d ∈D D(d ) with x-coordinate in S, if such intersection is not empty, and ∞ otherwise.

The deﬁnition of ω together with Observation A.2.2 implies that for every a, b ∈ I and (D, S ) ∈ 2D × 2S, R the rectangles in D are met by a common line y = ax + b with (a, b) ≤L (a, b ) and a ∈ S if and only if ω(D, S ) ≤L (a, b ). Moreover, since set intersection is monotone (i.e., A ∩ B ⊆ A, B), (D, S, ω) is a discrete abstract problem (see Deﬁnition 3.3.2), which meets the Monotonicity of Demand Condition. Hence, due to ** Theorem 4.2.**

5, it is suﬃcient to show that for every (D, S ) ∈ 2D × 2S, there exists a solution deﬁning set (D, S ) with |D | ≤ 4. orem).

If D does not admit a line transversal, by Theorem 2.1.6 there are 3 rectangles in D which do not admit a common line transversal. We let D be the set consisting of these rectangles.

Otherwise we let P+, dl (P+ ), dl (P+ ), dr (P+ ) and dr (P+ ) be as deﬁned in the proof of Theorem 2.4.6(iii),(iv).

If P+ does not intersect any of the vertical lines in D(S ) we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− )}.

If P+ does intersect D(S ), we let x = a be the vertical line in D(S) with the minimal a which P− intersects. We let d∗ ∈ D be such that the lowest (w.r.t. the y-axis) intersection point (a, y ), of the polygon D(d∗ ) with the line x = a, has the highest y. We set D = {dl (P− ), dl (P− ), d∗ }.

In all cases, (D, S ) is a solution deﬁning set for (D, S ) with cardinality at most 4, as needed.

**The Helly number cannot be reduced to 3 due to Example A.2.5 (with a = b = 2).**

Corollary A.3.1 Let D be a family of axis-parallel rectangles in the plane and for every d ∈ D, let D(d) be the set of line transversals which d admits in the dual (see Deﬁnition A.2.1). Let P (D) = ∩d∈D D(d) be the set of line transversals which D admits. The intersection of P (D) with either the x non-negative or x non-positive halfplanes is a convex polygon. The slopes of line transversals with non-negative (non-positive) slopes for D generate an interval [slmin, slmax] ([slmin, slmax ]) resulted by the projection of P (D) on the nonnegative (non-positive) part of the x-axis, respectively. Each of the 4 endpoints of these two intervals is determined by two rectangles.

We note that Theorem 2.4.5 implies Theorem 2.2.9 in the following way. Due to Observation 2.4.8, the Helly number in Theorem 2.2.9 is bounded from above by 4. Due to Example A.2.5, it is at least 4, so it is 4.

Appendix B Proving Theorem 2.3.4 In this chapter we prove Theorem 2.3.4, that is

We note that so far we have shown in Section 2.3 that h∗ (2, 2) h(2, 2) and that h∗ (3, 1) h(3, 1) = 2.

Before proving Theorem 2.3.4, we comment on the relation between non-lexicographic and lexicographic p-pierceability.

Proof: We ﬁrst note that for every (p − 1)-pierceable B, there is a lexicographically large enough point M ∈ I d such that B is Ap−1 -(p − 1)-pierceable for Ap−1 = (M,..., M ). Moreover R

B.1 Proving Cases (i), (ii) and (v) Proof: (of Theorem 2.3.4 cases (i),(ii) and (v)) Let B be a ﬁnite set of axis-parallel rectangles in I d and let (B, ωp ) be an abstract problem over the totally R ordered set I 2p ∪ {∞} where for every B ⊆ B and natural number p, ωp (B ) is the lexicographically R smallest p-piercing vector which is feasible for B (if B is not p-pierceable, we set ωp (B ) = ∞). Since adding a rectangle b to B cannot lexicographically decrease the lexicographically smallest feasible p-piercing vector, i.e., ωp (B ∪ {b}) ≥L ωp (B), we get that (B, ωp ) is an abstract problem which meets the Monotonicity Condition. From Theorem 4.1.6 it is suﬃcient to ﬁnd for every B ⊆ B a solution deﬁning set for B with cardinality which is bounded by the Helly number we want to prove. Let Aopt be the solution of the lexicographic p-piercing optimization problem on B.

Case (i) (h∗ (d, 1) = max(2, d)) We ﬁrst show that h∗ (d, 1) ≥ max(2, d). By Observation 2.3.12 and Theorem 2.1.2(i) h∗ (d, 1) ≥ h(d, 1) = 2. If B is 1-pierceable, for every i = 1,..., d we project B onto the i’th coordinate and thus get a one dimensional 1-piercing problem. Let bi ∈ B be a box whose projection on the i’th coordinate is an interval [li, ri ] with the greatest li. Since B intersects, li is inside the projection of B on the i’th coordinate. Let B = {b1,..., bd }. We observe that Aopt = (l1,..., ld ). It is possible to choose a set B such that B and B are Aopt -1-pierceable and there exists a suﬃciently small 0 such that neither B nor B are (l1,..., ld − )-1-pierceable but every proper subset of B is (l1,..., ld − )-1-pierceable. Hence h∗ (d, 1) ≥ max(2, d).

We now show that h∗ (d, 1) ≤ max(2, d). If there exist 2 boxes in B which are disjoint then B is not 1-pierceable. If every 2 boxes of B intersect then by Theorem 2.1.2(i) B intersects, and the lexicographically smallest intersection vector is determined by B deﬁned above. B is a solution deﬁning set for B of cardinality at most d. Hence h∗ (d, 1) ≤ max(2, d).

Case (ii) (h∗ (1, p) = p + 1) From Theorem 2.1.2(ii) and Observation 2.3.12 it remains to prove that h∗ (1, p) ≤ p + 1. If there exist p + 1 intervals in B which are pairwise disjoint then B is not p-pierceable and these p + 1 intervals serve as a solution deﬁning set for B. If every p + 1 intervals of B are p-pierceable then by Theorem 2.1.2(ii) B is p-pierceable. We can suppose it is not (p − 1)-pierceable. Let bp ∈ B be an interval [lp, rp ] with the greatest lp (if there are several such intervals, we choose the one with the minimal rp ). We look at the set of intervals which are not pierced by lp and deﬁne bp−1,..., b1 and lp−1,..., l1 recursively. Let B = {b1,..., bp }. B is a solution deﬁning set for B of cardinality at most p. (We note that if there are several intervals with greatest lp, not choosing the one with the minimal rp may cause B not to be a solution deﬁning set for B.) Thus, we conclude that h∗ (1, p) ≤ p + 1.

Case (v) (h∗ (d, p) = ∞ for d ≥ 2, p ≥ 3 and (d, p) = (2, 3)) It follows directly from Theorem 2.1.2(v) and Observation 2.3.12.

B.2 Some useful deﬁnitions and lemmas In order to prove cases (iii) and (iv) we need to give several deﬁnitions.

Deﬁnition B.2.1 Let B be a ﬁnite family of axis-parallel compact rectangles in the plane.

• Suppose B is 2-pierceable and let B ⊆ B. Let (c1, c2 ) ∈ I 4 be a feasible 2-piercing vector of B. We R say that (c1, c2 ) is a solution of type I and that B is type I 2-pierceable, if one of c1, c2 pierces both bT (B ) and bR (B ). Otherwise we say that (c1, c2 ) is a solution of type II and that B is type II 2pierceable. A ﬁnite set of compact rectangles is 2-pierceable if either it is type I 2-pierceable or type II 2-pierceable or both. We note that a ﬁnite set of compact rectangles may be 2-pierceable and not type I (type II) 2-pierceable, respectively. We let c2I (B ) (c2II (B )) denote the lexicographically smallest solution of the type I (type II) 2-piercing problem on B, if one exists, and ∞ otherwise, respectively.