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

We now show that (D, S, ω) obeys both Locality Conditions and that it obeys the Violation Condition. Let (D, S ) ∈ 2D ×2S and (D, S ) ∈ 2D ×2S be such that ω(D, S ) =L ω(D, S ) (so due to Observation 9.3.5 F easable(D, S ) = F easable(D, S )). We need to show that the following two properties hold. ∀h ∈ D, ω(D ∪ {h}, S ) L ω(D, S ) if and only if ω(D ∪ {h}, S ) L ω(D, S ), and ∀h ∈ S, ω(D, S ∪ {h}) L ω(D, S ) if and only if ω(D, S ∪ {h}) L ω(D, S ).

Regarding the second property we note (for every set X ∈ I d, let Int(X) denote its interior and let ∂(X) R denote its boundary)

Case 1 occurs if and only if r(D, S )di does not intersect F easible(D, S ) ∩ S. This happens if and only if r(D, S )di does not intersect F easible(D, S ) ∩ S, which occurs if and only if r(D ∪ {di }, S ) r(D, S ).

Case 2 occurs if and only if C(D, S ) ∈ r(D, S )di and r(D, S )di ∩ F easible(D, S ) ∩ S = ∅. This / happens if and only if C(D, S ) ∈ r(D, S )di and r(D, S )di ∩ F easible(D, S ) ∩ S = ∅, which occurs if / and only if r(D ∪ {di }, S ) = r(D, S ) and C(D ∪ {di }, S ) L C(D, S ).

