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

A special case of Problem 10.2.1 is when the line transversal must be non-descending Problem 10.2.2 Given are a set D = {d1,..., dn } of (non 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 non-descending line transversal whose direction is in S.

R 1 The solution of Problem 10.2.1 is the minimum scaling factor between the solution of Problem 10.2.2 and the analogue problem where the line transversal must be non-ascending.

10.2.1 A formulation as a discrete LP-type problem In this subsection we formulate Problem 10.2.2 as a ﬁxed-dimensional discrete LP-type problem by using** Theorem 2.4.**

4 and Theorem 5.3.6.

Let G = (D, S ) ∈ 2D × 2S be an arbitrary set such that G = (∅, ∅). We ﬁrst look closely at an optimal solution for Problem 10.2.2 on G. Let λ∗ be the optimal scaling factor. Due to Theorem 2.2.9 there is a direction s∗ ∈ S and a set D ⊆ D of at most 4 rectangles such that the solution of Problem 10.2.2 on (D, {s∗ }) is λ∗.

**For this solution we deﬁne the following variables:**

• SLmin(D, S ) is the slope of the line transversal for λ∗ D with a minimal non-negative slope.

• SLmax (D, S ) is the slope of the line transversal for λ∗ D with a maximal non-negative slope.

(Due to the optimality of the scaling factor, the slope range does not contain any direction from S in its interior.) We are ready to deﬁne a lexicographic version for Problem 10.2.2 Problem 10.2.3 Given are a set D = {d1,..., dn } of (not necessarily pairwise disjoint) axis-parallel rectangles, and a set S = {s1,..., sm } of allowed line directions. Find the lexicographically minimal vector λ = (λ1, s, b, slmin, −slmax ), such that the line y = sx + b (s ∈ S) is non-descending, intersects all the rectangles in λ1 D, and the slope range corresponding to λ1 D is [slmin, slmax ].

Proof: We need to show that ∀ α, β ∈ Λ with α β, hα ⊆ hβ, i.e., for all x ∈ hα, x is also in hβ. This is true by monotonicity: a line transversal for αh with a slope in a speciﬁc slope range is also a line transversal for βh with a slope in the same range.

For every h ∈ S and λ ∈ Λ we let

We show now that actually the d-dimension is only 4. Due to Corollary A.3.1 each of the two endpoints of the slope range corresponding to λ∗ D, SLmin(G) and SLmax (G), are deﬁned by at most two rectangles (a deﬁning pair). BD must contain such two deﬁning pairs. Since DIR(G) is one of the boundary points of the slope range, any two such deﬁning pairs also deﬁne λ1 (G), DIR(G) and b(G). In this way BD consists only of two such deﬁning pairs, i.e., of at most 4 rectangles, and BS = DIR(D, S ).

Before we continue, we explain the values the decision and optimization problems return. The decision problem returns “yes” if and only if λ∗ = λ1 (D, S) ≤ 1. The optimization problem returns the minimal scaling factor λ1 (D, S), the minimal non-negative direction from S such that λ1 (D, S) admits a line transversal with direction DIR(D, S) and intersection point b(D, S) with the y axis, the slope range deﬁned by SLmin(D, S), SLmax (D, S), and a basis B = (BD, BS ) for (D, S). We note that there exist line transversals for λ∗ D with each of the slopes SLmin(D, S) and SLmax (D, S). We can view B and LIN E(D, S) as witnesses for the optimality of the scaling factor λ1 (D, S). We only need to check that λ1 (BD, S) = λ∗ (the Monotonicity of Demand Condition implies λ∗ (D, S) ≥ λ∗ ) and that the line transversal LIN E(D, S) intersects each one of the rectangles λ∗ h, h ∈ D (the Monotonicity of Supply Condition implies λ∗ (D, S) ≤ λ∗ ).

The ﬁrst test can be executed in |S| time and the second in |D| time.

10.2.2 A linear time algorithm In this subsection we apply the linear time algorithm stated in Section 6.3.3. We need to show that the conditions of Theorem 6.3.6 are satisﬁed, and implement each of the violation test and basis calculation primitives in constant time. In the last subsection we formulated Problem 10.2.2 as a (4, 1)-dimensional discrete LP-type problem. In order to show that the algorithm stated in Section 6.3.3 is correct it remains to show Lemma 10.2.5 (D, S, ν) meets the Violation Condition (Deﬁnition 3.3.15).

Proof: We need to show that for every (D, S ) ∈ 2D × 2S and (D, S ) ∈ 2D × 2S with ν(D, S ) =

**ν(D, S ) the following properties hold:**

1. For every h ∈ D, if ν(D ∪ {h}, S ) ν(D, S ) then ν(D ∪ {h}, S ) ν(D, S )

2. For every h ∈ S, if ν(D, S ∪ {h}) ν(D, S ) then ν(D, S ∪ {h}) ν(D, S ).

Let λ1 = λ1 (D, S ) = λ1 (D, S ). We deﬁne the following functions related to P (λ1 D ), the set of line transversal which λ1 D admits (see Corollary A.3.1 for the deﬁnition and structure of P (λ1 D ) in the dual space of line transversal). Let lmin (D, S ) be the only line transversal with direction SLmin(D, S ) that λ1 (D, S )D admits. Let bmin(D, S ) be its intersection point with the y-axis. In this way (SLmin(D, S ), bmin (D, S )) is the leftmost point in P (λ1 D ). We deﬁne lmax (D, S ) and bmax (D, S ) similarly, so (SLmax (D, S ), bmax (D, S )) is the rightmost point in P (λ1 D ).

The proof of both properties relies on the following observation which is true due to (10.2).

the functions SLmin, bmin, lmin, SLmax, bmax and lmin ν(D, S ) = ν(D, S )→ (10.3) have the same values on (D, S ) and on (D, S ).

We ﬁrst show that the ﬁrst property holds. h ∈ D violates (D, S ) if and only if the set of line transversals which λ1 h admits does not contain both lines lmin (λ1 D, S ) and lmax (D, S ) (i.e., {(SLmin(D, S ), bmin (D, S ));

(SLmax (D, S ), bmax (D, S ))} ⊂ P (λ1 h)). Using (10.3), the latter condition occurs if and only if the set / of line transversals which λ1 h admits does not contain both lines lmin (λ1 D, S ) and lmax (D, S ), which in its turn occurs if and only if h ∈ D violates (D, S ).

Regarding the second property, we observe that h ∈ S violates (D, S ) if and only if either the slope h lies in the interior of the slope range corresponding to λ1 D (so the scaling factor decreases), or h is the left endpoint of the slope range with h DIR(D, S ). We conclude the proof by using (10.3) again.

We are ready to make the complexity calculations. Given a basis B = (BD, BS ) and its optimal scaling factor λ1, we compute in constant time the functions SLmin (B), bmin (B), lmin (B), SLmax (B), bmax (B), lmin (B), DIR(B) and the set of all line transversals for λ1 B, P (λ1 BD ) = ∩h∈BD D(λ1 h) (see Corollary A.3.1 for the notations).

The following violation tests are implemented in constant time as follows tvS : A new s-element h violates B if and only if either h lies in the interior of the slope domain (SLmin (B), SLmax (B)), or h = SLmin(B) and DIR(B) = SLmax (B).

tvD : A new d-element h violates B if and only if D(λ1 h) does not contain {(SLmin(D, S ), bmin (D, S ));

(SLmax (D, S ), bmax (D, S ))}.

the basis calculation for (D, S ) where both |D |, |S | are constants can be implemented in constant time as follows. For every h ∈ S calculate the minimal scaling factor λ1 (D, {h}) (this can be done by projecting the rectangles in D on a line perpendicular to direction h as explained in the beginning of Section 10.2 for h being the vertical direction). Let the s-element part of a basis BS, be the set consisting of the minimal h ∈ S resulting the minimal such λ1 (D, {h}). In order to deﬁne a d-element part of a basis BD, calculate P (λ1 D ) = ∩h∈D D(λ1 h) and let BD consists of two pairs that deﬁne the leftmost and rightmost point in P (λ1 D ). Due to Corollary A.3.1, (BD, BS ) is a basis for (D, S ). We have proved Theorem 10.2.6 Problem 10.2.1 is solvable in (randomized) linear time.

10.3 Discrete case II - A ﬁnite number of allowed line transversals We now deﬁne another discrete version for the line transversal of axis-parallel rectangles optimization problem.

<

The corresponding decision problem is Problem 10.3.2 Given are a set D of axis-parallel rectangles and a set S of lines. Decide whether D admits a line transversal from S.

A corollary of Theorem 2.2.12 is that the Helly number corresponding to the above problem is unbounded.

We show here Theorem 10.3.3 Problem 10.3.2 requires Ω(n log n) time under the algebraic computation tree model (when m = n).

Proof: We reduce in linear time the set equality problem to Problem 10.3.2. Given an instance of the set equality problem, i.e., two sets A, B of n real numbers each, we act as follows. We ﬁnd minA and maxA (minB and maxB ), the minimal and maximal elements in A (B), respectively. We deﬁne two new sets A = { maxA − min)A − 1 | a ∈ A} and B = { maxB − minB − 1 | b ∈ B}. All the elements in A and B are 2(a−minA 2(b−minB ) numbers between -1 to 1 and A = B if and only if A = B. For any −1 ≤ r ≤ 1 let p(r) be the intersection point of the unit circle and the ray originating at the origin and having an angle of r radians with the positive part of the x-axis. We deﬁne two instances for Problem 10.3.2. The ﬁrst instance, Instance I, has a set of lines SI = S(A ) and a set of rectangles (intervals) DI = D(B ) deﬁned as follows. We let S(A ) = {s(a ) | a ∈ A } where s(a ) is the line tangent to the unit circle at point p(a ). We let D(B ) = {i(b ) | b ∈ B } where i(b ) is an horizontal interval of length 100, whose left end is slightly to the right of p(b ) (from a computation point of view we build the left end of the interval at exactly p(b) but symbolically do not include this point in the interval). The resulting construction looks similar to Figure 2.4 rotated by 1 π radians clockwise. From the above construction we get that D(B ) admits a line transversal from S(A ) if and only if A ⊂ B. The second / instance, Instance II, has the set of lines SII = S(B ) and the set of rectangles DII = D(A ). we get that D(A ) admits a line transversal from S(B ) if and only if B ⊂ A. We conclude the proof by observing that / A = B if and only if both instances of Problem 10.3.2 return negative responses.

Chapter 11 The simple stochastic game We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl [SW92] for LP-type problems, we obtain the ﬁrst strongly subexponential solution for SSG’s (a strongly subexponential algorithm has only been known for binary SSG’s [Lu95]). Using known reductions between various games, we achieve the ﬁrst subexponential solution for Discounted Payoﬀ Games. Our solution is in fact strongly subexponential. We also give alternate simple proofs for the best known upper bounds for Parity Games, Mean Payoﬀ Games and binary SSG’s.

11.1 Introduction In this chapter we use the LP-type framework in order to give the ﬁrst strongly subexponential solution for Simple Stochastic Games (deﬁned below). To the best of our knowledge, this is the ﬁrst application of the LP-type framework for solving a problem which is neither in computational geometry nor in location theory.

Moreover, it is the ﬁrst application of variable-dimensional LP-type problems.

A Simple Stochastic Game (SSG) is deﬁned on a directed graph with three types of vertices, min, max, and average, along with two sink vertices, the 0-sink and the 1-sink. The sink vertices have no outgoing edges. For every average vertex ak, the outgoing edges from ak have positive rational weights such that the sum of their weights is 1. The outgoing edges from the min and max vertices are unweighed. One of the vertices is a start vertex.

The game is a contest between two players, 0 and 1. It is played in the following way. Begin by placing a token on the start vertex. When the token is on a min vertex yj, player 0 moves it along one of the outgoing edges of yj. When the token is on a max vertex xi, player 1 moves it along one of the outgoing edges of xi.

When the token is on an average vertex ak, the edge along which the token is moved is determined randomly, in proportion to the weights of the edges outgoing from ak. The game ends when one of the sink vertices is reached. The goal of player 1 is to reach the 1-sink. The goal of player 0 is to avoid the 1-sink.

Before the game begins, player 1 chooses an outgoing edge from each max vertex. These selected edges will deﬁne a strategy for player 1. During the game, whenever the token is on a max vertex, player 1 will move the token along the edge that is included in his strategy. (Deﬁning strategies deterministically in this way does not result any loss of generality [Co92]). Similarly, a choice of an outgoing edge for each min vertex is a strategy for player 0. Given a SSG, we would like to ﬁnd the best strategies for both players. The corresponding decision problem is to determine whether player 1 wins with probability greater than 2 when both players use their “best strategies”.

A binary SSG is a special case of a SSG, where the outgoing degrees of the min and max edges are bounded by 2, and where all average vertices have exactly two outgoing edges of weight 2 each. Zwick and Paterson [ZP96] gave a simple polynomial reduction from a SSG with n vertices and nn edges, in which the denominators of all the (rational) probabilities are at most l, to a binary SSG with n = O((n + nn) log l) vertices and nn = O(nn log l) edges. We note that nn may be quadratic in n, so the number of vertices in the binary game resulted by the reduction,√, may be Θ(n2 ). In this case, the running time of the best n known algorithm for binary SSG’s (which is e n time) becomes exponential in n.