Theory of Computing, Volume 3 (2007), pp. 159–177 http://theoryofcomputing.org

Removing Degeneracy May Require a Large Dimension Increase^{∗}

Jiří Matoušek  Petr Škovroň

Received: March 12, 2007; published: September 26, 2007.

Abstract: Many geometric algorithms are formulated for input objects in general position; sometimes this is for convenience and simplicity, and sometimes it is essential for the algorithm to work at all. For arbitrary inputs this requires removing degeneracies, which has usually been solved by relatively complicated and computationally demanding perturbation methods.

The result of this paper can be regarded as an indication that the problem of removing degeneracies has no simple “abstract” solution. We consider LP-type problems, a successful axiomatic framework for optimization problems capturing, e. g., linear programming and the smallest enclosing ball of a point set. For infinitely many integers D we construct a Ddimensional LP-type problem such that in order to remove degeneracies from it, we have to increase the dimension to at least (1 + ε)D, where ε > 0 is an absolute constant.

The proof consists of showing that certain posets cannot be covered by pairwise disjoint copies of Boolean algebras under some restrictions on their placement. To this end, we prove that certain systems of linear inequalities are unsolvable, which seems to require surprisingly precise calculations.

∗An extended abstract of this paper has appeared in Proceedings of European Conference on Combinatorics, Graph Theory and Applications 2007 (Eurocomb), pp. 107–113.

ACM Classification: F.2.2

AMS Classification: 68U05, 06A07, 68R99

Key words and phrases: LP-type problem, degeneracy, general position, geometric computation, partially ordered set

Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed

copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2007 Jiří Matoušek and Petr Škovroň

J. Matoušek and P. Škovroň

1 Introduction

Geometric computation and degeneracy. Many descriptions of algorithms in computational geometry or in geometric optimization, as well as numerous proofs in discrete geometry, start with a sentence similar to “Let us assume that the given points are in general position.” General position may mean that no three among the points are collinear, or we may also require than no four are cocircular, etc., depending on the considered problem. Violations of general positions, such as three points on a line, are referred to as degeneracies.

Assuming the input to be nondegenerate (i. e., in general position) usually simplifies the description, analysis, and implementation of a geometric algorithm significantly. For many algorithms, this assumption can be avoided with some extra work and careful attention to detail (a case study, arguing in favor of expending such extra work, is Burnikel et al. [4]). However, for some algorithms, the nondegeneracy assumption is not only a convenient simplification, but rather an essential condition for correctness and/or for running time analysis, which seems difficult to circumvent—we will mention an example below.

General methods have been developed for removing degeneracies in geometric algorithms, based on infinitesimal perturbations of the input (Edelsbrunner and Mücke [8], Yap [22], Emiris and Canny [9]). Roughly speaking, the coordinates of each input object are changed by a suitable function of a real parameter ε > 0, and the considered algorithm is executed with these new input objects, treating ε as a formal quantity, smaller than any concrete nonzero real number occurring in the algorithm. These approaches can actually be implemented, but they have several drawbacks: They slow down the computations significantly (typically by a large constant factor, but sometimes even much more), they increase space requirements, and sometimes it may be difficult or impossible to reconstruct the correct result for the original input from the result for the perturbed input—see [4] for a discussion.

Removing degeneracies means “breaking ties” in some sense. Of course, the ties cannot be broken arbitrarily, since geometric algorithms almost always depend on some kind of global consistency of the input. Still, one might hope for some simpler, perhaps combinatorial, way of removing degeneracies.

To illustrate what we have in mind, let us recall that the famous simplex method of linear programming may also suffer from degeneracy—namely, for many pivoting rules the simplex method may get into an infinite loop (to cycle) for certain highly degenerate inputs. (However, unlike degeneracy in the geometric computations mentioned above, cycling of the simplex method is not an issue in practice.) There are two well-known pivot rules that provably avoid cycling: the lexicographic rule, which is conceptually an infinitesimal perturbation, and Bland’s rule, which is a combinatorial rule working solely with indices of variables and constraints, as opposed to geometric properties of the input. So our question is, whether there is something like a general “Bland’s rule” that would allow one to avoid degeneracies in (some interesting classes of) geometric algorithms.

The present work can be regarded as an indication that a simple, general, and efficient combinatorial method is unlikely to exist.

Removing Degeneracy May Require a Large Dimension Increase

LP-type problems. We investigate the problem of removing degeneracies in a class of optimization problems known as LP-type problems (or “generalized linear programming problems”). This axiomatic framework, invented by Sharir and Welzl in 1992 [19], has become a well-established tool in the field of geometric optimization; see [17, 1, 2, 3, 14, 5, 15, 11] for more applications and results on LP-type problems, as well as e. g. [21, 12, 10, 18] for the investigation of other, related frameworks.

Once it is shown that a particular optimization problem is an LP-type problem and certain algorithmic primitives are implemented for it, several efficient algorithms are immediately at disposal: the Sharir–Welzl algorithm, two other randomized optimization algorithms due to Clarkson [7] (see [13, 6] for a discussion of how it fits the LP-type framework), a deterministic version of it [6], and an algorithm for computing the minimum solution that violates at most k of the given n constraints [16] (this is the promised example of an algorithm where nondegeneracy appears crucial).

An LP-type problem is given by a finite set H of constraints and a value w(G) ∈ ℝ for every subset G ⊆ H. Intuitively, w(G) is the minimum value of a solution that satisfies all constraints in G. As our running example, we will use the problem of computing the smallest disk containing a given planar point set. Here H is a finite point set in ℝ^{2} and w(G) is the radius of the smallest circular disk that encloses all points of G. The general definition is as follows:

Definition 1.1. An LP-type problem is a pair (H,w), where H is a finite set and w: 2^{H} → ℝ is a mapping satisfying the following two conditions:^{1}

Monotonicity: For all F ⊆ G ⊆ H we have w(F) ≤ w(G).
Locality:  For all F ⊆ G ⊆ H and all h ∈ H,
if w(F) = w(G) = w(F ∪ {h}) then w(G ∪ {h}) = w(G).

For the smallest enclosing disk problem, monotonicity is obvious, while verifying locality requires the nontrivial but well known geometric result that the smallest enclosing disk is unique for every set.

The most important parameter of an LP-type problem, essentially controlling the behavior of algorithms dealing with the given problem, is the combinatorial dimension.

Definition 1.2. Let (H,w) be an LP-type problem and let G ⊆ H. A basis of G is any inclusion-minimal subset B ⊆ G with w(B) = w(G). A set B ⊆ H is called a basis in (H,w) if it is a basis of some G ⊆ H. The combinatorial dimension of (H,w) is the maximum cardinality of a basis.

