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

Proof: If c$ = −∞ then the line y = y $ intersects all the rays at −∞ and hence for i = 1,..., n, gi (y $ ) = ai. Suppose y 0 is an optimal solution of the restricted lex1-center problem. From the deﬁnition of functions gi, for i = 1,..., n, gi (y 0 ) ≥ ai, so due to Observation 12.2.2

and that the optimal center is unique, for this case where c$ is ﬁnite.

12.3 A linear time solution algorithm for the min rays problem As in the previous section, let c$ and y $ be an optimal solution for the min rays problem. By using Theorem 12.2.3, p@ = (x@, y $ ) is an optimal center for the restricted lex1-center problem. We deﬁne a test oracle as follows. The input of the test oracle is the same as for the min rays problem with an additional

**point p = (x@, y). The output is one of the following:**

• p is an optimal center.

• p is not an optimal center. All optimal centers lie to the right of p (i.e., y $ y).

• p is not an optimal center. All optimal centers lie to the left of p (i.e., y $ y).

We ﬁrst show that Lemma 12.3.1 The test oracle can be implemented in linear time.

Proof: We ﬁrst note that, u(y), the upper envelope of the rays in the min rays problem, is a unimodal function, i.e., it has either a unique ﬁnite local minimum which is also its global minimum, or the minimum is −∞ and the source of −∞, u−1 (−∞), is a compact interval. (See [JKP72] pp. 52 for a deﬁnition of unimodal one variable functions).

We compute the value of each of the 2n rays at y. If all the values are −∞ we conclude that p is an optimal center. Else there is a ﬁnite maximal value among the 2n calculated values. We look at the rays attaining this maximal value on y. If all of them are decreasing we conclude that p is not an optimal center and y $ y. If all of them are increasing we conclude that p is not an optimal center and y $ y. Else, there are rays of both types and we conclude that p is an optimal center. Clearly, the time consumed in the algorithm given above is linear in n.

We are now ready to prove Theorem 12.3.2 The min rays problem is solvable in Θ(n) time.

the critical values. The value y m can be found in linear time due to Blum, Floyd, Pratt, Rivest and Tarjan [BFPRT73] (see alternatively [CLR90]). At this time we call the test oracle with p = (x@, y m ). This test runs in linear time (Lemma 12.3.1). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of any optimal center. Thus we drop one of the rays in each one of these pairs, namely r. If the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p we act similarly and drop the ray r of at least half of the pairs. In this case we drop at least 4 of the rays.

We process the set of pairs of type (i4) as follows. As before we deﬁne for each pair a critical real value.

This value is the projection on the y axis of the intersection point of the rays composing the pair, as indicated by the big white circle in Figure 12.4 (i4). Now, let y m denote the median of the critical values. At this time we call the test oracle with p = (x@, y m ). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of the optimal center. Thus we drop one of the rays in each one of these pairs, namely r. Now suppose that the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p. The critical values of at least half of the pairs are to the right of y m and hence to the right of the optimal center. We construct a new critical value for each of these pairs as indicated by the small black circle in Figure 12.4 (i4). Now, let y m denote the median of the new critical values. At this time we call the test oracle with p = (x@, y m ). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of any optimal center. Thus we drop one of the rays in each one of these pairs, namely r. If the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p we act similarly and drop the ray r of each one of at least half of the pairs. In this case we drop at least 1 of the rays.

We process the sets of decreasing pairs (d1), (d2), (d3) and (d4) in a symmetric way.

If during the iteration the test oracle returns that p is an optimal center we exit the algorithm and return this point. Otherwise we are left with no more than 8 of the original rays. We arbitrary form pairs of the remaining rays, partition the pairs of rays into the 12 types as before and reiterate until we are left with a constant number of rays. The critical values we associate with these constant number of rays are the projections on the y-axis of their roots and of their intersection points. There is a constant number of such

12.4 A linear time solution algorithm for the lex1-center problem Let p∗ = (x∗, y ∗ ) be an optimal center of the lex1-center problem (12.5). Let c∞ be the solution value of the (non-lexicographic) weighted planar 1-center problem (12.3) and p∞ = (x∞, y ∞ ) be a center realizing this solution.

We observe that if the maximal distance c∞ is realized by an horizontal distance then there exists i such that c∞ = ωi dx (p∞, pi ) ≥ ωi dy (p∞, pi ) and x∗ = x∞. We ﬁnd x∞ by solving Problem (12.3) in linear time as demonstrated in Section 12.1. Next we let x@ = x∞ and ﬁnd an optimal center p@ = (x@, y @ ) for the restricted lex1-center problem by solving the min rays problem in linear time by the algorithm presented in the previous section. Due to Theorem 12.2.3 the solution is an optimal solution for the restricted lex1-center problem.

If the maximal distance c∞ is not realized by an horizontal distance (i.e., it is realized by a vertical distance), we rotate the points in P by π radians around the origin and repeat the above process. We proved Theorem 12.4.1 The lexicographic rectilinear 1-center problem in the plane is solvable in Θ(n) optimal time.

12.5 Concluding remarks We note that our algorithm can be modiﬁed in order to solve, in the same time bound, the following generalizations of the lex1-center problem (with l∞ norm).

• The lex1-center problem in I d. We describe in short the solution algorithm for this problem. As in R the planar problem, we ﬁrst solve the corresponding non-lexicographic 1-center problem. This ﬁxes one of the d coordinates. Then we successively solve d − 1 restricted problems, of decreasing dimensions d − 1, d − 2,..., 1 by decomposing each restricted problem of dimension d into d one-dimensional min rays problems. It thus follows that the total running time is linear in n where the constant is quadratic in d.

