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

We ﬁrst assume that the following condition holds. In the last paragraph in the proof we will show that this condition is always met. The condition is that each two of the intervals (di, dj ) (deﬁned in the proof of** Theorem 2.4.
**

3 above) have a common point not greater than a. Hence, due to the lexicographic version of Helly’s Theorem, Theorem 2.3.2, there exists a slope a ≤ a such that each two sets from D admit a common transversal with slope a. Let a be the minimal such slope.

For every dk ∈ D we denote by seg[k] the interval resulted by the intersection of the y-axis with all the line transversals with slope a that dk admits. Since each two sets from D admit a common transversal with slope a, the intervals in {seg[k] | dk ∈ D} are pairwise intersecting. Due to Helly’s Theorem, there exists a point b common to all the intervals. Let b be the minimal such b. In other words the line y = a x + b is a line transversal for D. If a a then (a, b ) L (a, b ) and we are done.

Otherwise (a = a ), we need to show that b ≤ b, i.e., ∀k, seg[k] ∩ (−∞, b ] = ∅. Since a = a there exists an interval of slopes (di, dj ) whose minimal slope is a. Let us consider the interval of slopes of all the line transversals for dk, di, dj. The minimal slope in the interval is a. This implies together with the theorem’s assumption about triplets of objects, that there exist a common line transversal y = a x + b, for dk, di, dj which have b ≤ b, so seg[k] ∩ (−∞, b ] = ∅ as needed.

It remains to show that each two intervals of slopes have a common point not greater than a. We use similar arguments as in the proof of Theorem 2.1.4. For such pairs of intervals as (di1, di2 ) and (di1, di3 ) this is assured by the assumption of a common transversal of slope at most a for di1, di2 and di3. We now show that each two intervals, say (di1, di2 ) and (di3, di4 ) have a common point of at most a. Due to the theorem’s assumption the minimal slope for each one of these two intervals is at most a, so if they have a common point, they must have also a common point of at most a. Hence it is suﬃcient to show that these intervals have a common point. If these intervals, (di1, di2 ) and (di3, di4 ), do not have a common point, then a contradiction would result as follows. Each of the intervals (di1, di3 ), (di1, di4 ), (di2, di3 ) and (di2, di4 ) would have points in common with both (di1, di2 ) and (di3, di4 ), so that the following situation arises for a slope a∗ between (di1, di2 ) and (di3, di4 ): the convex sets di1, di2 and also di3, di4, are separable by lines of slope a∗, from which follows the separability of an additional pair by means of each of these two separating lines, but the pairs di1 and di3, di1 and di4, di2 and di3, and di2 and di4 are not separable in this way. This is obviously a contradiction.

**The Helly number 3 is tight due to Observation 2.3.12 and Theorem 2.1.4.**

A.2 Discrete and lex variants of Theorem 2.1.8 (Theorems 2.2.10, 2.3.10 and 2.4.6) We start by presenting an alternate proof for Theorem 2.1.8(i). This proof will be helpful in proving more discrete Helly theorems for line transversals later in this chapter. We use a well known (see for example [Ed87]) geometric duality transformation Deﬁnition A.2.1 Let D be a transformation which maps every point (a, b) in the plane into the non vertical line y = ax − b and vice versa, that is, it maps a non vertical line l to the point D(l) such that D(D(l)) = l.

Let h ⊂ I 2 be a set of points. We extend the deﬁnition of D to sets of points in the natural way D(h) = R {D(p) | p ∈ h}.

We note

Observation A.2.3 D transforms every vertical interval [(a, b), (a, b )] into a strip with slope a, which intersects the y-axis in the interval [(0, −b ), (0, −b)] and transforms the set of all lines with slope a into the vertical line x = a.

Considering an axis-parallel rectangle as an (inﬁnite) union of vertical intervals we get Observation A.2.4 D transforms every axis-parallel rectangle h into an unbounded non-convex polygon D(h), which is the complement of the union of two disjoint unbounded convex polygons. The intersection of D(h) with either one of the x non-positive or the x non-negative halfplanes yields a convex unbounded polygon (see Figure A.1).