If (H,w) is a smallest enclosing disk problem, then the combinatorial dimension is at most 3 (since for every point set G in the plane there is a subset B of at most 3 points of G such that G and B have the same smallest enclosing disk). Similarly, a higher-dimensional version, the smallest enclosing ball problem of a point set in ℝ^{d}, has combinatorial dimension at most d + 1.

Degeneracy in LP-type problems. What should be considered a degeneracy in the smallest enclosing disk problem? A reasonable answer is a subproblem with an “overdetermined” solution, which means a set G whose minimum enclosing disk is determined by two distinct inclusion-minimal subsets B_{1},B_{2} ⊆ G. For example, B_{1} and B_{2} can be two different diametrical pairs determining the same disk. Nondegeneracy for an arbitrary LP-type problem can be defined in a similar way [16].

1Actually, the usual definition of an LP-type problem is more general: the mapping w can also attain a special value −∞, which is considered smaller than all real numbers, and for which the locality axiom is not required. Moreover, instead of ℝ, one can use an arbitrary linearly ordered set, but this brings nothing new, just sometimes a more convenient notation. We will stick to the definition above since it is simpler, and it will be easy to check that the more general definition doesn’t change anything in our result.

Theory of Computing, Volume 3 (2007), pp. 159–177 161

Figure 1: A degenerate LP-type problem where removing degeneracy increases dimension.

Definition 1.3. We call an LP-type problem (H,w) nondegenerate if w(B_{1}) ≠ w(B_{2}) for any two distinct bases B_{1},B_{2}.

Consequently, in a nondegenerate LP-type problem, every G ⊆ H has exactly one basis.^{2} For removing degeneracies, we want to break the ties w(B_{1}) = w(B_{2}) by slightly modifying the

values of w, while retaining all strict inequalities among the original values:

Definition 1.4. An LP-type problem (H,w′) is a refinement of an LP-type problem (H,w) on the same set of constraints if for all F,G ⊆ H with w(F) < w(G) we have w′(F) < w′(G).

We thus formalize “removing degeneracies” of an LP-type problem (H,w) as the question of finding a nondegenerate refinement of (H,w).

At first sight it might seem that in order to produce a nondegenerate refinement, it should suffice to impose some suitable linear order on every group of bases sharing the same value of w—perhaps one could even take an arbitrary ordering.

However, some thought reveals that things are not that simple. As was observed in [16], sometimes we also have to create new bases, and even larger ones than those present in (H,w). Namely, consider the smallest enclosing disk problem with H = {a,b,c,d} forming the vertices of a square (Figure 1). The set H has two bases B_{1} = {a,c} and B_{2} = {b,d}, and the combinatorial dimension of the problem is 2. We will refer to this particular 2-dimensional LP-type problem as the square example and denote it by (H_{sq},w_{sq}). It is easily checked (we will do so in Section 2) that any nondegenerate refinement has dimension at least 3. Hence removing degeneracies necessarily increases the dimension by 2.

In a preliminary report [20] containing some of the results of the present paper, an LP-type problem was presented where removing degeneracy forces dimension increase by 2. Here we exhibit LP-type problems where the required increase is arbitrarily large.

Theorem 1.5. There exists a positive constant ε > 0 such that for infinitely many values of D, there is an LP-type problem of combinatorial dimension D, for which every nondegenerate refinement has combinatorial dimension at least (1 + ε)D.

The example of an LP-type problem as in the theorem is obtained by an “iterated join” of the square example. We also show that an essentially equivalent example can be represented as a linear program in the usual sense (a highly degenerate linear program).

2Another, seemingly weaker, notion of nondegeneracy naturally coming to mind is to require that every G ⊆ H has a unique basis. However, any LP-type problem satisfies this latter condition can easily be converted into an LP-type problem of the same dimension that is nondegenerate in the sense of Definition 1.3 [16]. So these definitions are essentially equivalent.

Theory of Computing, Volume 3 (2007), pp. 159–177 162

The result can also be understood as telling us that for degenerate LP-type problems, the combinatorial dimension doesn’t convey a full “dimensionality” information about the problem. An alternative dimension parameter might be the smallest possible dimension of a nondegenerate refinement; however, this appears quite hard to determine.

The main open question is, can the smallest possible dimension of a nondegenerate refinement be bounded by some function of the dimension of the original degenerate LP-type problem? In particular, does every 2-dimensional LP-type problem have a nondegenerate refinement of dimension bounded by a universal constant? We suspect that it is not the case, but it seems that the methods of the present paper are not sufficient to yield such a result. The structure of 2-dimensional LP-type problems, say, appears both quite restricted and hard to describe, and at present we have no candidate for an LP-type problem where removing degeneracies might require increasing the dimension by more than a small constant factor.

2 Structure of nondegenerate LP-type problems

Let (H,w) be an LP-type problem. We consider the partially ordered set (poset) (2^{H},⊆) , a Boolean algebra. For every x ∈ ℝ, we define the set system 𝒫_{x}= {G ⊆ H : w(G) = x}. The 𝒫_{x} for all x ∈ ℝ form a partition of 2^{H}. Monotonicity implies that 𝒫_{x} has no “holes”: If F ⊂ M ⊂ G and x = w(F) = w(G), then w(M) = x as well. The following lemma shows that for nondegenerate LP-type problems, each 𝒫_{x} is actually a copy of a Boolean algebra.

Lemma 2.1 (Cube lemma). Let (H,w) be a nondegenerate LP-type problem. For every x ∈ ℝ with 𝒫_{x} ≠ ∅ there exist two (uniquely determined) sets B,C ⊆ H such that 𝒫_{x} = {F ⊆ H : B ⊆ F ⊆ C}. The set B is the basis of all F ∈ 𝒫_{x}.

We call the set {F ⊆ H : B ⊆ F ⊆ C} a cube, we use the notation [B,C] for it, we call B the bottom vertex and C the top vertex of the cube [B,C], and |C \ B| is the dimension of the cube.

Proof. We choose G ∈ 𝒫_{x} arbitrarily, we let B be the basis of G, and we set

C = {h ∈ H : w(B) = w(B ∪ {h})} .

We claim that this choice of B and C satisfies the desired conditions. First we prove that w(B) = w(C). Letting C \ B = {c_{1},...,c_{m}}, we check by induction that w(B) = w(B ∪ {c_{1},...,c_{i}}), i = 0,1,...,m. Indeed, the induction step from i to i + 1 follows immediately from the locality axiom with F = B, G = B ∪ {c_{1},...,c_{i}}, and h = c_{i+1} . Now when we have w(B) = w(C), monotonicity implies that [B,C] ⊆ 𝒫_{x}.

Now let us assume w(F) = w(B) for some F ⊆ H. Let B′be a basis of F; we have w(B′) = w(F) = w(B), and thus B = B′ by nondegeneracy. In particular, B ⊆ F. For every f ∈ F we have w(B) ≤ w(B ∪ {f}) ≤ w(F) = w(B), so w(B) = w(B ∪ {f}), and hence f ∈ C; thus F ⊆ C. Since F was an arbitrary set in 𝒫_{x} and we have obtained B ⊆ F ⊆ C, we conclude with 𝒫_{x} ⊆ [B,C].