• In the all-centers lex1-center problem we are given the same input as for the lex1-center problem.

Instead of ﬁnding an optimal center, one has to ﬁnd all optimal centers.

We now consider another version of the lex1-center problem, the discrete lex1-center problem. In this problem the center must be one of the input points.

The discrete lex1-center problem on the real line is solved in O(n log n) time as follows. Let p∗ be the optimal center of the (non-lexicographic) 1-center problem on the real line. We next ﬁnd the two neighboring points pl, pr ∈ P of p∗. Due to the convexity of the objective function one of pl, pr is an optimal solution. We calculate the lexicographic distances vector from each of pl, pr to the remaining points by ﬁrst calculating the n − 1 distances and then sorting it. We then compare the two vectors. The center realizing the lexicographically smaller vector is an optimal solution. The above operations can be done in O(n log n) total time. We observe that the all-centers discrete non-weighted lex1-center problem on the real line has a lower bound of Ω(n log n) under the algebraic computation tree model by a simple reduction from set equality problem [Be83].

We observe that the discrete lex1-center problem in I d (d ≥ 2) is solved in O(n2 ) time (where the R constant depends exponentially on d) as follows. First construct the n sorted weighted distances vectors from each point in P to all the remaining n − 1 points. This is done by a reduction to the O(n2 ) algorithm of Lee and Ching [LC85] which sorts the n sets of directions from each point in an n-membered set of points in the plane, to the remaining points. The optimal center is the point which realizes the lexicographically smallest vector among the resulting n sorted vectors.

Chapter 13 Concluding remarks [A94] concludes her paper with “...The major open problem is to characterize the Helly systems (X, H) for which there is an objective function ω that gives a ﬁxed dimensional LP-type1 problem (H, ω)”. A partial answer for her question is that every lexicographic Helly system (see Subsection 2.3.3) admits an objective function ω that gives a ﬁxed dimensional LP-type problem (H, ω).

In her thesis ([A93]), Amenta explores the class of LP-type problems and its intimate relationship with Helly theorems. She summarizes her theoretical results as

** Helly ⊃ LP-type ⊃ CP**

that is, the class of problems for which there is a Helly theorem about the constraints, strictly contains the class of ﬁxed-dimensional LP-type problems, which strictly contains the class of CP, convex programming problems.

Let LexHelly denote the class of problems for which there is a lexicographic Helly theorem about the constraints. In this thesis we show that LexHelly ⊂ Helly and that LexHelly ⊆ LP-type.

We also deﬁne discrete Helly theorems, lex-discrete Helly theorems and discrete LP-type problems and show that the class of problems for which there is a lex-discrete Helly theorem about the constraints equals the class of ﬁxed-dimensional discrete LP-type problems. We provide linear time random algorithms for solving ﬁxed-dimensional discrete LP-type problems which satisfy the Violation Condition (Deﬁnition 3.3.15). It is an open problem to provide such algorithms without using the Violation Condition.

In Chapter 11 we formulate the simple stochastic game decision problem as a discrete LP-type problem, and solve it in subexponential time by using the LP-type algorithm of [SW92]. It is an interesting open problem whether more games, for which no subexponential algorithm is currently known, can be formulated as discrete LP-type problems, LP-type problems, or even Linear Programming problems.

Similarly to the continuous case, the connection between discrete Helly theorems and discrete LP-type theory has been mutually proﬁtable. We have proved a few lex-discrete Helly theorems by showing that the discrete abstract problem corresponding to it has a deﬁning set of ﬁxed cardinality (Theorem 4.2.5). Going in 1 Amenta uses the term GLP rather than LP-type.

the other direction, we have showed several geometric optimization problems to be discrete LP-type problems by using discrete Helly theorems.

In this thesis we obtain more than a dozen new discrete, lexicographic and lex-discrete Helly theorems.

We strongly believe that further research will lead to the discovery of more such Helly theorems.

Appendix A Proving theorems related to line transversals A.1 Discrete and lex variants of Theorem 2.1.4 (Theorems 2.2.7, 2.3.7 and 2.4.3) We start by proving a lex-discrete version of Theorem 2.1.4 Proof: (of Theorem 2.4.3) We can assume that ∀a ∈ S, a ≤ a (otherwise we drop from S all slopes greater from a without aﬀecting the theorem). Every non-vertical line in the plane has a real (ﬁnite) slope.

For every pair of two convex sets di and dj from D we denote by (di, dj ) the closed interval of slopes, such that for every a ∈ (di, dj ) there exists a line transversal for di and dj with slope a. Since every 4 sets admit a line transversal with slope from S, every two of these intervals have a common point from S. Hence, due to Theorem 2.2.1, there exists a slope a ∈ S such that each two sets from D admit a common transversal y = ax + b for some b. Let a ∈ S 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 quadruple of objects, that there exists a common line transversal y = a x + b, for dk, di, dj with b ≤ b, so seg[k] ∩ (−∞, b ] = ∅ as needed.

Considering Theorem 2.2.7, we assume that a separating direction is the y-axis (otherwise we rotate the plane relatively to the origin and update S accordingly). Due to Observation 2.4.8 the Helly number of Theorem 2.2.7 is bounded above by the one of its lexicographic version, Theorem 2.4.3, i.e., 4.

The Helly number 4 is tight for Theorem 2.2.7, since Theorem 2.2.10(i), which is a special case of Theorem 2.2.7, has Helly number 4. We now prove a lexicographic (continuous) version of Theorem 2.1.4 Proof: (of Theorem 2.3.7) The proof resembles the one of Theorem 2.4.3.