Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 29-35.

The Upper Bound Conjecture for Arrangements of Halfspaces

Johann Linhart^{∗}

Mathematisches Institut der Universität Salzburg Hellbrunnerstraße 34, A-5020 Salzburg

Abstract. For an arbitrary arrangement of n open hemispheres of S^{d}, it is conjectured that the number of vertices contained in at most k of the hemispheres attains its maximum for each k < (n − d)/2 in case the hemispheres determine the dual of a spherical cyclic polytope. This would imply a sharp upper bound on the analogous numbers for arrangements of half-spaces in E^{d}. The latter is proved here for d ≤ 4.

1. Introduction

In Euclidean d-space E^{d}, an (open) half-space is a subset defined by a linear inequality, H^{+} = {x ∈ E^{d} | u · x > β }, with a non-zero vector u ∈ E^{d} and a real number β. For β = 0, the intersection of H^{+} with the unit sphere of E^{d} is called an (open) hemisphere or also half-space of S^{d−1}. A finite set of half-spaces of E^{d} or S^{d} is called an arrangement of half-spaces. Equivalently, one might speak of arrangements of oriented hyperplanes or hyperspheres.

Each such arrangement A = {H_{1}^{+},…, H_{n}^{+}} dissects the (Euclidean or spherical) space into a number of “cells” or “faces”, which may be defined as follows. Associate to each point x a position vector (p_{1},…, p_{n}) ∈ {−1, 0, +1}^{n} by setting