The uniqueness of B and C follows from a simple observation that every cube has a unique top and bottom vertex.

Figure 2: The poset 𝒫_{w_{sq}(H_{sq})} for the square example.

To see how this lemma can be used, let us check the claim made in the introduction: every nondegenerate refinement of the square example (H_{sq},w_{sq}) has dimension at least 3. The poset 𝒫_{w_{sq}(H_{sq})} of all subsets of H_{sq} with the same smallest enclosing circle as that of H_{sq} consists of all subsets of {a,b,c,d} containing {a,c} or {b,d}; see Figure 2.

In any nondegenerate refinement, 𝒫_{w_{sq}(H_{sq})}has to be expressed as a disjoint union of cubes, and if the dimension of the refinement were 2, all of these cubes would have to have a 2-element set as the bottom vertex. In order to cover {a,b,c,d}, we have to use a 2-dimensional cube, say [{a,c},{a,b,c,d}]. To cover the remaining sets {b,d}, {a,b,d}, and {b,c,d} by disjoint cubes, we must use at least one of the 0-dimensional (single-vertex) cubes [{a,b,d},{a,b,d}] or [{b,c,d},{b,c,d}] with a 3-element bottom vertex. Therefore a combinatorial dimension of any nondegenerate refinement of (H_{sq},w_{sq}) is at least 3.

3 The construction

We begin by defining a binary operation on LP-type problems.

Definition 3.1. Let (H_{1},w_{1}) and (H_{2},w_{2}) be LP-type problems, and assume H_{1} ∩ H_{2} = ∅. We define a new LP-type problem, denoted by (H,w) = (H_{1},w_{1}) ∗ (H_{2},w_{2}) and called the join of (H_{1},w_{1}) and (H_{2},w_{2}): H := H_{1}∪ H_{2} and w(G) := w_{1}(G ∩ H_{1}) + w_{2}(G ∩ H_{2}) for all G ⊆ H.

Lemma 3.2. The join (H,w) = (H_{1},w_{1}) ∗ (H_{2},w_{2}) is indeed an LP-type problem, and dim(H,w) = dim(H_{1},w_{1}) + dim(H_{2},w_{2}).

Proof. First we observe that if F ⊆ G and w(F) = w(G), then w_{i}(F ∩H_{i}) = w_{i}(G∩H_{i}), i = 1,2. Indeed, since F ∩ H_{i} ⊆ G ∩ H_{i}, we have w_{i}(F ∩ H_{i}) ≤ w_{i}(G ∩ H_{i}), and to get equality of the sum, equality must hold in both components.

Now we verify the axioms for (H,w). Monotonicity is obvious, and for locality, let F ⊆ G ⊆ H and h ∈ H satisfy w(F) = w(G) = w(F ∪ {h}). Supposing h ∈ H_{1}, we have w_{1}(F ∩ H_{1}) = w_{1}(G ∩ H_{1}) = w_{1}((F ∩ H_{1}) ∪ {h}) by the observation above, and locality in (H_{1},w_{1}) yields w_{1}((G ∩ H_{1}) ∪ {h}) = w_{1}(G ∩ H_{1}). Then

w(G ∪ {h}) = w_{1}((G ∩ H_{1}) ∪ {h}) + w_{2}(G ∩ H_{2}) = w_{1}(G ∩ H_{1}) + w_{2}(G ∩ H_{2}) = w(G) ,

so (H,w) is indeed an LP-type problem.

Now we check dim(H,w) ≥ dim(H_{1},w_{1}) + dim(H_{2},w_{2}). Let B_{i} be a basis in (H_{i},w_{i}) witnessing dim(H_{i},w_{i}). It suffices to check that B = B_{1} ∪ B_{2} is a basis in (H,w); that is, w(A) < w(B) for every proper subset of B. Letting A_{i} = A ∩ H_{i}, we have A_{i} ⊆ B_{i} with at least one of the inclusions proper, say A_{1} ⊂ B_{1}. Since B_{1} is a basis, we have w_{1}(A_{1}) < w_{1}(B_{1}) and w(A) < w(B) follows.

For the opposite inequality dim(H,w) ≤ dim(H_{1},w_{1}) + dim(H_{2},w_{2}), we choose a basis B in (H,w) with |B| = dim(H,w) and set B_{i} = B∩H_{i}. It suffices to check that B_{i} is a basis in (H_{i},w_{i}). Let us consider a proper subset A_{1} ⊂ B_{1}; then

w_{1}(B_{1}) + w_{2}(B_{2}) = w(B_{1}∪ B_{2}) > w(A_{1}∪ B_{2}) = w_{1}(A_{1}) + w_{2}(B_{2}) ,

and we get w_{1}(A_{1}) < w_{1}(B_{1}) as needed. The lemma is proved.

The example. For the proof of Theorem 1.5 we define, for a natural number m, an LP-type problem ℒ_{m} as the m-fold join of the square example (H_{sq},w_{sq}). More formally, we choose distinct elements a_{1},...,a_{m}, b_{1},...,b_{m}, c_{1},...,c_{m}, d_{1},...,d_{m}, we let H_{i} = {a_{i},b_{i},c_{i},d_{i}}, and we let w_{i}: H_{i} → ℝ be a “copy” of the value function w_{sq} from the square example, defined on H_{i}. We let

ℒ_{m}= (H,w) = (H_{1},w_{1}) ∗ ··· ∗ (H_{m},w_{m})

(we note that the operation of join is clearly associative). We have |H| = 4m and by the above lemma, ℒ_{m} is an LP-type problem of combinatorial dimension D = 2m. It is easy to check that by taking a join of m suitable nondegenerate refinements of the square example we obtain a nondegenerate refinement of (H,w) of combinatorial dimension 3m.

We want to bound from below the dimension of any nondegenerate refinement of ℒ_{m}. Similar to the warm-up argument for (H_{sq},w_{sq}), any nondegenerate refinement ℒ′= (H,w′) of ℒ_{m} of dimension D′ yields a covering of the poset 𝒫_{w(H)} = {G ⊆ H : w(G) = w(H)} by disjoint cubes [B_{j},C_{j}], where each bottom vertex B_{j} satisfies |B_{j}| ≤ D′. We will deal with this combinatorial problem in the next two sections.

