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

where rbtp (VG ) is deﬁned in (8.7) and rbtp−1 (G) is deﬁned in (8.1).

We formulate the p-Recovery Points problem on the real line as a p-dimensional dual LP-type problem as follows. Let Λ = I p ∪ {−∞, ∞} and let 2H denote the set of all induced subtrees of H. We deﬁne an R abstract problem (H, τp ) with a lexicographic objective function τp : 2H →Λ whose ﬁrst p − 1 coordinates consist of the objective function ωp−1 deﬁned in (8.3), and the last coordinate is the only leaf in H

** Theorem 8.3.**

1 The p-Recovery Points problem on the real line is a p-dimensional dual LP-type problem.

Proof: Let us consider the lexicographic function τp as deﬁned in (8.10). Due to (8.9) its ﬁrst coordinate is the roll-back time of the p-Recovery Points problem on the Real Line. Hence it is suﬃcient to show that the abstract problem (H, τp ) is a p-dimensional dual LP-type problem.

We conclude the proof by noting that the abstract problem (VH, − max VH ) is a 1-dimensional dual LPtype problem, and that due to Theorem 8.2.7 the abstract problem (H, ωp−1 ) is a (p − 1)-dimensional dual LP-type problem.

We could have solved (H, τp ) by applying Theorem 8.2.8 on the path tree H deﬁned above. There is one problem with this approach. Since the real points in the given set VH are not sorted a-priori, it takes O(n log n) time to calculate (preprocess) the corresponding set of edges EH. Thus in this approach the preprocessing phase takes O(n log n) time, and the second phase of placing p-Recovery Points on the (path) tree H takes additional linear time, making this approach run in O(n log n) time.

In order to obtain a linear time solution, we give below speciﬁc linear time implementations for the various functions and algorithms that we deﬁned in Section 8.2 for trees.

For every i we implement the distance to the root function drH, by setting drH (hi ) = hi − h1. For every i, j we implement the nearest common ancestor function ncaH, by setting ncaH (hi, hj ) = min{hi, hj }, and implement the distance function dH, by setting hi − hj if hi hj or h1 = hj = h1 dH (hi, hj ) = ∞ otherwise.

The general position assumption of the tree case that the ﬁnite lengths of the directed paths between pairs of vertices are all distinct, is equivalent in the real line case to assuming that no two distinct pairs of points in VH have the same distance. We note that all our results remain valid when we omit this general position assumption, by replacing the distance function dH with the lexicographic distance function d (x, y) = (dH (x, y), min{x, y}).

Let G = (VG, EG ) be an induced subtree of the path tree H. Let us consider an optimal solution, Op−1 (G), for (8.1) on G (which equals (8.7) on VG ). If there is more than one optimal solution with the same roll-back time, we take the one which is realized as follows. Due to the general position assumption, the big paths in all of the optimal solutions are identical and equal [hjl, hjh ]. Let nh be the number of recovery points on the path [hjh, h1 ], which are diﬀerent from hjh. Let nl be the number of recovery points on the path [h2, hjl ], which are diﬀerent from hjl and h2. Clearly nh + nl + 3 ≤ p.

We are now ready to deﬁne a distribution algorithm, that assigns correctly values to the state variables Ci (G), Di (G), i = 0,..., p. Intuitively, the algorithm “pushes” the recovery points as much as possible towards the middle of the big path. We let C1 (G) = h1 and D1 (G) = 0. For i = 2,..., nh we recursively deﬁne Ci (G) = max{v ∈ VG | v ≤ Ci−1 (G) + rbtp (G)} and Di (G) = rbtp (VG ) − (Ci (G) − Ci−1 (G)).

We let Cnh +1 (G) = hjh and Dnh +1 (G) = rbtp (VG ) − (Cnh +1 (G) − Cnh (G)). We let Cnh +2 (G) = hjl.

We let Cnh +3 (G) = min{v ∈ VG | v ≥ h2 − rbtp (VG )} and Dnh +3 (G) = rbtp (VG ) − (h2 − Cnh +3 (G)).

For i = 1,..., nl − 1 we recursively deﬁne Cnh +3+i (G) = min{v ∈ VG | v ≥ Cnh +2+i (G) − rbtp (VG )} and Dnh +3+i (G) = rbtp (VG )− (Cnh +3+i (G)− Cnh +2+i (G)). Let P = nh + nl + 3 be a variable holding the number of currently used recovery points (so CP −1 (G) is the recovery point closest to hjl from the right side). If P p we say that there are free recovery points. Last, we let Dnh +2 (G) = rbtp (VG )−(CP −1 (G)−Cnh +2 (G)).

If P p we set for every P i ≤ p, Ci (G) =“undeﬁned” and Di (G) = −∞ (see Figure 8.2).

