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

tvS be the time needed for checking whether a given s-element violates a given basis B.

tbDS be the time needed for constructing a basis for a given d-element and sets D, S of constant size.

tvD is constant by checking whether the conditions stated in Lemma 9.1.5 are satisﬁed. tvS is constant by checking whether the conditions stated in Lemma 9.1.7 and Lemma 9.1.9 are satisﬁed. tbDS is constant by trying all possible choices of a D ⊆ D, |D | ≤ p + 1 and S ⊆ S, |S | ≤ p and checking whether (D, S ) meets all the conditions as stated in the deﬁnition of a basis (Deﬁnition 3.3.5).

We conclude with Theorem 9.1.15 The discrete p-center problem on the line can be solved in randomized linear time.

We note that all our results remain valid when we omit the general position assumption, by using the “lexicographic” deﬁnition d(x, y) = (|x − y|, min{x, y}).

9.2 p-center problems on circles In this kind of p-center problems the space is a circle (1-dimensional sphere) and the metric is such that the length between two points is the length of the shorter arc between them. We emphasis that the relative order of the points on the circle is not given a-priori.

9.2.1 Continuous case ** Lemma 9.2.**

1 The Helly number of the Helly theorem corresponding to the (continuous) p-center problem on circles is unbounded.

Proof: It is enough to construct for every constant k an instance (H, ω) of the p-center problem on circles such that for every H ⊂ H with |H | ≤ (2k + 1)p, we have ω(H ) ≤ k but ω(H) = k + 1. We achieve this by letting H = {0, 1, 2, 3,..., (2k + 1)p} and making the circle be of perimeter (2k + 1)p + 1.

To conclude this subsection we provide a lower bound of Ω(n log n) for the (continuous) 1-center problem on circles. We will make a reduction from the following problem Problem: Maximum Gap Given n real numbers x1,..., xn, ﬁnd the maximum diﬀerence between two consecutive numbers. (Two numbers xi and xj are said to be consecutive if xi ≤ xj and there exists no other number xk, s.t. xi xk xj.) ** Lemma 9.2.**

2 ([LW86]) The Maximum Gap problem requires Ω(n log n) time under the algebraic computation tree model.

** Lemma 9.2.**

3 The (continuous) 1-center problem on circles requires Ω(n log n) time under the algebraic computation tree model.

Proof: We show that the Maximum Gap problem can be reduced to the 1-center problem on circles in O(n) time. Given an instance H of the Max Gap problem, we ﬁrst ﬁnd minH and maxH in linear time.

We then deﬁne an instance for the 1-center problem on circles H = {h − minH | h ∈ H} on a circle of perimeter maxH − minH. It is obvious that the maximum gap between two consecutive points in H is maxH − minH −2r1 (H ) where r1 (H ) is the radius of the 1-center problem on H. Therefore the (continuous) 1-center problem on circles also requires Ω(n log n) time.

9.2.2 Discrete case ** Lemma 9.2.**

4 The d-Helly number of the Helly theorem corresponding to the discrete p-center problem on circles is unbounded.

Proof: We use the same construction as in the proof of Lemma 9.2.1 and deﬁne D = S = H. Let D be an arbitrary subset of D such that |D | = (2k + 1)p. It is easy to see that ω(D, S) = k + 1 while ω(D, S) = k.

We conclude this subsection by giving a lower bound of Ω(n log n) for the discrete 2-center problem on circles. We will make a reduction from Set Equality problem (see deﬁnition and lower bound in Section 7.3.1).

** Lemma 9.2.**

5 The discrete 2-center problem on circles requires Ω(n log n) time under the algebraic computation tree model.

Proof: We show that Set Equality can be reduced to the discrete 2-center problem on circles in O(n) time. Given an instance A, B of the Set Equality problem, we ﬁrst ﬁnd minA and minB in linear time. If minA = minB we stop and output A = B. Otherwise we transform every a ∈ A and b ∈ B into two points on the unit circle in the plane as follows. We transform every a ∈ A into the two intersection points between the unit circle and the line y = (a − minA )x. We transform every b ∈ B into the two intersection points between the unit circle and the line resulted by rotating the line y = (b − minA )x by π radians relatively to the origin. Considering the unit circle as a circle of perimeter 2π, it is easy to see that A = B if and only if the radius of the discrete 2-center problem is π. (If there exists a ∈ A such that a ∈ B, choosing its image / on the unit circle to be the two centers will yield a smaller radius). Therefore the discrete 2-center problem on circles also requires Ω(n log n) time.