The case m = 2 . The 4-dimensional LP-type problem ℒ_{2} is analyzed in [20], and it is shown that every nondegenerate refinement has dimension at least 6. The corresponding poset 𝒫_{w(H)} is illustrated in Figure 3. Interestingly, this 𝒫_{w(H)} does admit a cover by disjoint cubes with bottom vertices of cardinality at most 5; see Figure 4. However, the covers corresponding to a nondegenerate refinement have to satisfy an additional condition, called acyclicity, and a case analysis in [20] verifies that every acyclic cover must have a bottom vertex of cardinality 6 or larger. Here we won’t define acyclicity; we just remark that arbitrary covers by disjoint cubes correspond to nondegenerate violator spaces, which is a generalization of LP-type problems investigated in [11]. One can thus say that ℒ_{2} has a 5-dimensional nondegenerate refinement in the realm of violator spaces, but not in the realm of LP-type problems. On the other hand, the subsequent proof of Theorem 1.5 doesn’t use acyclicity in any way and thus it applies equally well to violator spaces.

J. Matoušek and P. Škovroň

Figure 3: The poset 𝒫_{w(H)} for m = 2. The numbers in the right indicate sizes of the corresponding sets. Figure 4: A covering of 𝒫_{w(H)} by disjoint cubes with all bottom vertices of size at most 5; a 4dimensional cube is marked by circles around its vertices.

Theory of Computing, Volume 3 (2007), pp. 159–177 166

4 Setting up a linear system

The basic strategy for the proof of Theorem 1.5 is simple. Let ℒ_{m}= (H,w) be the example constructed above and let us suppose that the poset 𝒫 := 𝒫_{w(H)} ⊂ 2^{H} can be covered by disjoint cubes [B_{j},C_{j}] with |B_{j}| ≤ D′. Since dim(H,w) = D = 2m and all bases of (H,w) have exactly this size, we have 2m ≤ |B_{j}| ≤ |C_{j}| ≤ |H| = 4m for all j. Let x_{d,k} denote the number of cubes with |B_{j}| = 2m + d and |C_{j}| = 2m + k, d ≤ Δ := D′− 2m, d ≤ k ≤ 2m. A cube [B_{j},C_{j}] with |B_{j}| = 2m + d and |C_{j}| = 2m + k contains sets of cardinality 2m+ℓ, d ≤ ℓ ≤ k, and the number of sets of this cardinality in [B_{j},C_{j}] equals \binom{k−d}{ℓ−d} (this formula is actually valid for all ℓ if we adopt the convention that \binom{a}{b} = 0 for b < 0 or b > a). If we let

F (m,ℓ) = |{G ∈ 𝒫: |G| = 2m + ℓ}| ,

we get that the x_{k,d} have to satisfy the following system of linear equations:

∑_{d=0}^{Δ} ∑_{k=max(d,ℓ)}^{2m} \binom{k − d}{ℓ − d} x_{d,k}= F (m,ℓ) , ℓ = 0,1,...,2m .  (4.1)

We are going to prove that with Δ = ⌈εD⌉, where ε is a sufficiently small positive constant, this system of equations for variables x_{k,d} has no nonnegative real solution, provided that m is sufficiently large.

To see that an approach based on counting sets of individual cardinalities may help us to prove nonexistence of the covering of 𝒫, note that already the proof in the end of Section 2 may be rephrased in terms of counting. In the poset in Figure 2, the vector of numbers of sets of cardinality 2, 3, and 4 is (2,4,1). However, this vector cannot be obtained as a nonnegative linear combination of vectors (1,0,0), (1,1,0), and (1,2,1), which give numbers of sets of the respective cardinalities in cubes with the allowed cardinality of the bottom vertex.

First we evaluate F (m,ℓ).

Lemma 4.1. We have

F (m,ℓ) = ∑_{s} \binom{m}{s,ℓ − 2s,m − ℓ + s} 2^{m+ℓ−3s} ,

with the sum being over all s with 0 ≤ 2s ≤ ℓ and s ≥ ℓ − m (here \binom{n}{k_{1},k_{2},k_{3}} = \frac{n!}{k_{1}!k_{2}!k_{3}!} is a multinomial coefficient, k_{1}+ k_{2}+ k_{3} = n).

Proof. First we observe, reasoning as in the proof of Lemma 3.2, that a set B ⊆ H is a basis of H in ℒ_{m} if and only if each B_{i} = B ∩ H_{i} is a basis of H_{i} in (H_{i},w_{i}). Hence the bases of H are the sets B with B∩H_{i} = {a_{i},c_{i}} or B∩H_{i} = {b_{i},d_{i}} for all i = 1,2,...,m. A set G ⊆ H is in 𝒫 iff it contains at least one of these bases; i. e., if it contains at least one of the pairs {a_{i},c_{i}},{b_{i},d_{i}} for all i.

For G ∈ 𝒫 of cardinality 2m + ℓ let s_{r} = |{i ∈ {1,2,...,m} : |G ∩ H_{i}| = r}|, r = 2,3,4. We have s_{2} + s_{3} + s_{4} = m and 2s_{2} + 3s_{3} + 4s_{4} = |G| = 2m + ℓ. Calculation shows that s_{2} = m − ℓ + s_{4} and s_{3} = ℓ − 2s_{4}.

For counting the number of possible ways of choosing G, we first fix s = s_{4}. Then s_{2} and s_{3} are fixed as well, and there are \binom{m}{s_{2},s_{3},s_{4}} ways to choose the indices i contributing to each s_{r} (in other words, to choose which are the H_{i} where G takes 2, 3, or 4 elements, respectively). Knowing that |G ∩ H_{i}| = 2, there are two possibilities for G∩H_{i}, for |G∩H_{i}| = 3 we have 4 possibilities, and for |G∩H_{i}| there is just one possibility. Therefore, once |G∩H_{i}| has been fixed for all i, there are 2^{s_{2}}·4^{s_{3}} = 2^{m+ℓ−3s_{4}} possibilities for G. Summation over s = s_{4} yields the statement of the lemma (the conditions on the range of s in the summation correspond to the obvious restrictions s_{2},s_{3},s_{4} ≥ 0).

5 Unsolvability of the linear system

We recall that for finishing the proof of Theorem 1.5, it suffices to show that for Δ := ⌈2εm⌉ and m sufficiently large, the linear system (4.1) has no nonnegative solution x = (x_{d,k})_{d=0}^{Δ} _{k=d}^{2m}.

Before starting with the formal proof, which is a sequence of somewhat frightening calculations, we say a few words about how it was found. We started by testing the solvability for concrete values of parameters via linear programming. We used the function LinearProgramming in Mathematica, which uses arbitrary precision arithmetic and computes the solution exactly; this allowed us to deal with m up to about 1000 (other LP solvers we tried failed for large instances because of insufficient accuracy). By the Farkas lemma, the unsolvability is always witnessed by a linear combination of the equations that has nonnegative coefficients on the left-hand side and negative right-hand side. By minimizing the sum of absolute values of (suitably normalized) coefficients providing such a linear combination, we found that the unsolvability was witnessed, in all examples we tried, by a linear combination of only 3 of the equations. For simplifying the analytic approach, we then tried 3 consecutive equations, and found that such combinations work as well, provided that the index of the middle equation is chosen in a suitable range. These numerical results encouraged us to try finer and finer estimates, until we finally reached the following proof.