p_{i} := \{ \begin{matrix}+1 & if x ∈ H_{i}^{+} \\ 0 & if x ∈ H_{i}, \\ −1 & if x ∈ H_{i}^{−}, \end{matrix}

where H_{i} is the bounding hyperplane of the half-space H_{i}^{+}, and H_{i}^{−} is the complement of H_{i} ∪ H_{i}^{+}. If two points have the same position vector, call them equivalent. Then the corresponding equivalence classes are the faces of A. As usual, faces of dimension zero are called vertices.

∗ Research supported partially by the Austrian Science Foundation (FWF), project No. P8625-PHY.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1993 Heldermann Verlag, Berlin

The position vectors of the vertices of a spherical arrangement constitute the cocircuits of an oriented matroid [1]. One might conjecture that the results of this paper generalize to arbitrary oriented matroids. However, it is not clear whether the method of proof used here generalizes, since it uses the so-called “switchings” or “mutations” of simplices (see before Lemma 3), which are not generally applicable for oriented matroids [1].

For each vertex, we consider the number of half-spaces containing it. This will be called the weight of the vertex. It may be any integer from 0 to n − d. Let us denote by v_{k} the number of vertices having weight k, and by g_{k} the number of vertices having weight at most k, thus g_{k} = ∑_{j=0}^{k} v_{j}.

For proving upper bounds of the numbers g_{k}, we may assume the arrangement to be simple, which means that each (d + 1)-subset of the hyperplanes of the arrangement determines a d-simplex. Otherwise, we may transform the arrangement into a simple one by small displacements of the hyperplanes such that none of the numbers g_{k} decreases.

For simple arrangements we have ∑_{k=0}^{n−d} v_{k} = \binom{n}{d} on E^{d}, or 2\binom{n}{d} on S^{d}. Moreover, v_{n−d−k} = v_{k} on the sphere, since for each vertex of weight k the antipodal vertex has weight n − d − k. Thus, on S^{d}, the numbers v_{k} and g_{k} are interesting for k < (n − d)/2 only.

These numbers (and the corresponding ones for higher dimensional faces) are of importance in computational geometry and have already been investigated by several authors (see e.g. [3], [9]). If the intersection of the half-spaces H_{i}^{−} is not empty, the weight of a vertex is also called its level.

In particular, there are the following results:

(a) in S^{2}: g_{k} ≤ (k + 1)n for k < (n − 2)/2 (cf. [7]),

(b) in E^{d} or S^{d}: g_{k} = O (k^{⌈^{\frac{d}{2}}⌉}n^{⌊^{\frac{d}{2}}⌋}) if k = o(n) (cf. [2]).

The result (a) is sharp, and (b) gives the correct order of magnitude, since it is realized by an arrangement defining the dual of a cyclic polytope. In [5] and [7] explicit bounds for g_{k} were given (for arbitrary dimension d), but they are only sharp in special cases.

The arrangements of n half-spaces intersecting in a polyhedron with n facets are of particular importance. In Euclidean space it is somewhat more convenient to consider the case where the intersection of the negative half-spaces is such a polyhedron. Thus we define an arrangement A = {H_{1}^{+},…, H_{n}^{+}} to be polyhedral if

P (A) := ⋂_{i=1}^{n} clH_{i}^{−}

is a (possibly unbounded) polyhedron with n facets (cl denotes the closure). If P (A) is the dual of a cyclic polytope, we call A cyclically polyhedral. On the sphere S^{d}, we understand by the “dual of a cyclic polytope” with n facets the intersection of n hemispheres given by the inequalities a_{i} · x < 0 with a_{i} = (1, t_{i}, t_{i}^{2},…, t_{i}^{d}) and 0 < t_{1} < … < t_{n}. For the numbers v_{k,n,d} of vertices of weight k of the corresponding arrangement, we have

v_{k,n,d} = \{ \begin{matrix}2\binom{n−k−m}{m−1}\binom{k+m−1}{m−1} & for d = 2m − 1, \\ \frac{2n}{d} \binom{n−k−m−1}{m−1}\binom{k+m−1}{m−1} & for d = 2m. \end{matrix}

This may be derived in a similar manner as the formula for the number of facets of a cyclic polytope (cf. [4]). Presumably each polyhedron combinatorially equivalent to this very special “dual of a cyclic polytope” yields an arrangement with the same numbers v_{k} = v_{k,n,d} of vertices of weight k, provided the arrangement is simple. For d ≤ 4, this has been proved by M.Philipp [10]. For d ≤ 3, the numbers v_{k} are even the same for all simple polyhedral arrangements of n hemispheres on S^{d}. This is almost trivial for d ≤ 2, and for d = 3 it has been observed independently by Clarkson/Shor [2] and Philipp [10].

The main subject of the present article is the following conjecture (cf. also [7]), which may be viewed as a generalization of the well-known upper bound theorem for convex polytopes [8], since g_{0} is the number of vertices of the polyhedron P (A).

Conjecture. In an arbitrary arrangement of n half-spaces of S^{d}, the number g_{k} of vertices having weight at most k attains its maximum for each k < (n − d)/2 in the case of a cyclically polyhedral arrangement.

This conjecture would imply the same upper bound for Euclidean arrangements, as may be seen by identifying E^{d} with the “northern” hemisphere of S^{d}. (This is explained in detail in the proof of Lemma 1.) However, in E^{d} the numbers g_{k} may be strictly smaller than for the corresponding spherical arrangement, since some of the (spherical) vertices having weight at most k may lie on the “southern” hemisphere. So the cases where the maximum is attained must be treated separately.

Unfortunately, we are only able to prove this conjecture for E^{d}, and only for d ≤ 4. On the other hand, we get a result valid for all k ≤ n − d, but it seems to be sharp only for k < (n − d)/2.

2. The theorem and its proof

Theorem. For each arrangement of n half-spaces in E^{d}, d ≤ 4, and for each k ≤ n − d, the number g_{k} of vertices having weight at most k cannot be greater than the corresponding number in a cyclically polyhedral arrangement of n hemispheres on S^{d}.

In view of the values of v_{k,n,d} given above this yields the following explicit bounds:

g_{k} ≤ \{ \begin{matrix}(k + 1)n & for d = 2, \\ (k + 1)(k + 2)(3n − 2k − 6)/3 & for d = 3, \\ (k + 1)(k + 2)(3n − 2k − 9)n/12 & for d = 4. \end{matrix}

The proof of this theorem is based on the following concept. Let u be a nonzero vector in E^{d} and β, γ two real numbers. If we associate to each t ∈ [0, 1] the half-space

H^{+}(t) := {x ∈ E^{d} | u · x > β + γt}

we call H^{+} a constantly moving half-space (with velocity γ ). A finite set of constantly moving half-spaces will shortly be called a moving arrangement. The velocities of the individual half-spaces may of course be different.

Lemma 1. For each polyhedral arrangement in E^{d}, d ≤ 3, the assertion of the theorem is true.

Proof. Let A = {H_{1}^{+},…, H_{n}^{+}} be an arrangement in E^{d}, and identify E^{d} with a hyperplane of E^{d+1} not passing through the origin O. Let H′_{i} be the hyperplane spanned by O and H_{i}. Choose the orientation of H′_{i} such that H_{i}^{′+} contains H_{i}^{+}. Then consider the spherical arrangement

A′ = {H′_{i} ∩ S^{d} | i ∈ {1,…, n}} .

Each vertex of A with weight k corresponds to a pair of antipodal vertices of A′ having weights k and n − d − k. Thus v_{k} ≤ v′_{k}, where v_{k} and v′_{k} denote the number of vertices of A and A′, respectively, having weight k. This proves the lemma, since on S^{d}, for d ≤ 3, the numbers g_{k} are the same for all polyhedral arrangements, as was already remarked in the introduction.

By the total weight of an arrangement A we understand the sum of the weights of all vertices of A. We shall use this notion in particular for subsets of arrangements consisting of d + 1 half-spaces, which we also call (d + 1)-subarrangements.

Lemma 2. Each (d + 1)-subarrangement of a polyhedral arrangement in E^{d} has total weight ≤ d − 1.

Proof. Let S be an arbitrary (d + 1)-subarrangement of A. For convenience, denote its elements by H_{0}^{+},…, H_{d}^{+}. By using a suitable affine coordinate system, we may suppose that H_{1},…, H_{d} are the coordinate hyperplanes and H_{0} has the equation x_{1} +…+x_{d} = 1. The total weight of S is clearly ≤ d + 1. If it were = d + 1, the half-spaces of S would be as follows:

H_{i}^{+} = \{ \begin{matrix}\{ x | x_{i} > 0\} & for 1 ≤ i ≤ d, \\ \{ x | ∑ x_{j} < 1\} & for i = 0. \end{matrix}

But then, evidently, P (S) would be empty, and thus P (A) would be also.

Now assume that the total weight of S is d. This means that exactly one of the half-spaces H_{0}^{+},…, H_{d}^{+} points “outward”, i.e. the simplex defined by the corresponding hyperplanes is not contained in it. Without loss of generality we may assume H_{0}^{+} to be this half-space. This means

H_{i}^{+} = \{ \begin{matrix}\{ x | x_{i} > 0\} & for 1 ≤ i ≤ d, \\ \{ x | ∑ x_{j} > 1\} & for i = 0. \end{matrix}

Since A is polyhedral, P (A) ∩ H_{0} ≠ ∅. But for each element x of this intersection, we would have x_{j} ≤ 0 (for each j) and ∑ x_{j} = 1, which is a contradiction.

We say a (d+1)-subarrangement {H_{i_{0}}^{+},…, H_{i_{d}}^{+}} of a moving arrangement A is switched at t_{0} ∈ (0, 1), if the hyperplanes H_{i_{0}}(t_{0}),…, H_{i_{d}}(t_{0}) intersect in a point (the switching point).

Lemma 3. In E^{d}, each (d + 1)-subarrangement of a moving arrangement is switched at most once.

Proof. Consider such a (d + 1)-subarrangement and denote it by {H_{0}^{+},…, H_{d}^{+}},

H_{i}^{+}(t) := {x ∈ E^{d} | u_{i} · x > β_{i} + γ_{i}t}

with u_{i} ∈ E^{d} \{O} and β_{i}, γ_{i} ∈ E. Denote by D(t) the determinant of the augmented coefficient matrix of the linear system

u_{i} · x = β_{i} + γ_{i}t, i ∈ {0,…, d} .

The subarrangement is switched at t_{0} if and only if this system has a solution, which implies D(t_{0}) = 0. Since D : t ⟶ D(t) is an affine function, this can occur for at most one t_{0} ∈ (0, 1).

If A = {H_{1}^{+},…, H_{n}^{+}} is a moving arrangement, we denote by g_{k}(t) the number of vertices having weight at most k in the arrangement

A(t) := {H_{1}^{+}(t),…, H_{n}^{+}(t)} .

If a subarrangement of A is switched at t_{0}, the terms “before the switching” and “after the switching” refer to the arrangements A(t_{0} − ϵ) and A(t_{0} + ϵ), respectively, with sufficiently small ϵ > 0.

Lemma 4. Let S be a (d + 1)-subarrangement of A which is switched at t_{0}. Let s be the total weight of S after the switching, and m the weight of the switching point (with respect to A(t_{0}) ). Then, for sufficiently small ϵ > 0,

g_{m}(t_{0} + ϵ) = g_{m}(t_{0} − ϵ) + d + 1 − 2s,

and the g_{k} with k ≠ m remain constant. In particular, g_{m} does not decrease at t_{0} if s ≤ (d + 1)/2.

Proof. Before the switching, the total weight of S is d + 1 − s. This means there are d + 1 − s vertices of S with weight m + 1 and s vertices with weight m. After the switching the situation is reversed, s vertices of S have weight m + 1 and d + 1 − s have weight m. This implies the lemma.

Proof of the theorem for d ≤ 3: Let A_{0} = {H_{1}^{+},…, H_{n}^{+}} be an arbitrary simple arrangement of half-spaces in E^{d}, d ≤ 3, and A_{1} the polyhedral arrangement which is obtained from A_{0} by translating the halfspaces such that they support the unit sphere S^{d−1}, which means A_{1} = {H_{1}^{′+},…, H_{n}^{′+}} with H_{i}^{′−} ⊃ S^{d−1}, H′_{i} parallel to H_{i} and tangent to S^{d−1}, for each i ∈ {1,…, n}. A_{0} and A_{1} uniquely determine a moving arrangement A such that A(0) = A_{0} and A(1) = A_{1}. By Lemma 2, each (d + 1)-subarrangement of A(1) has total weight ≤ d − 1 , which is ≤ (d + 1)/2 for d ≤ 3. Thus by Lemmas 3 and 4, g_{k}(0) ≤ g_{k}(1) for each k. Finally, by Lemma 1, the upper bounds of the theorem are valid for g_{k}(1) and thus also for g_{k}(0).

Proof of the theorem for d = 4: Let A = {H_{1}^{+},…, H_{n}^{+}} be a simple arrangement of half-spaces in E^{4}. For each i ∈ {1,…, n}, consider the 3-dimensional arrangement

A_{i} := { H_{j}^{+} ∩ H_{i} | j ∈ {1,…, n} \{i} } .

Since the theorem is already proved for d = 3, the number of vertices in A_{i} having weight at most k is bounded above by

G_{k,n−1} := (k + 1)(k + 2)(3(n − 1) − 2k − 6)/3.

Since there are n hyperplanes H_{i} and each vertex belongs to exactly 4 of them,

g_{k} ≤ n G_{k,n−1}/4 = (k + 1)(k + 2)(3n − 2k − 9)n/12.

Remark 1. By an argument analogous to that in the above proof for d = 4, the validity of the conjecture for any odd dimension d = 2m − 1 would imply its validity for the subsequent even dimension d = 2m.

Remark 2. The bound of our theorem is not attained for each cyclically polyhedral Euclidean arrangement (see the remark after the formulation of the conjecture). But there are “extremal” Euclidean arrangements, where g_{k} attains the upper bound for each k < (n − d)/2. In two dimensions, the arrangements generated by (almost) regular) polygons are extremal in this sense (cf. [6]). The following examples of extremal arrangements in E^{3} have been tested by computer for m ≤ 40:

a) Let V be a set of 2m points on the sphere S^{2}, consisting of the slightly perturbed vertices of an m-sided prism. If m is odd, the arrangement of planes touching the sphere in the points of V is extremal in the above sense. (Of course, the planes have to be oriented such that the sphere lies in the negative half-spaces.)

b) Similarly, we get an extremal arrangement of 2m planes for even m by the slightly perturbed vertices of an m-sided antiprism.

Acknowledgement. The author wishes to thank Martin Philipp (Salzburg), who has greatly helped him in preparing this paper and correcting several mistakes.

References

[1] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G.M. Ziegler, Oriented Matroids, Encyclopedia of Mathematics (Cambridge University Press, 1993).

[2] K.L. Clarkson, P.W. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom. 4 (1989), 387 - 421.

[3] H. Edelsbrunner, Algorithms in Combinatorial Geometry (Springer-Verlag, Berlin etc., 1987).

[4] B. Grünbaum, Convex Polytopes, John Wiley & Sons, London, 1967.

[5] J. Linhart, Arrangements of oriented hyperplanes, Discrete Comput. Geom. 10 (1993), 435 - 446.

[6] J. Linhart, On the total weight of arrangements of halfplanes, Geometriae dedicata 43 (1993), 165 - 172.

[7] J. Linhart, The weights of the vertices in arrangements of hemispheres. Discrete Math. (submitted).

[8] P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179 - 184.

[9] K. Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete Comput. Geom. 6 (1991), 307 - 338.

[10] M. Philipp, Combinatorial properties of arrangements of halfspaces, Ph.D. Thesis, University of Salzburg, Austria, 1994.