9.3 p-center problems with l∞ norm We will mainly concentrate on the planer case where the continuous (discrete) problem is to ﬁnd p congruent squares with edges parallel to the axis (with centers from S), of the smallest radius covering H (D), respectively.

9.3.1 Continuous case The weighted 1-center problem in I d has a linear time solution as it can be formulated as a linear programR ming problem (see [FW74]).

[Dr87] solves in linear time the planar 2-center problem. The weighted 2-center problem has a linear time solution due to [KC92]. Sharir and Welzl ([SW96]) solve in randomized linear time the planar 2-center (3-center) problem by formulating it as a 13-dimensional (43-dimensional) LP-type problem, respectively.

For both problems [SW96] deﬁne explicitly a lexicographic objective function which satisﬁes the Unique Minimum Condition.

The Helly theorem corresponding to the continuous p-center problems with l∞ norm is just Theorem 2.1.2.

We conclude by stating the lower bounds given by Sharir and Welzl ** Lemma 9.3.**

1 ([SW96]) The continuous planar p-center problem with l∞ norm requires Ω(n log n) time under the algebraic computation tree model, for any p 3.

9.3.2 Lexicographic planar case In the lexicographic weighted p-center problem (p-lcenter problem, in short) we are given the same input, and r wish to ﬁnd the lsmallest vector (r, x1, y1,..., xp, yp ) such that the set of all squares { wi hi | i = 1,..., n} with center in H and radius r multiplied by the corresponding weight is ((x1, y1 ), (x2, y2 ),..., (xp, yp ))-p-pierceable.

We call r the radius and (x1, y1,..., xp, yp ) the centers vector. (See Subsection 2.3.2 for deﬁnitions related to p-pierceability.) In this subsection we solve the planar lexicographic weighted p-center problem for p = 1, 2, 3 in randomized linear time by using either

• Theorem 2.1.2, its corresponding lexicographic version Theorem 2.3.4, and Theorem 5.3.6, or

• Theorem 2.1.2 applied on open rectangles, its corresponding lexicographic version Theorem 2.3.4, and Theorem 5.3.7.

Considering the ﬁrst approach, we start by deﬁning the parameterized Helly system corresponding to our problem. Let the ground set of all possible p-centers be

is the set of all points in Xp such that the i-th center is at weighted distance at most λ from h. From the construction we obtain Observation 9.3.2 The solution of the weighted planar p-center problem with l∞ norm on a set of points H = {h1,..., hn } and a corresponding set of weights {ω1,..., ωn } is at most r if and only if there is a common point to all the sets hpr, h ∈ H.

¯ (Hp, ω) is an LP-type problem of combinatorial dimension 2 (6, 34) for p = 1 (p = 2, 3), respectively. In this way the second approach yields LP-type formulations with smaller combinatorial dimension than the ﬁrst approach. These formulations have also smaller combinatorial dimension than the formulation of [SW96] (6 instead of 13 for the case p = 2, and 34 instead of 43 for the case p = 3).

** Theorem 9.3.**

3 The lexicographic weighted planar p-center problem with l∞ norm is solvable in randomized linear time, for p = 1, 2, 3.

Proof: Until now we have shown that the lexicographic planar p-center problem with l∞ norm is an LP-type problem of dimension at most 2 (6, 34) for p = 1 (p = 2, 3), respectively. We solve this problem by using the LP-type randomized algorithms, such as the one of Sharir and Welzl (see Section 6.2). In order to obtain a linear running time it remains to show how to implement the violation test and basis calculation primitives such that they run in constant time. We slightly change the structure of these two primitives: We implement the basis calculation primitives such that when called with input (B, h) it returns in addition to a basis B(B ∪ {h}) for B ∪ {h}, also the value ω(B ∪ {h}), of the objective function on B ∪ {h}, and the point x(B ∪ {h}) which realizes this value (there is only such point since the objective function is lexicographic).

The input for the violation tests consists of x(B) in addition to B (i.e., we call Violation(B, h, x(B))). The ¯ ¯ violation test primitive checks whether x(B) ∈ hp (h). This is done in constant time since hp (h) is of constant complexity. We implement the basis calculation primitive Basis(B, h) in constant time as follows. For any proper subset B ⊂ B ∪ {h} we calculate explicitly ω(B ) and the point x(B ) realizing this value. Then for every h ∈ B ∪ {h} \ B we call Violation(B, h, x(B )). B is a basis for B ∪ {h} if and only if all these calls return “false”.