Proof of the unsolvability of (4.1). We set, somewhat arbitrarily, t = m/2, assuming m even (we suspect that t = τm for any fixed τ ∈ (0,1) would work, but we haven’t checked). We will show that for sufficiently large m already the system of the three consecutive equations with ℓ = t − 1, t, and t + 1 has no nonnegative solution. To this end, we find a linear combination of these three equations, with suitable coefficients α,β,γ, such that the resulting equation has all coefficients on the left-hand side nonnegative, while the right-hand side is strictly negative. We will assume that β is negative and we normalize the coefficients so that β = −1 (we need not justify this assumption since we are free to choose α,β,γ as we wish). Explicitly, to have the coefficient of the variable x_{d,k} in the resulting equation nonnegative, we need that the following system of (Δ + 1)(2m − Δ/2 + 1) inequalities is satisfied:

α\binom{k − d}{t − d − 1} − \binom{k − d}{t − d} + γ\binom{k − d}{t − d + 1} ≥ 0 , 0 ≤ d ≤ Δ , d ≤ k ≤ 2m .  (5.1)

To have right-hand side strictly negative, we need the following inequality:

αF (m,t − 1) − F (m,t) + γF (m,t + 1) < 0 .  (5.2)

Our basic intuition behind the proof is a “continuous” one: For m large and fixed, the left-hand side of (5.2) is something like a “weighted second derivative” of F (m,t) according to t, while on the lefthand side of (5.1)we have the same kind of the weighted second derivatives of the binomial coefficients.

So our goal is to prove that the graph of F (m,t) “bends less” than the graph of any of the binomial coefficients involved, and hence F cannot be built as a positive linear combination of the binomial coefficients.

However, this initial intuition is a quite rough one, since the choice of suitable α and γ turns out to be surprisingly subtle. Namely, we need to choose α = α_{0}+ α_{1}/t and γ = γ_{0}+ γ_{1}/t, where

α_{0} = \frac{\sqrt{10}+ 2}{4} ≈ 1.29057 , γ_{0} = \frac{\sqrt{10}− 2}{6} ≈ 0.193713

are uniquely determined real constants and α_{1},γ_{1} are constants in certain ranges. For concreteness we set α_{1} = 1 and γ_{1} = 1/8.

We get (5.1) from the following lemma:

Lemma 5.1. There is a positive constant ε > 0 such that, with the above choice of t, α, and γ, Equation (5.1) holds for all d ≤ Δ = ⌈2εm⌉ and for all k ≥ d, provided that m, and hence t, are sufficiently large.

Proof. We use the substitution y = k−d and x = t −d. We thus want to show α\binom{y}{x−1}−\binom{y}{x}+γ\binom{y}{x+1} ≥ 0. For y < x−1 all three terms are 0, and so we may assume y ≥ x−1. We rewrite the left-hand side to

\frac{y!}{(x + 1)!(y − x + 1)!} ( αx(x + 1) − (x + 1)(y − x + 1) + γ(y − x + 1)(y − x)) .

Let us denote by f(α,γ,y,x) the expression in parentheses; we want to show that it is nonnegative.

Let us choose constants α′_{1}< α_{1} and γ′_{1}< γ_{1}. Assuming ε in the lemma sufficiently small, we have d sufficiently small compared to x, and hence α = α_{0}+α_{1}/(x+d) ≥ α_{0}+α′_{1}/x and γ = γ_{0}+γ_{1}/(x+d) ≥ γ_{0}+ γ′_{1}/x.

Since f is nondecreasing in α and in γ (for the relevant y and x), it suffices to check that

f(α_{0}+ \frac{α′_{1}}{x} ,γ_{0}+ \frac{γ′_{1}}{x},y,x) ≥ 0 ,

and we will verify this for all sufficiently large real x and all real y. One of the properties of α_{0} and γ_{0} needed here is α_{0}γ_{0} = 1/4. Things can be simplified a little by the substitution y = x(z + 1). Then f(α_{0}+ α′_{1}/x,γ_{0}+ γ′_{1}/x,x(z + 1),x) is a polynomial in x and z. For x fixed it is a quadratic polynomial in z, and the coefficient of z^{2} is γ_{0}x^{2}+ γ′_{1}x > 0 (this calculation and the subsequent ones were done using Mathematica). Therefore, it has a unique minimum, which can be found by setting the first derivative (according to z) to 0. This minimum occurs at

z_{0} = z_{0}(x) = \frac{x^{2}+ (1 − γ_{0})x − γ′_{1}}{2x(γ_{0}x + γ′_{1})} .

Substituting this into f(α_{0}+ \frac{α′_{1}}{x},γ_{0}+ \frac{γ′_{1}}{x},z(x + 1),x) yields a function of x of the form

\frac{−γ_{0}− 2γ_{0}^{2}+ 4α′_{1}γ_{0}^{2}+ γ′_{1}}{4γ_{0}^{2}} x + O(1) ,

the O(.) notation referring to x → ∞. Calculation shows that the coefficient of x is a positive real number (for α′_{1}and γ′_{1}sufficiently close to α_{1} and γ_{1}, respectively). Hence f is indeed positive for the considered values of the variables.

Remark. It is easy to check that if α,γ are positive constants, then the inequality f(α,γ,x,y) ≥ 0 holds for all y and all sufficiently large x if and only if αγ > \frac{1}{4}. However, for such α and γ (5.2) fails. We are thus forced to choose α and γ depending on x such that αγ → \frac{1}{4} as x → ∞.

We now proceed to establish (5.2). We set

Q(m,t,s) = \binom{m}{s,t − 2s,m − t + s} 2^{m+t−3s} ,

so that F (m,t) = ∑_{s}Q(m,t,s). First we look for the s maximizing Q(m,t,s). Let

r(m,t,s) = \frac{Q(m,t,s)}{Q(m,t,s − 1)} = \frac{(t − 2s + 1)(t − 2s + 2)}{8s(m − t + s)}

be the ratio of two consecutive terms. As a function of s it is decreasing, and so Q(m,t,s) is maximum for the largest s with r(m,t,s) ≥ 1.

We stick to our choice t = m/2. It is more convenient to use t as a parameter; let us write r̃(t,s) = r(2t,t,s) and Q̃(t,s) = Q(2t,t,s), and let us note that m−t = t. If we let σ = (\sqrt{10}−3)/2 ≈ 0.0811388 be the positive root of the equation (1 − 2σ)^{2} = 8σ(1 + σ) and s_{0} = ⌊σt⌋, then