** Figure 8.2: 9 recovery points and their corresponding “C” state variables.**

Here nh = nl = 3.

Observation 8.3.2 The algorithm stated above, applied on input VG, hjh, hjl, rbtp (VG ), p, runs in O(pn) time and assigns to the state variables the same values as Procedure Main Distribute(G, hjh, hjl, rbtp−1 (G), p−

1) assigns.

It remains to show how to apply the randomized algorithm of [SW92] in order to solve this problem in linear time. We need to start with an initial basis (candidate basis) B0, for H as we do in Function Main Recovery below. This function returns a basis for H for the Recovery Points problem on H, and uses Function lptype from the algorithm of [SW92] (see Section 6.2).

Function Main Recovery(H, p) begin calculate h1 and h2, the minimal and maximal elements in VH choose a subset VH ⊆ VH with h1, h2 ∈ VH and |VH | = p at random calculate the roll-back time of VH by ﬁnding the maximal distance between consecutive points in VH ﬁnd the two points hjh, hjl between which the big interval lies compute the state variables by executing the distribution algorithm presented above let B0 be the set consisting of the recovery points of VH return lptype(H, B0 ) end Recovery

.p current number of cuts on the xi axis.

.index always equals to i.

.length maximum length in axis xi after performing optimal.p guillotine cuts.

.worse maximum length in axis xi after performing optimal (.p − 1) guillotine cuts.

**We also deﬁne the following two trees, sorted by two diﬀerent keys:**

LEN GT HT REE contains A[1],A[2],...,A[d] sorted by decreasing.length order (such that the root has the biggest length value). (The key of this tree is.length).

W ORSET REE contains A[1],A[2],...,A[d] sorted by increasing.worse order (such that the root has the smallest worse value). (The key of this tree is.worse).

**We use the following three procedures on these two trees:**

Root(t) returns the value of the key of the root of the tree t.

Insert(rec, t) inserts the record rec into the tree t while keeping the order of the tree.

Update(rec, t) deletes the root of the tree t and the performs Insert(rec, t).

We note that Function Root(t) can be implemented in constant time while Function Insert(rec, t) and Function Update(rec, t) can be implemented in O(log d) time ([CLR90]). We solve the p-Guillotine Cuts

**problem by the following function:**

8.4 Placing recovery points on circles In the p-Recovery Points problem on circles we are given a ﬁnite family H of points on a circle of perimeter l. We wish to ﬁnd a subset H ⊆ H of p points that realizes the minimum of the largest interval length, resulted by cutting the circle at the points of H. We emphasis that the given points are not sorted, so constructing a circular graph from the input points requires Ω(n log n) time. We prove that solving the 2-Recovery Points problem on circles requires Ω(n log n) operations under the algebraic computation tree model (i.e., prove Theorem 5.1.7). We ﬁrst deﬁne the following two problems

and Problem: l-distance Input: A ﬁnite family H of reals such that maxH − minH = 2l.

Output: “true” if and only if there are two points h1, h2 ∈ H (not necessarily adjacent), which are at distance l apart.

We will also use Theorem 8.4.1 (Ben-Or [Be83]) Any algebraic decision tree algorithm that solves the Membership in P ⊂ I n problem must have depth of at least log #(P ), where #(P ) is the number of disjoint connected components R of P.

Proof: (of Theorem 5.1.7) Let us consider an instance H = {h1,..., hn } of the l-distance problem as a single point (h1,..., hn ) ∈ I n. Let P be the set of points in I n for which the answer for the problem is “false”.

R R Every two points hi, hj divide I n into the three disconnected open subspaces xi xj + l, |xi − xj | l and R xj xi + l by the two hyperplanes xi = xj + l and xj = xi + l (xi and xj are the i’th and j’th coordinates in I n, respectively). In this way P is composed out of 3n disconnected regions. By Theorem 8.4.1 the decision R tree algorithm which solves the Membership in P problem is of depth Ω(log(3n )) = Ω(n log n), so under the algebraic computation tree model, it takes Ω(n log n) comparisons to solve the l-distance problem.

We conclude our proof by reducing the l-Distance problem to Placing 2-Recovery Points on Circles.

Having an instance H of the l-distance problem, we “connect” min H to max H and result a circle of perimeter 2l. This is done in constant time. We then solve the 2-Recovery Points problem on Circles. The answer for the l-distance problem is “true” if and only if the answer for the 2-Recovery problem is “true”.

Remark: It is possible to solve the p-Recovery Points problem on circles in O(n log n) time by ﬁrst sorting the points in O(n log n) time and then applying the ideas of Frederickson and Johnson [FJ83].

Chapter 9 p-center problems