We note that since the optimal solution for the lexicographic planar p-center problem is an optimal solution for the non-lexicographic problem, we get an alternative solution to the one of [SW96]. We summarize in Corollary 9.3.4 The planar p-center problem with l∞ norm is solvable in randomized linear time, for p = 1, 2, 3.

with x ≤L x if and only if ω(D, S ) ≤L x. 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 | ≤ 2d.

If D is inﬁnite (then S must be ﬁnite), we replace each box h ∈ D, by the smallest possible compact box C(h) which is contained in h and contains the same points in S as does h. Since the set S is ﬁnite, we get that the resulted set of boxes C(D) = {C(h) | h ∈ D} is also ﬁnite, and for every D ⊆ D and S ⊆ S, ω(D, S ) = ω(C(D ), S ).

If the intersection of the boxes in D is empty, by Theorem 2.1.2(i) there are two boxes which do not intersect. We let D to consist of these two boxes.

Otherwise, for each coordinate i = 1,..., d, we act as follows. Let Li (D ) ∈ D be a box whose projection on the i’th coordinate is an interval [li, ri ] with the smallest ri (if D is inﬁnite, such a box does not necessarily exist. In this case we take instead a box h ∈ D such that C(h) ∈ C(D ) is a box whose projection on the i’th coordinate is an interval [li, ri ] with the smallest ri. Such a box C(h) exists since C(D ) is a ﬁnite set).

We let Gi (D) ∈ D be a box whose projection on the i’th coordinate is an interval [li, ri ] with the greatest li (if D is inﬁnite and no such box exists, we proceed similarly to what we did in the deﬁnition of Li (D )).

We let D = {L1 (D ), G1 (D ),..., Ld (D ), Gd (D )}. We note that D ∩ S = D ∩ S (and when D is ﬁnite, D = D ).

In both cases, (D, S ) is a solution deﬁning set for (D, S ) and the cardinality of D is at most 2d, as needed.

This Helly number is at least 2d due to Example 2.2.2.

We note that Theorem 2.4.1 implies Theorem 2.2.1 in the following way. Due to Observation 2.4.8 the Helly number in Theorem 2.2.1 is bounded from above by 2d, the Helly number in Theorem 2.4.1. Due to ** Example 2.2.**

2 it is at least 2d, so it is 2d.

In order to avoid conﬂict in our notations, let B denote the set of boxes, let P denote the set of points for** Theorem 2.4.**

1, let D denote the set of demand points, and let S denote the set of supply points for the 1-center problem. For every (D, S ) ∈ 2D ×2S let r(D, S ) be the optimal radius for the 1-center problem on (D, S ), realized by making s∗ (D, S ) ∈ S a center. Looking at the set of boxes r(D, S )D = {r(D, S )di | di ∈ D } where r(D, S )di is the box with center at di and radius r(D i ), we note that s∗ (D, S ) intersects all the,S w boxes of r(D, S )D. Applying Theorem 2.4.1 on B = r(D, S )D and P = S, we take a solution deﬁning

**set as determined in the proof of Theorem 2.4.1 above, and deﬁne the following variables:**

We also deﬁne C(D, S ) ∈ S to be the optimal center. We let the range of the objective function be I + × I 2(d+1) and deﬁne the objective function to be R R ω(D, S ) = (r(D, S ), C(D, S ), l1 (D, S ), −g1 (D, S ),..., ld (D, S ), −gd (D, S )).

Clearly (D, S, ω) is a discrete abstract problem.

For every (D, S ) ∈ 2D × 2S we let F easible(D, S ) denote the set of all intersection points for the boxes r(D, S )D. From the deﬁnitions of the variables and the optimality of the solution we get Observation 9.3.5 Let D, S, W be an instance of the general discrete weighted 1-center problem in I d with R l∞ norm. For every (D, S ) ∈ 2D × 2S, F easible(D, S ) is the minimal axis-parallel box containing the 2 points (g1 (D, S ),..., gd (D, S )) and (l1 (D, S ),..., ld (D, S )), and C(D, S ) lies on its boundary.

We show now that (D, S, ω) is a (2d, 1)-dimensional DLP-type problem. (D, S, ω) obeys the Monotonicity of Demand Condition since adding a new box h to D cannot lexicographically decrease the value, i.e.

ω(D, S) ≤L ω(D ∪ {h}, S). Similarly, (D, S, ω) obeys the Monotonicity of Supply Condition since adding a new point h cannot lexicographically increase the objective function value.