r̃(t,s_{0}) = \frac{(t − 2s_{0}+ 1)(t − 2s_{0}+ 2)}{8s_{0}(m − t + s_{0})}
= \frac{(1 − 2σ + O(t^{−1} ))^{2}}{8(σ + O(t^{−1} ))(1 + σ + O(t^{−1} ))}
= \frac{(1 − 2σ)^{2}}{8σ(1 + σ)} + O(t^{−1} )
= 1 + O(t^{−1} ) .

Next, we need an estimate on the rate of decrease of Q̃(t,s_{0}+ a) as |a| increases.

Lemma 5.2. Let c_{0} = \frac{4}{1−2σ} + \frac{1}{σ} + \frac{1}{1+σ} ≈ 18.0244. Suppose that a = o(t^{2/3}). Then

\frac{Q̃(t,s_{0}+ a)}{Q̃(t,s_{0})} = (1 + o(1))e^{−c_{0}a^{2}/2t} ,

where o(.) refers to t → ∞ and the convergence is uniform in a.^{3}

1 − ζ(t) ≤ \frac{Q̃(t,s_{0}+ a)}{Q̃(t,s_{0})e^{−c_{0}a^{2}/2t}} ≤ 1 + ζ(t)

3That is, there exists a function ζ: (0,∞) → [0,∞) with ζ(t) → 0 as t → ∞ such that for all relevant a and t.

Theory of Computing, Volume 3 (2007), pp. 159–177 170

Proof. We will be summing over j = 1,2,...,a in the proof. Let us write ξ = j/t; thus ξ = o(1). We have, using 1 + x = e^{x}+ O(x^{2}),

r̃(t,s_{0}+ j) = (1 + O(t^{−1} ))\frac{r̃(t,s_{0}+ j)}{r̃(t,s_{0})}

= (1 + O(t^{−1} ))\begin{matrix}( 1 − \frac{2j}{t−2s_{0}+1} ) & ( 1 − \frac{2j}{t−2s_{0}+2} ) \\ ( 1 + \frac{j}{s_{0}}) & ( 1 + \frac{j}{t+s_{0}} ) \end{matrix}

= (1 + O(t^{−1} ))\begin{matrix}(1 − \frac{2}{1−2σ} ξ) & 2 \\ (1 + \frac{1}{σ}ξ) & (1 + \frac{1}{1+σ} ξ) \end{matrix}

= (1 + O(t^{−1} ))\begin{matrix}( e^{− \frac{2}{1−2σ} ξ} + O(ξ^{2})) & 2 \\ ( e^{\frac{1}{σ} ξ} + O(ξ^{2})) & ( e^{\frac{1}{1+σ} ξ} + O(ξ^{2})) \end{matrix}

= (1 + O(t^{−1} ))(1 + O(ξ^{2}))e^{−(\frac{2}{1−2σ} + \frac{1}{σ} + \frac{1}{1+σ} ) ξ}
= (1 + O(t^{−1} ) + O(ξ^{2}))e^{−c_{0}ξ} .

Then, using ln(1 + x) = x + O(x^{2}),

ln \frac{Q̃(t,s_{0}+ a)}{Q̃(t,s_{0})} = ∑_{j=1}^{a} lnr̃(t,s_{0}+ j)

= ( ∑_{j=1}^{a} −\frac{c_{0}j}{t} ) + O( \frac{a}{t}) + O( \frac{a^{3}}{t^{2}})

= −\frac{c_{0}a^{2}}{2t} + O( \frac{a}{t} + \frac{a^{3}}{t^{2}}) .

The lemma follows.

Next, we consider the expression D̃(t,s) = αQ(m,t −1,s)−Q(m,t,s)+γQ(m,t +1,s) with m = 2t, α = α_{0} + α_{1}/t, and γ = γ_{0} + γ_{1}/t as above. The idea is to show that for s close to s_{0} we have D̃(t,s) negative, while for s further from s_{0} it can be positive but it is sufficiently small compared to −D̃(t,s_{0}). Again, the calculation has to be done rather precisely in order to work.

Lemma 5.3. Let us suppose that a = o(t), and let s_{0} = ⌊σt⌋ be as above. Then

D̃(t,s_{0}+ a) = Q̃(t,s_{0}+ a)\frac{C}{t}( \frac{c_{1}}{t}a^{2}− 1 + o(1)) ,

where C is a certain positive constant whose value will not be important,

c_{1} = (14584\sqrt{10}+ 46192)/5877 ≈ 15.70710522 ,

the o(.) notation refers to t → ∞, and the convergence is uniform in a.

Proof. Similar to the proof of Lemma 5.1 we rewrite

D̃(t,s) = Q̃(t,s) · \frac{1}{2(t + 1 − 2s)(t + s + 1)} g(α,γ,t,s) ,

with g(α,γ,t,s) = α(t −2s+1)(t −2s)−2(t −2s+1)(t +s+1)+4γ(t +s)(t +s+1). With the constant σ as above, g(α_{0}+ α_{1}/t,γ_{0}+ γ_{1}/t,t,σt) becomes a polynomial in t, which is a priori quadratic, but the constants α_{0} and γ_{0} are chosen so that the coefficient at t^{2}, which equals 14−5\sqrt{10}+(26−8\sqrt{10})α_{0}+ (11 − 2\sqrt{10})γ_{0}, vanishes. (This, together with α_{0}γ_{0} = \frac{1}{4}, are the two conditions that uniquely determine α_{0} and γ_{0}.) The coefficient of the linear term equals −c_{2} = (191 − 62\sqrt{10})/8 ≈ −0.632652 (and thus g(α,γ,t,s) is indeed negative and of order t for s sufficiently near to σt).

More quantitatively, expanding and simplifying gives

g(α_{0}+ α_{1}/t,γ_{0}+ γ_{1}/t,t,σt + b) = −c_{2}t + c_{3}b^{2}+ O(b^{2}/t + b + 1)

with c_{3} = (14 + 5\sqrt{10})/3. For a = b + σt − s_{0} = b + σt − ⌊σt⌋ ≤ b + 1 we then obtain

g(α_{0}+ α_{1}/t,γ_{0}+ γ_{1}/t,t,s_{0}+ a) = −c_{2}t + c_{3}a^{2}+ O(a^{2}/t + a + 1) .

Therefore, using a = o(t), we arrive at

D̃(t,s_{0}+ a) = Q̃(t,s_{0}+ a) · \frac{−c_{2}t + c_{3}a^{2}+ O(a^{2}/t + a + 1)}{2(t + 1 − 2s)(t + s + 1)}
= Q̃(t,s_{0}+ a) · \frac{C}{t}( \frac{c_{3}a^{2}}{c_{2}t} − 1 + o(1))

as required.

We are ready to prove (5.2). For our choice of α, γ, and t we have

αF (m,t − 1) − F (m,t) + γF (m,t + 1) = ∑_{a} D̃(t,s_{0}+ a) .