Case 3 occurs if and only C(D, S ) ∈ r(D, S )di, and there exists j such that among the projections of the boxes in r(D, S )D ∪ {r(D, S )di } on the j’th coordinate, the projection of r(D, S )di results an interval [l, r] with either the smallest r or greatest l. This happens if and only if C(D, S ) ∈ r(D, S )di, and among the projections of the boxes in r(D, S )D ∪ {r(D, S )di } on the j’th coordinate, the projection of r(D, S )di results an interval [l, r] with either the smallest r or greatest l. This occurs if and only if r(D ∪{di }, S ) = r(D, S ), C(D ∪{di }, S ) =L C(D, S ), and (l1 (D ∪{di }, S ), −g1 (D ∪{di }, S ),..., ld (D ∪ {di }, S ), −gd (D ∪ {di }, S )) L (l1 (D, S ), −g1 (D, S ),..., ld (D, S ), −gd (D, S ).

We have just proved that ∀h ∈ D, ω(D ∪ {h}, S ) L ω(D, S ) if and only if ω(D ∪ {h}, S ) L ω(D, S ). Hence (D, S, ω) is a discrete LP-type problem which satisﬁes the Violation Condition.

It is easy to verify that B(D, S) = ({L1 (D, S), G1 (D, S),..., Ld (D, S), Gd (D, S)}, {C(D, S)}) is a basis of a feasible and bounded (D, S) and that the problem is of d-dimension 2d and s-dimension 1.

The “violation test” can easily be implemented in constant time. For a basis B = (BD, BS ) and a delement di, ω(BD ∪{di }, BS ) ω(B) if and only if either r(B)di does not contain C(B), or there exists j such that among the projections of the boxes in r(B)D ∪{r(B)di } on the j’th coordinate, the projection of r(B)h results an interval [l, r] with either the smallest r or greatest l. For an s-element h, ω(BD, BS ∪ {h}) ω(B) if and only if either h lies in the interior of F easible(B), or h lies on the boundary of F easible(B) and h ≤L C(B). The “basis calculation” can be implemented in constant time by calling the violation test a constant number of times. Using a DLP-algorithm such as the one stated in Section 6.3.3, we conclude with

9.3.4 Discrete planar rectilinear p-center problem (p 1) ** Lemma 9.3.**

7 The d-Helly number of the Helly theorem corresponding to the discrete planar rectilinear 2-center problem is unbounded for p 1.

Proof: The fact that the discrete planar rectilinear p-center problem (p 1) does not have a ﬁnite d-Helly number can be proved similarly to the proof of Lemma 9.2.4. Instead of constructing a circle of perimeter (2k + 1)p + 1, we construct a square of perimeter (2k + 1)p + 1 (in l∞ norm) whose sides are rotated by Π radians relatively to the axes.

Corollary 9.3.8 The discrete planar rectilinear 2-center problem cannot be formulated as a ﬁxed d-dimensional discrete LP-type problem.

We conclude this subsection with giving a lower bound for this problem.

** Lemma 9.3.**

9 ([Seg02]) The discrete planar rectilinear 2-center problem requires Ω(n log n) time under the algebraic computation tree model.

9.4 Euclidean p-center problems The deﬁnition is analogous to the one of the planar rectilinear p-center problem where the metric is Euclidean.

9.4.1 Continuous Euclidean p-center problems Megiddo [Me83a] gives a deterministic linear time solution algorithm for the planar Euclidean 1-center problem. [SW92] formulate the Euclidean 1-center problem in I d as a (d + 1)-dimensional LP-type problem R and thus solve it in randomized linear time. The Helly theorem corresponding to this problem with λ = 1 is just the Radius theorem (Theorem 2.1.1).

We conclude this subsection with giving a lower bound for this problem.

** Lemma 9.4.**

1 ([Seg02]) The Euclidean planar 2-center problem requires Ω(n log n) time under the algebraic computation tree model.

9.4.2 Discrete planar Euclidean 1-center problem Lee and Wu prove ** Lemma 9.4.**

2 ([LW86]) The discrete planar Euclidean 1-center requires Ω(n log n) time under the decision tree computation model ([AHU74]).

[LW86] solve this problem in Θ(n log n) optimal time. The Helly theorem corresponding to this problem with λ = 1 is the discrete Radius Theorem, which has unbounded Helly number (Corollary 2.2.5).

** Lemma 9.4.**

3 The d-Helly number of the Helly theorem corresponding to the discrete planar Euclidean 1-center problem is unbounded.

9.5 A summary of Helly numbers for p-center problems in diﬀerent spaces We give a summary of the Helly numbers and d-Helly numbers of the Helly theorems corresponding to the various p-center problems.

All results marked by † are due to [DG82]. The result marked by ‡ is due to Helly’s Theorem.

Regarding the s-Helly numbers of the various discrete p-center problems we have Observation 9.5.1 The s-Helly number of the Helly theorem corresponding to any p-center problem is p.

This is true because the optimal solution has a radius length of at least r if and only if locating the centers at any p locations will yield a radius which is not smaller than r. In other words, for every real r we have ∀S with |S | ≤ p, rp (D, S ) ≥ r ⇒ rp (D, S) ≥ r.

We note that due to Corollary 4.1.3 (Corollary 4.2.3) every p-center (discrete p-center) problem which has an unbounded Helly (d-Helly) number cannot be formulated as a ﬁxed-dimensional LP-type (discrete LP-type) problem, respectively.

Chapter 10 Line transversals in the plane In this section we deal with various planar line transversal problems. In a line transversal decision problem we are given a set of objects H and need to decide whether H admits a line transversal (i.e., a line which has a non-empty intersection with each object in H). In a line transversal optimization problem we have to ﬁnd the minimal scaling factor λ∗ ∈ I + such that there exists a line which has a non-empty intersection R with each scaled object in H. We note that the unscaled family of objects admits a line transversal if and only if the optimal scaling factor λ∗ is at most 1.

The various line transversal problems diﬀer in the restrictions given on the objects in H and on the possible choices of the line transversals.

10.1 Continuous case A possible restriction on the objects in H is that they are translates of a convex set O containing the origin.

We refer to the origin as its reference point. h is a translate of O if there exists a translation vector c ∈ I 2 R + such that h = O + c = {x + c | x ∈ O}. For every scaling factor λ ∈ I R and translate h = O + c let λh = λO + c be the scaled translate (i.e., homothet) of O, which results from scaling O by factor of λ relatively to its reference point, while keeping the translation vector c ﬁxed.

In the line transversal of translates (decision) problem we are given a convex set O containing the origin as its reference point, and a set C = {c1,..., cn } of translation vectors, such that the objects in H = {O + ci ; i = 1,..., n}, are pairwise disjoint. Tverberg [Tv89] showed that if every family H ⊆ H with |H | ≤ 5 admits a line transversal, then also H admits a line transversal (Theorem 2.1.8(v)). Egyed and Wenger [EW89] use this theorem to give a deterministic linear time algorithm to ﬁnd such a line transversal.

Amenta [A94] solves the corresponding optimization problem in randomized linear time. She ﬁrst uses Tverberg’s theorem to formulate the problem as a parameterized Helly system. She then assumes that the set of translates is in general position, to get that the corresponding mathematical programming problem meets the Unique Minimum Condition. Then she applies her main theorem, Theorem 5.1.4, to get a ﬁxeddimensional LP-type formulation for this problem. Last, she applies the randomized LP-type algorithms to solve the problem in linear time. We comment that if the lexicographic version of Tverberg’s theorem has a ﬁnite Helly number (see Theorems 2.3.7, 2.3.8 and 2.3.9 for examples of lexicographic versions of Helly theorems about line transversals), then it will be possible to solve the problem (in the same time complexity) without assuming general position, by using Theorem 5.3.6.

For motivation purposes Amenta notes that the line transversal at λ∗ is tangent to at most three translates, for any non-degenerate example. Since the corresponding Helly number is 5, it is easy to construct situations in which the line transversal is tangent to exactly three of the ﬁve translates. Let us look at the example given by [A93] (Figure 10.1).

Consider the line transversals of the three central balls, as they grow while we increase the scaling factor λ. Assuming that the balls are in general position, there will be three distinct moments (w.r.t. the scaling factor) at which a new connected subset of line transversals becomes feasible. The two remaining balls are positioned so that only the last of these subsets contains a transversal of the whole family.

When the set O is a unit circle this optimization problem is equivalent to both the Euclidean 1-line center problem and the set width problem applied on the set C of translation vectors. (In the Euclidean 1-line center we are given a family H of points and ﬁnd a line which minimizes the maximal distance r of a point in H to the line. In the set width problem we have the same input and want to ﬁnd a pair of closest parallel lines between which all the points in H lie. We note that the line which is parallel to these two lines and lies at equal distance from them, is a line center of H). Both problems have a lower bound of Ω(n log n) under the algebraic computation tree model ([LW86]).

A similar problem is the line transversal of axis-parallel rectangles. Here the family H of objects is of (not necessarily pairwise disjoint) axis-parallel rectangles. The decision problem is solved in linear time via LP-type algorithms or by reducing it to linear programming ([A92], [A94], [Me91]). We are unaware of any linear time algorithms for the corresponding optimization problem. We note that the optimization problem is solvable in randomized linear time by a similar way to the solution of the line transversal of translates optimization problem (for this we use either Theorem 2.3.8 and Theorem 5.3.6, or Theorems 2.1.5, 2.3.8 and 5.3.7).

The last problem we consider in this chapter is the line transversal of a totally separable set H of convex sets (see Deﬁnition 2.1.3). We are unaware of any linear time algorithms for the decision problem, even when the convex sets in H are simple. We call the objects in H simple if they have a constant size storage description, and if the intersections and common tangents between any two objects can be found in constant time. If in addition to the objects in H, we are given an order in which a line transversal should meet the sets, the algorithm of Egyed and Wenger [EW91] solves the problem in linear time. We note in passing that if we are not given this order, it is possible to solve the optimization problem in randomized linear time in a similar way to the solution of the line transversal of translates optimization problem (by using either ** Theorem 2.3.**

7 and Theorem 5.3.6, or Theorems 2.1.4, 2.3.7 and 5.3.7). As explained above, the solution of the optimization problem implies the solution of the corresponding decision problem.

We refer to all the problems in this subsection as continuous because the line transversal can be in any direction and can intersect the y-axis at any point.

10.2 Discrete case I - A ﬁnite number of allowed directions of line transversals In this subsection we deﬁne a discrete version for the line transversal of axis-parallel rectangles optimization problem. We solve it in randomized linear time by using the discrete LP-type framework.

Problem 10.2.1 Given are a set D = {d1,..., dn } of (not necessarily pairwise disjoint) axis-parallel compact rectangles, and a set S = {s1,..., sm } of allowed line directions. Find the minimal scaling factor λ∗ = 1 λ1 (D, S) ∈ I +, such that λ∗ D admits a line transversal whose direction is in S.

R 1 If we choose S to be the (inﬁnite) set of all possible directions, this problem coincides with the continuous one. We can assume that S does not contain the vertical direction and that the directions in S are such that the allowed lines are {y = ax + b | a ∈ S}. (If S does contain a vertical direction, we will take the minimal solution (i.e., scaling factor) of Problem 10.2.1 on S without the vertical direction and on the vertical direction alone. We solve the latter problem in linear time by solving the weighted 1-center problem on the line. The input set of points for this problem is {p1,..., pn }, where for all i, pi is the projection of the reference point of rectangle di on the x-axis. The weight ωi associated to each point pi is l1, where li i is the length of the projection of rectangle di on the x-axis (see Chapter 9 for the deﬁnition of the weighted 1-center problem)).