Proof: (of Theorem 2.1.8(i)) We assume without loss of generality that the segments are vertical (we can rotate the segments in D around the origin). We use the duality transformation D deﬁned above and consider the corresponding dual problem. Due to Observation A.2.3, each vertical line in the primal is transformed to a strip in the dual. Since the resulting strips are convex sets, we get from Helly’s Theorem that if every 3 strips intersect then all strips intersect. Every point in this intersection equals in the primal problem to a line transversal which intersects H.

This Helly number cannot be reduced to two (consider for instance any 3 non-collinear points in the plane).

Using in the proof above the lexicographic version of Helly’s Theorem, implies an upper bound of 3 for the lexicographic Helly number in Theorem 2.3.10(i). By Observation 2.3.12, the lexicographic Helly number in ** Theorem 2.3.**

10(i) is at least as large as the Helly number of its non-lexicographic version, Theorem 2.1.8(i), so it is exactly 3. We now prove a discrete version of Theorem 2.1.8(i) Proof: (of Theorem 2.2.10(i)) Without loss of generality we assume that the segments are vertical (otherwise we rotate the segments in D around the origin and update S accordingly). If there is no line transversal for D, by Theorem 2.1.8(i) there are 3 translates in D for which there is no line transversal.

Otherwise (there exists a line transversal for D), we use the duality transformation D from Deﬁnition A.2.1 and consider the corresponding dual problem. Due to Observation A.2.3, for every d ∈ D, D(d) is a strip.

The intersection of these strips forms a non-empty polygon P = ∩d∈D D(d). We let P be the polygon containing P, which is resulted by the intersection of the following at most 4 diﬀerent strips. Two strips whose intersection has the same rightmost point as of P, and two strips whose intersection has the same

leftmost point as of P. Observations A.2.3 and A.2.2 imply that a line transversal of D with direction in S exists if and only if there is an intersection between P and some vertical line in D(S).

It is clear from the following example that the Helly number cannot be reduced to 3 Example A.2.5 Let D = {a, b, c, d} consists of the vertical 2-units intervals a = [(−1.5, 1); (−1.5, 3)], b = [(−1, 2); (−1, 4)], c = [(1, 2); (1, 4)] and d = [(1.5, 3); (1.5, 5)] (see left side of Figure A.2) and let S = {s1 = −0.1, s2 = 1.1} be the set of line directions (each direction is represented by a real number). The set of line transversals for each interval is a strip in the dual (see right side of Figure A.2). The feasible region of line transversals is the intersection of the 4 strips D(a), D(b), D(c), D(D), i.e., the quadrangle whose corners are the white points in the ﬁgure. The set of line transversals with directions in S are the two thick vertical lines D(s1 ), D(s2 ). We note that the quadrangle does not intersect either of the lines D(s1 ), D(s2 ), while the intersection of each three strips intersects one of the two vertical lines.

The deﬁnition of ω together with Observation A.2.2 implies that for every a, b ∈ I and (D, S ) ∈ 2D × 2S, R the intervals 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.

If there is no line transversal for D with direction in S, by Theorem 2.2.10(i) there are 4 translates in D for which there is no line transversal with direction in S. We set D to consist of these translates.

Otherwise, the convex polygon P = ∩d ∈D D(d ) is not empty. Observation A.2.2 implies that D admits a line transversal y = ax + b with (a, b) ≤L (a, b ) if and only if P contains the point (a, b). Let dl, dl ∈ D be vertical intervals, such that the left intersection point of D(dl ), D(dl ) equals the leftmost point of P.

Similarly, let dr, dr ∈ D be vertical intervals, such that the right intersection point of D(dr ), D(dr ) equals the rightmost point of P.

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

Otherwise, let a ∈ S be the smallest slope such that P intersects the line x = a. We let d∗ ∈ D be a vertical interval, such that the intersection point (a, y ), of the strip D(d∗ ) and the line x = a, has the highest y. We set D = {dl, dl, d∗ }.

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

Choosing a arbitrary large, say a = 10, and any real b for Example A.2.5, we get that the Helly number cannot be reduced to 3.