We note that the discrete abstract problem (D, S, rp ) is a p-supply problem (see Deﬁnition 3.3.17). As before, in the general discrete non-weighted p-center problem (the general discrete p-center problem, in short) all the weights equal 1.

The discrete weighted (non-weighted) p-center problem is a special case where S = D. We note that the radius of the continuous weighted (non-weighted) p-center on a given set H is not greater than the one of the discrete weighted (non-weighted) p-center on H, respectively.

9.1 p-center problems on the line In the p-center problem on the line the space is I and the distance function is ∀x, y ∈ I d(x, y) = |x − y|.

R R, For both discrete and continuous 1-center problems and for the continuous 2-center problem there are trivial O(n) time algorithms [Han73]. If the order of the demand points in D is given a-priori, the continuous pcenter problem can be solved in linear time by the fairly involved technique of Frederickson [Fr91]. Otherwise (the order of the points in D is not given), this problem can be formulated as a ﬁxed-dimensional LP-type problem, P1, by using Theorem 2.1.2(ii) and by deﬁning explicitly a lexicographic objective function. We note that by formulating the lexicographic Helly theorem, Theorem 2.3.4(ii), as a Helly system with a ﬁnite lexicographic Helly number, and using either Theorem 5.3.6 or Theorem 5.3.7, we can formulate the p-center problem as a ﬁxed-dimensional LP-type problem, P2. In this way, any of the resulted problems P1, P2 is solvable in randomized linear time, for any ﬁxed p, by using the various LP-type algorithms.

In the following subsections we formulate the general discrete p-center problem on the line as a ﬁxeddimensional discrete LP-type problem and solve it in randomized linear time (for any ﬁxed p 1). We are unaware of any other linear time solutions for this problem, even for the case p = 2. It is hard to see how we can use our linear time solution for the Recovery Points problem on the real line (Section 8.3), in order to solve the general discrete p-center problem on the line (even if we restrict two of the centers to be minS, maxS and let D = S).

Whenever it is clear from the context (i.e., when the input is two sets D, S), we will call the problem of calculating (9.2) discrete p-center.

9.1.1 A formulation as a discrete abstract problem (D, S, ω) Let D = {d1,..., dn } be a set of n demand points and S = {s1,..., sm } be a set of m supply points. To simplify the discussion, we assume general position of the points - all distances between demand points and supply points are distinct. Later on we will show how to remove this supposition. Let D ⊆ D and S ⊆ S be arbitrary non-empty sets and let G = (D, S ). Without loss of generality we assume that the optimal radius r = rp (D, S ) = d(d1, s1 ) is the distance between d1 and s1. If di ∈ D is at distance at most r from sj ∈ S we say that sj covers di since an interval of length 2r centered at sj covers di. Let c = d1 +s1 be the middle point between s1 to d1.

Let us consider an optimal solution for the discrete p-center problem on G with radius r = rp (G)1.

We deﬁne for it an optimal solution, not necessarily identical, which minimizes additional parameters as 1 In doing so we slightly abuse our notation since rp (G) = rp ((D, S )) while we refer to it as rp (D, S ) explained below. We start by deﬁning the following state variables. C(G) = {C1 (G), C2 (G),...Cp (G)} is a set consisting of the at most p centers from S. For each Ci (G) ∈ S we deﬁne a corresponding state variable, Di (G) ∈ D which contains the farthest demand point which is served by Ci (G) and lies on the side of Ci (G) which doesn’t contain c (i.e., Ci (G) lies in the interval connecting between c and Di (G)). We also deﬁne the auxiliary variables C 1 (G),..., C p (G), D0 (G), D1 (G),..., Dp (G). The state and auxiliary variables are given values as follows. Due to the general position assumption, the radius r is realized uniquely by d1 and s1. Let nl be the number of centers to the left of (smaller than) s1 and nr be the number of centers to the right of (greater than) s1. Clearly nl + nr + 1 ≤ p. We let C1 (G) = s1, D0 (G) = d1. If nl ≥ 1 we let D2 (G) = min{h ∈ D }. For i = 2,..., nl, we recursively deﬁne Ci (G) = max{h ∈ S | h ≤ Di−1 (G) + r} and Di+1 (G) = min{h ∈ D | h Ci (G) + r}. We deﬁne Cnl +1 (G) = max{h ∈ S | h ≤ Dnl (G) + r}.

We let Dnl +2 (G) = max{h ∈ D }. For i = 1,..., nr, we recursively deﬁne Cnl +1+i (G) = min{h ∈ S | h ≥ Dnl +1+i (G) − r} and Dnl +2+i (G) = max{h ∈ D | h Cnl +1+i (G) − r}. We let P = nh + nl + 1 be a variable holding the number of center points in Op (G) (so CP (G) is the center closest to s1 which is bigger than s1 ).