For concreteness let us set a_{0} = t^{3/5}. We will show that

∑_{|a|≤a_{0}} D̃(t,s_{0}+ a) ≤ −\frac{δ}{\sqrt{t}} Q̃(t,s_{0})

for a constant δ > 0. Now for a > a_{0} we have

|D̃(t,s_{0}+ a)| ≤ αQ̃(t − 1,s_{0}+ a) + Q̃(t,s_{0}+ a) + γQ̃(t + 1,s_{0}+ a) .

We have Q(t − 1,s_{0}+ a) ≤ Q̃(t − 1,s_{0}+ a_{0}), which is smaller than Q̃(t − 1,s_{0}) by a factor exponential in t (see Lemma 5.2). A similar argument applies for t and t + 1 and for a < −a_{0} and thus the sum over |a| > a_{0} is negligible.

Combining Lemmas 5.2 and 5.3, we get that for |a| ≤ a_{0} we have

D̃(t,s_{0}+ a) = Q̃(t,s_{0})\frac{C}{t}(1 + ϕ_{t}(a))e^{−c_{0}a^{2}/2t} ( \frac{c_{1}a^{2}}{t} − 1 + ψ_{t}(a)) ,

where ϕ_{t}(a) and ψ_{t}(a) are some functions converging to 0 as t → ∞, uniformly in a.

We will show that

∑_{|a|≤a_{0}} (1 + ϕ_{t}(a))e^{−c_{0}a^{2}/2t} ( 1 − \frac{c_{1}a^{2}}{t} − ψ_{t}(a)) = Ω(\sqrt{t}) .  (5.3)

Let us fix an arbitrarily small ν > 0 and let us assume that t has been chosen so large that |ϕ_{t}(a)| ≤ ν, |ψ_{t}(a)| ≤ ν for all a. Then the left-hand side of (5.3) is bounded from below by

∑_{|a|≤a_{0}} e^{−c_{0}a^{2}/2t}(1 − c_{1}a^{2}/t) − ∑_{|a|≤a_{0}} (1 + |ϕ_{t}(a)|)e^{−c_{0}a^{2}/2t}|ψ_{t}(a)| − ∑_{|a|≤a_{0}} |ϕ_{t}(a)|e^{−c_{0}a^{2}/2t}

≥ ∑_{|a|≤a_{0}} e^{−c_{0}a^{2}/2t} ( 1 − \frac{c_{1}a^{2}}{t}) − 3ν ∑_{|a|≤a_{0}} e^{−c_{0}a^{2}/2t} .

By basic properties of Riemann integration and uniform continuity arguments it is routine to check that both of these sums converge to the corresponding integrals as t → ∞. So it suffices to bound from below

(1 − 3ν)∫_{−a_{0}}^{a_{0}} e^{−c_{0}a^{2}/2t} da − \frac{c_{1}}{t} ∫_{−a_{0}}^{a_{0}} a^{2}e^{−c_{0}a^{2}/2t} da .

Since a_{0}^{2}/t = t^{1/5} → ∞ as t → ∞ and the integrands decrease exponentially in a^{2}/t, we make only a negligible error by taking both integrals from −∞ to ∞. We have

(1 − 3ν)∫_{−∞}^{∞} e^{−c_{0}a^{2}/2t} da = (1 − 3ν)\sqrt{2πt/c_{0}}≈ 0.590419\sqrt{t}

while

\frac{c_{1}}{t} ∫_{−∞}^{∞} a^{2}e^{−c_{0}a^{2}/2t} da = c_{1}\sqrt{2π}c_{0}^{−3/2} \sqrt{t}≈ 0.514513\sqrt{t} .

This finally proves (5.2).

6 A geometric representation by a linear program

It turns out that an LP-type problem ℒ̂_{m}= (H,ŵ), which is similar to ℒ_{m} and which can also be used as an example establishing Theorem 1.5, can be represented as a linear program. To see that our proof of Theorem 1.5 works for ℒ̂_{m} as well, it will be enough to verify that its poset 𝒫_{ŵ(H)} of maximum-weight sets is isomorphic to 𝒫_{w(H)} of ℒ_{m}, and this will follow from the discussion below.

Figure 5: A linear program in ℝ^{3} essentially representing the square example.

We begin by setting up the following linear program with variables x,y,z (η > 0 is a very small positive real number):

minimize z + ηy + η^{2}x subject to
a:  x + 4y − 2z ≤ 1
b: 3x + 8y + 2z ≤ 5
c: 3x − 8y + 2z ≤ −3
d : −x − 4y − 2z ≤ −3
x,y,z ≥ 0 .

The corresponding LP-type problem (H_{sq},ŵ_{sq}) has the set H_{sq} = {a,b,c,d} of four constraints corresponding to the four inequalities of the linear program. The value ŵ_{sq}(G) of any subset G ⊆ H_{sq} is the minimum of the linear program where the constraints of H_{sq}\ G have been deleted (we stress that the implicit nonnegativity constraints x,y,z ≥ 0 are always present, even for G = ∅). In this way, ŵ_{sq}(G) is well defined for every G.

The linear program is illustrated in Figure 5. For better visualization, the picture shows the unit cube [0,1]^{3}, and intersections of the bounding planes of the constraints with the facets x = 0 and x = 1 of the cube. The minimum of the linear programs containing both the constraints a and c or both the constraints b and d is attained at the point x_{abcd} = (0,1/2,1/2); thus, ŵ_{sq}(H_{sq}) = 1/2. It can be checked that for every subset G of constraints containing neither {a,c} nor {b,d}, the minimum is attained at a point with z = 0, and thus with ŵ_{sq}< 1/2 (the picture shows the minima for all G of cardinality 2). Thus ℒ̂ is a 2-dimensional LP-type problem with the poset 𝒫_{ŵ_{sq}(H_{sq})} isomorphic to 𝒫_{w_{sq}(H_{sq})} for the square example.

Next, we observe that if (H,w) is an LP-type problem corresponding to a linear program with variables x_{1},...,x_{n} and with objective min∑ c_{i}x_{i}, and (H′,w′) is an LP-type problem corresponding to a linear program with variables x′_{1},...,x′_{n} and with objective min∑ c′_{i}x′_{i}, then the join (H,w)∗(H′,w′) corresponds to the linear program obtained by putting the constraints of both linear programs together and with objective min(∑ c_{i}x_{i}+∑ c′_{i}x′_{i}). Indeed, it suffices to check that the value function in (H,w)∗(H′,w′) coincides with the value function obtained from the combined linear program, and this is immediate. In particular, the m-fold join ℒ̂_{m} of m disjoint copies of (H_{sq},ŵ_{sq}) corresponds to the following linear program in 3m variables:

minimize ∑ _{i=1}^{m} (z_{i}+ ηy_{i}+ η^{2}x_{i}) subject to