We note that Theorem 2.4.6(i) implies Theorem 2.2.10(i) in the following way. Due to Observation 2.4.8 the Helly number in Theorem 2.2.10(i) is bounded from above by 4, the Helly number in Theorem 2.4.6(i).

Due to Example A.2.5 it is at least 4, so it is 4.

We now prove a lexicographic version of Theorem 2.1.8(iii),(iv) by using Theorem 4.1.6 Proof: (of Theorem 2.3.10(iii),(iv)) We will use the duality transformation D from Deﬁnition A.2.1.

Let ω : 2H →I 2 ∪ {∞} be a function such that for every H ⊆ H, ω(H ) is the lexicographically smallest R point in ∩h∈H D(h ), 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 H ⊆ H, the rectangles in H are met by a common R line y = ax + b with (a, b) ≤L (a, b ) if and only if ω(H ) ≤L (a, b ). Moreover, since set intersection is monotone (i.e., A ∩ B ⊆ A, B), (H, ω) is an abstract problem which meets the Monotonicity Condition.

Hence, due to Theorem 4.1.6, it is suﬃcient to show that for every H ⊆ H, there exists a solution deﬁning set H of cardinality at most 5.

If there is no line transversal for H, by Theorem 2.1.8(v) there are at most 5 translates in H which do not admit a common line transversal. We set H to consist of these translates.

Otherwise, H admits a line transversal. Due to Observation A.2.4 the intersection of ∩h∈H D(h) with the x non-negative halfplane (the x non-positive halfplane) is a (possibly empty) convex polygon P+ (P− ), respectively. If P− is not empty, there exist at most two translates h1, h2 ∈ H which determine the lexicographically smallest point in P− (i.e., lexicographic min P− = lexicographic min(D(h1 ) ∩ D(h2 ))). We set H = {h1, h2 }.

Otherwise (P− is empty and P+ is not empty), due to Helly’s Theorem there exists a set H ⊆ H of cardinality at most 3 such that (I + ×I R)∩(∩h∈H D(h)) = ∅. Moreover, since P+ is not empty there exist at R most two translates h1, h2 ∈ H which determine the lexicographically smallest point in P+ (i.e., lexicographic min P+ = lexicographic min((I + × I ∩ D(h1 ) ∩ D(h2 ))). In this case we set H = H ∪ {h1, h2 }.

R R) In all cases, H is a solution deﬁning set for H with cardinality at most 5, as required.

From Observation 2.4.8 and the fact that the Helly number of the corresponding non-lexicographic Helly theorem, Theorem 2.1.8(iii),(iv), is 5, we get that the Helly number cannot be reduced to 4. We now prove a lex-discrete version of Theorem 2.1.8(iii),(iv) using Theorem 4.2.5 Proof: (of Theorem 2.4.6(iii),(iv)) 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 lexiR cographically 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 R D S (D, S ) ∈ 2 × 2, 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 | ≤ 7.

We ﬁrst consider the case where D admits a line transversal. Let P+ (P− ) denote the intersection of ∩d ∈D D(d ) with the x non-negative (the x non-positive) halfplane, respectively. Due to Observation A.2.4, P+ and P− are (possibly empty) convex polygons.

For X = P−, P+, let dl (X), dl (X) ∈ D be rectangles such that the leftmost intersection point of D(dl ), D(dl ) equals the leftmost point in X. Similarly, let dr (X), dr (X) ∈ D be such that the rightmost intersection point of D(dr ), D(dr ) equals the rightmost point in X. In this way at most 8 rectangles determine the leftmost and rightmost extreme points in P− and P+.

Observations A.2.2 and A.2.3, and the deﬁnition of P+ and P− imply that D admits a line transversal with direction in S if and only if the intersection between P+ ∪ P− and D(S ) is not empty. By making a more careful analysis, which takes into consideration the fact that the objects in D are pairwise disjoint translates of a rectangle, we will show that the leftmost and rightmost points in P+ and P− are determined by at most 7 polygons. I.e., we can choose {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), dr (P+ ), dr (P+ )} such that the set is of cardinality at most 7.