\begin{matrix}x_{i}+ 4y_{i}− 2z_{i} & ≤ & 1 \\ 3x_{i}+ 8y_{i}+ 2z_{i} & ≤ & 5 \\ 3x_{i}− 8y_{i}+ 2z_{i} & ≤ & −3 \\ −x_{i}− 4y_{i}− 2z_{i} & ≤ & −3 \\ x_{i},y_{i},z_{i} & ≥ & 0 \end{matrix} \} i = 1,2,...,m .

We could have presented the example for Theorem 1.5 in this form, but we find the abstract construction of join more transparent.

Acknowledgment

We would like to thank the anonymous referees for careful reading and a number of valuable comments.

References

[1] * N. Amenta: Helly theorems and generalized linear programming. Discrete and Computational Geometry, 12:241–261, 1994. [Springer:bx1262r145x60505]. 1

[2] * N. Amenta: A short proof of an interesting Helly-type theorem. Discrete and Computational Geometry, 15:423–427, 1996. [Springer:1fdgptcx3qfd4vm4]. 1

[3] * H. Björklund, S. Sandberg, and S. Vorobyov: A discrete subexponential algorithm for parity games. In Proc. 20th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’03), Lect. Notes Comput. Sci. 2607, pp. 663–674. Springer-Verlag, 2003. [Springer:wpjqa08u8db47c3g]. 1

[4] * C. Burnikel, K. Mehlhorn, and S. Schirra: On degeneracy in geometric computations. In Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA’94), pp. 16–23. SIAM, 1994. [SODA:314464.314474]. 1

[5] * T. Chan: An optimal randomized algorithm for maximum Tukey depth. In Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 430–436. SIAM, 2004. [SODA:982792.982853]. 1 [6] * B. Chazelle and J. Matoušek: On linear-time deterministic algorithms for op-

timization problems in fixed dimension. Journal of Algorithms, 21:579–597, 1996. [Elsevier:10.1006/jagm.1996.0060]. 1

[7] * K. L. Clarkson: Las Vegas algorithms for linear and integer programming. Journal of the ACM, 42:488–499, 1995. [JACM:201019.201036]. 1

[8] * H. Edelsbrunner and E. P. Mücke: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1):66–104, 1990. [ACM:77635.77639]. 1

[9] * I. Emiris and J. Canny: A general approach to removing degeneracies. SIAM J. Computing, 24:650–664, 1995. [SICOMP:10.1137/S0097539792235918]. 1

[10] * K. Fischer: Smallest enclosing balls of balls. PhD thesis, ETH Zürich, Nr. 16168, 2005.

Available at http://e-collection.ethbib.ethz.ch. 1

[11] * B. Gärtner, J. Matoušek, L. Rüst, and P. Škovroň: Violator spaces: Structure and algorithms. Discr. Appl. Math., 2007. In press. Also in arXiv cs.DM/0606087. Extended abstract in Proc. 14th Europ. Symp. Algorithms (ESA’06). [arXiv:cs.DM/0606087]. 1, 3

[12] * B. Gärtner and I. Schurr: Linear programming and unique sink orientations. In Proc. 17th Ann. Symp. on Discrete Algorithms (SODA’06), pp. 749–757. ACM Press, 2006. [SODA:1109557.1109639]. 1

[13] * B. Gärtner and E. Welzl: Linear programming - randomization and abstract frameworks. In Proc. 13th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’96), pp. 669–687, London, UK, 1996. Springer-Verlag. 1

[14] * B. Gärtner and E. Welzl: A simple sampling lemma: Analysis and applications in geometric optimization. Discrete and Computational Geometry, 25(4):569–590, 2001. [Springer:9flx12lr0mghtcc4]. 1

[15] * N. Halman: On the power of discrete and of lexicographic Helly-type theorems. In Proc. 46th FOCS, pp. 463–472. IEEE Comp. Soc. Press, 2004. [FOCS:10.1109/FOCS.2004.47]. 1

[16] * J. Matoušek: On geometric optimization with few violated constraints. Discrete and Computational Geometry, 14:365–384, 1995. [Springer:r750741557886767]. 1, 1, 1, 2

[17] * J. Matoušek, M. Sharir, and E. Welzl: A subexponential bound for linear programming. Algorithmica, 16:498–516, 1996. [Algorithmica:r378224736133416]. 1

[18] * I. Schurr: Unique sink orientations of cubes. PhD thesis, ETH Zürich, Nr. 15747, 2004. Nr.

15747. Available at http://e-collection.ethbib.ethz.ch. 1

[19] * M. Sharir and E. Welzl: A combinatorial bound for linear programming and related problems. In Proc. 9th Symp. on Theoretical Aspects of Computer Science (STACS’92), volume 577 of Lecture Notes in Computer Science, pp. 569–579. Springer-Verlag, 1992. 1 [20] * P. Škovroň: Removing degeneracies in LP-type problems may need to increase dimension. In

Jana Šafránková and Jiří Pavlů, editors, Proc. 15th Week of Doctoral Students (WDS), pp. I:196–207. Matfyzpress, Prague, 2006. 1, 3, 3

[21] * T. Szabó and E. Welzl: Unique sink orientations of cubes. In Proc. 42nd FOCS, pp. 547– 555. IEEE Comp. Soc. Press, 2001. [FOCS:10.1109/SFCS.2001.959931]. 1

[22] * C. K. Yap: A geometric consistency theorem for a symbolic perturbation scheme. Journal of Computer and System Sciences, 40(1):2–18, 1990. [JCSS:10.1016/0022-0000(90)90016-E]. 1

AUTHORS

Jiří Matoušek [About the author]

Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI) Charles University, Malostranské nám. 25 118 00 Praha 1, Czech Republic matousek kam mff cuni cz

http://kam.mff.cuni.cz/~matousek/

Petr Škovroň [About the author]

Department of Applied Mathematics Charles University, Malostranské nám. 25 118 00 Praha 1, Czech Republic xofon kam mff cuni cz

http://kam.mff.cuni.cz/~xofon/

ABOUT THE AUTHORS

Jiří Matoušek has been at Charles University in Prague steadily from 1981 on, although his role there has somehow progressed from student to professor. He has also often enjoyed the hospitality of nice people at many places, most extensively in Berlin, Germany and Zürich, Switzerland. He has written papers and textbooks in various areas of discrete mathematics and theoretical computer science, such as discrete and computational geometry, low-distortion embeddings of metric spaces, geometric discrepancy, and topological combinatorics, often just out of curiosity. From his youth he has retained an aversion towards questionnaires and biographical sketches, although many other things he has already forgotten.

Petr Škovroň is just finishing his Ph. D. in the Department of Applied Mathematics of Charles University, Prague under the supervision of Jiří Matoušek. He is about to enter a computer industry career. In his free time he likes to play jazz on the flute.