On Zones of Flats in Hyperplane Arrangements

Michael E. Houle* and Takeshi Tokuyama**

*Department of Information Science, University of Tokyo Bunkyo-ku, Tokyo 113, Japan **IBM Research, Tokyo Research Laboratory, Chiyoda-ku, Tokyo 102, Japan

Abstract Let H be a set of n hyperplanes in R^{d}, let A(H) be its arrangement, and let b be an m-dimensional flat. The zone of b in the arrangement A(H) is the set of open d-dimensional cells of A(H) which are intersected by b. We prove that the maximum number of incidences of k-cofaces of the arrangement with cells of the zone is O(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}ϕ_{k,d,m}(n)), where ϕ_{k,d,m}(n) = log n if m ≥ 1, d+m is odd, d−m ≥ 3 and k ≥ ⌈\frac{d−m}{2}⌉; otherwise, ϕ_{k,d,m}(n) = 1. A constructive lower bound of Ω(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}) is also shown. The bounds apply equally well to pseudo-arrangements and zones of pseudo-flats.

1 Introduction

Let H be a set of n hyperplanes in d-dimensional space, and let b be some other hyperplane. In the arrangement A(H) formed by H, the zone Z(H, b) of b is the set of open d-dimensional cells intersected by b. The complexity of a zone may be evaluated as follows. First, let us define a border of the arrangement to be a pair (f, C) such that C is a cell of the arrangement, and f is a face in the closure of C. If f is a k-coface (a face of co-dimension k or dimension d − k), then we say that (f, C) is a k-border of A(H). The k-complexity of a zone is thus the number of k-borders (f, C) such that C is a cell of the zone.

In the analysis of their incremental algorithm for constructing an arrangement of hyperplanes, Edelsbrunner, O’Rourke and Seidel [7, 5] were the first to consider the complexity of a zone. In what has come to be known as the Zone Theorem, they stated that the maximum k-complexity of a zone of a hyperplane, taken over all arrangements of n hyperplanes in R^{d}, is Θ(n^{d−1}) — assuming that d is treated as a fixed quantity. Recently, however, Edelsbrunner, Seidel and Sharir [6] discovered that their proof was in fact incorrect, even though the Zone Theorem itself is true. In the same paper, they provided a correct proof based on a very elegant technique leading to a recurrence relation in n and d, which they solve by induction.

In this paper, instead of zones of hyperplanes, we shall consider zones of flats (affine subspaces) of any dimension. As in the case of zones of hyperplanes, the zone Z(H, b) of an m-flat b in an arrangement A(H) is the set of open cells of A(H) which intersect b. We shall refer to such zones as m-zones. The k-complexity of Z(H, b) shall be denoted by z_{k}(H, b); in R^{d}, the maximum of z_{k}(H, b) over all sets of n hyperplanes H and all m-flats b shall be denoted by z_{k}(n, d, m). The main result of this paper is the following:

Theorem 1 (Zone Theorem for Flats)

z_{k}(n, d, m) = O(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}ϕ_{k,d,m}(n)),
= Ω(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}),

where

ϕ_{k,d,m}(n) = \{ \begin{matrix}log n & if m ≥ 1, d + m is odd, d − m ≥ 3 and k ≥ ⌈\frac{d−m}{2}⌉; \\ 1 & otherwise. \end{matrix}

The Zone Theorem for flats could be thought to link the asymptotic versions of three wellknown combinatorial theorems: the face-count formulae for hyperplane arrangements (the case m = d, due to Buck [4, 5]), the “classical” Zone Theorem (the case m = d − 1), and the Upper Bound Theorem for convex polytopes (the case m = 0, due to McMullen [8]).

The upper bound on z_{k}(n, d, m) shall be proved in the next section, using a slightly modified version of the powerful recurrence relation of [6]. Although the technique which leads to such recurrences is still new, its importance has already been demonstrated in applications to related problems in combinatorial geometry. Aronov, Matoušek and Sharir [1] used this tool to show that the sum of squares of the total complexities of the cells of an arrangement is O(n^{d} log^{⌊ \frac{d}{2} ⌋−1} n), a result that has many applications of its own. Aronov and Sharir [2] employed the technique to obtain a bound of O(n^{d−1} log n) for the total complexity of the zone of a low-degree (d − 1)-dimensional algebraic surface. More recently, Pellegrini [9] extended the approach of Aronov and Sharir to obtain an upper bound on the total complexity of lowdegree algebraic surfaces of any dimension. Applied to the total complexity of zones of flats, Pellegrini’s more general bounds match ours; however, they do not match our bounds on the k-complexity when k is small.

In Section 3, we shall establish the lower bound on the complexity of an m-zone, by exhibiting a set of hyperplanes H and an m-flat b for which this bound is tight. We then conclude our discussion in Section 4.

2 The Upper Bound

For the proofs of this section, we shall consider only those sets of hyperplanes H and m-flats b which are in general position; that is, where every j hyperplanes intersect in a (d − j)-flat, for 1 ≤ j ≤ d + 1, and where every j hyperplanes together with b intersect in an (m − j)-flat, for 1 ≤ j ≤ m + 1. Clearly, if H and b are not in general position, b and the hyperplanes of H may be perturbed to obtain a new flat b′ and a new set H′ in general position such that z_{k}(H′, b′) ≥ z_{k}(H, b).

For the case m = d − 1, the recurrence of the following lemma was first obtained by Edelsbrunner, Seidel, and Sharir [6]. Although the proof for the more general case is virtually identical to their proof, we repeat it here for the sake of clarity and completeness.

Lemma 2 For d ≥ 2, m > 0, 0 ≤ k < d, and n > k,

z_{k}(n, d, m) ≤ \frac{n}{n − k} [z_{k}(n − 1, d, m) + z_{k}(n − 1, d − 1, m − 1)] .

Proof Let H be a set of n hyperplanes in R^{d}, and let b be an m-flat. We assume that H and b are in general position. Given some hyperplane h ∈ H, we define H_{h} to be the set H \ {h}, and H/h to be {h′ ∩ h | h′ ∈ H_{h}}. Note that H/h forms a (d − 1)-dimensional arrangement of n − 1 “hyperplanes” within h. In addition, we define b/h to be the (m − 1)-flat b ∩ h.

We now consider the effect on z_{k}(H_{h}, b) when h is reinserted into the arrangement A(H_{h}). In particular, let us consider its effect on the k-border (f, C) of Z(H_{h}, b). Note that since H is in general position, f is not contained in h. We distinguish three cases:

Case 1: h ∩ C = ∅. The k-border (f, C) is also a border of Z(H, b).

Case 2: h ∩ C ≠ ∅ but h ∩ f = ∅. Let h_{f} be the (open) halfspace bounded by h that contains f, and let C′ = C ∩h_{f}. If C′ intersects b, then (f, C) gives rise to one k-border in Z(H, b), namely (f, C′); otherwise it gives rise to none.

Case 3: h ∩ C ≠ ∅ and h ∩ f ≠ ∅. Let C′ and C′′ be the two cells of A(H) that result from the splitting of C by h. If only one of C′ and C′′ intersect b, say C′, then (f, C) gives rise to one k-border in Z(H, b). However, if both C′ and C′′ intersect b, then (f, C) gives rise to two k-borders. However, one of the two may be counted as if it were a k-border of Z(H/h, b/h), since C ∩ h must contain b/h, and must have f ∩ h in its closure.

Since these three cases cover all k-borders (f, C) in Z(H, b) that are not contained in h, the number of such k-borders is at most z_{k}(H_{h}, b) + z_{k}(H/h, b/h). Summing this quantity over all choices of h, we obtain

(n − k)z_{k}(H, b) ≤ ∑_{h∈H} (z_{k}(H_{h}, b) + z_{k}(H/h, b/h)) ,

since every k-border in Z(H, b) is counted n − k times, once for each hyperplane of H that does not contain f. From this, the lemma follows. □

To solve the recurrence of Lemma 2, we resort to a proof which is inductive in both n and m. The induction basis follows from the fact that z_{k}(n, d, 0) is specified exactly by the Upper Bound Theorem. However, for m > 1 a direct solution of the recurrence does not yield a satisfactory bound for those cases where k is large. The next lemma allows us to avoid the expansion of the recurrence when it would lead to an inflated upper bound.

Lemma 3 Given fixed values of n, d, and m, if there exists some function ψ(n) such that z_{k}(n, d, m) = O(ψ(n)) for 0 ≤ k ≤ ⌊\frac{d}{2}⌋, then z_{k}(n, d, m) = O(ψ(n)) for all 0 ≤ k ≤ d.

Proof (sketch) For any convex polytope, the Dehn-Sommerville relations yield ⌊\frac{d}{2}⌋ independent linear equations, whose variables are the number of k-cofaces of the polytope, and whose coefficients are independent of n. The result follows from the fact that the Dehn-Sommerville equations are additive over all cells of a zone. □

Information concerning the Dehn-Sommerville relations may be found in many places in the literature, including [5, 8].

We are now ready for the proof of the upper bound:

Theorem 4 z_{k}(n, d, m) = O(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}ϕ_{k,d,m}(n)), where

ϕ_{k,d,m}(n) = \{ \begin{matrix}log n & if m ≥ 1, d + m is odd, d − m ≥ 3 and k ≥ ⌈\frac{d−m}{2}⌉; \\ 1 & otherwise. \end{matrix}

Proof For d = 1, the theorem holds trivially. For d = 2, the theorem is already known to hold (see [5] for one example of the many different proofs), and for m = 0, it follows from the Upper Bound Theorem. Let us therefore assume that for the remainder of this proof, n > d > 2 and m > 0.

The recurrence of Lemma 2 may be expanded to yield

z_{k}(n, d, m) ≤ \begin{matrix}( & {n \atop k} & ) \\ ( & {d \atop k} & ) \end{matrix}z_{k}(d, d, m) + ∑_{j=d}^{n−1} \begin{matrix}( & {n \atop k} & ) \\ ( & {j \atop k} & ) \end{matrix}z_{k}(j, d − 1, m − 1).

Note that the number of inductive applications of the above recurrence will be exactly m, and thus the “constants” of proportionality are independent of n.

First, let us consider the case where m = 1. We distinguish between the subcases k ≤ ⌊\frac{d}{2}⌋ and k > ⌊\frac{d}{2}⌋. In the former subcase, the Upper Bound Theorem yields

z_{k}(n, d, 1) = O(n^{k}) + O(n^{k} · ∑_{j=d}^{n−1} j^{min\{k,⌊ \frac{d−1}{2} ⌋\}−k}).

If d is even and k = ⌊\frac{d}{2}⌋ (= ⌈\frac{d−m}{2}⌉), then min\{k, ⌊\frac{d−1}{2}⌋\} − k = −1, and therefore

z_{k}(n, d, 1) = O(n^{⌊ \frac{d}{2} ⌋} log n)
= O(n^{min\{k+1,⌊ \frac{d+1}{2} ⌋\}} log n).

Otherwise, min\{k, ⌊\frac{d−1}{2}⌋\} − k ≥ 0, and

z_{k}(n, d, 1) = O(n^{min\{k+1,⌊ \frac{d+1}{2} ⌋\}}).

Thus the theorem can be seen to hold for the case where m = 1 and k ≤ ⌊\frac{d}{2}⌋. For the case when k > ⌊\frac{d}{2}⌋, the bounds for the values of k less than or equal to ⌊\frac{d}{2}⌋ imply, together with Lemma 3, that the theorem holds for all values of k.

Consider now the case where m > 1. If the three conditions d − m ≥ 3, d + m is odd, and k ≥ ⌈\frac{d−m}{2}⌉ all hold, then the conditions (d − 1) − (m − 1) ≥ 3, (d − 1) + (m − 1) is odd, and k ≥ ⌈\frac{(d−1)−(m−1)}{2}⌉ also hold. If any one of the former conditions is violated, then one of the latter conditions is also violated. With this observation, the inductive hypothesis can be applied to the recurrence

z_{k}(n, d, m) ≤ \begin{matrix}( & {n \atop k} & ) \\ ( & {d \atop k} & ) \end{matrix}z_{k}(d, d, m) + ∑_{j=d}^{n−1} \begin{matrix}( & {n \atop k} & ) \\ ( & {j \atop k} & ) \end{matrix}z_{k}(j, d − 1, m − 1).

for the subcase k ≤ ⌊\frac{d}{2}⌋, as follows:

z_{k}(n, d, m) = O(n^{k}) + O(n^{k} · ∑_{j=d}^{n−1} j^{min\{m−1,⌊ \frac{d+m}{2} ⌋−1−k\}}ϕ_{k,d−1,m−1}(j))
= O(n^{k} + n^{k} · n^{min\{m,⌊ \frac{d+m}{2} ⌋−k\}}ϕ_{k,d,m}(n))
= O(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}ϕ_{k,d,m}(n)).

Note that if m > 1 and k ≤ ⌊\frac{d}{2}⌋, the expression min\{m − 1, ⌊\frac{d+m}{2}⌋ − 1 − k\} is always nonnegative. □

3 The Lower Bound

Having proved an upper bound for z_{k}(n, d, m), we now prove that in certain cases, it is tight.

Theorem 5 z_{k}(n, d, m) = Ω(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}).

Proof By construction. The lower bound is known to hold whenever d ≤ 2, k = 0, m = 0, or m ≥ d − 1. Let us consider the case where d > 2 and m ≤ d − 2.

Let A(H_{m}) be an arrangement of \frac{n}{2} hyperplanes in R^{m} such that the hyperplanes of H_{m} are in general position. Next, consider the arrangement A(H_{d−m}) of \frac{n}{2} hyperplanes in R^{d−m} avoiding the origin, such that the cell C containing the origin has Θ(n^{min\{k,⌊ \frac{d−m}{2} ⌋\}}) bounding k-cofaces; the existence of such a polytope is guaranteed by the Upper Bound Theorem.

We now construct a new arrangement A(H) in R^{d} whose hyperplanes are h′ × R^{d−m} for h ∈ H_{m}, and R^{m} × h′′ for h′′ ∈ H_{d−m}. Let b be the m-flat R^{m} × 0^{d−m}, where 0^{d−m} is the origin of R^{d−m}. Clearly, the Cartesian product of every face of A(H_{m}) with C is a cell of A(H) contained in the zone of b.

We shall count the number of k-borders f of Z(H, b) such that j = min{k, d − m} of the k hyperplanes containing f derive from A(H_{d−m}). Each j-border of C in A(H_{d−m}) gives rise to Θ(n^{m}) such k-borders of A(H), one for every (k − j)-border in A(H_{m}). The total number of such k-borders is thus

Θ(n^{m}) · Θ(n^{min\{j,⌊ \frac{d−m}{2} ⌋\}}) = Θ(n^{min\{k+m,⌊ \frac{d+m}{2} ⌋\}}),

which proves the lower bound. □

4 Discussion

Although for some choices of k, d, and m a gap of log n exists between the upper and lower bounds, we conjecture that the lower bound is tight. The problem of whether the log n factor can be eliminated is still very much open.

As did those of [6], the proofs of this paper do not exploit the linearity of the hyperplanes or flats — only the combinatorial properties of their intersections. For this reason, the Zone Theorem for flats also applies to arrangements of pseudo-hyperplanes and zones of pseudo-flats (formed from the intersection of pseudo-hyperplanes) [3].

The original Zone Theorem of [7] was based on a slightly different definition of a zone, where a cell C was considered to be in the zone of hyperplane b if its closure intersected b. This definition is not equivalent to that used in this paper; under the closed-cell definition, the maximum complexity of an m-zone of an arrangement of n hyperplanes in R^{d} is Ω(n^{d−1}), for all m < d. To see that this is indeed true, consider the case where b and all the hyperplanes of H contain the origin: every k-border of A(H) belongs to Z(H, b). On the other hand, the closed-cell definition is equivalent to the open-cell definition if H is in general position.

References

[1] Aronov, B., Matoušek, J., and Sharir, M. On the Sum of Squares of Cell Complexities in Hyperplane Arrangements, in “Proc. 7^{th} Annual ACM Symposium on Computational Geometry” (1991), pp. 307-313.

[2] Aronov, B. and Sharir, M. On the Zone of a Surface in a Hyperplane Arrangement, manuscript, 1991.

[3] Björner, A., Las Vergnas, M., Sturmfels, B., White, N., and Ziegler, G. Oriented Matroids, book in preparation.

[4] Buck, R. C. Partition of Space, Amer. Math. Monthly 50 (1943), pp. 541-544.

[5] Edelsbrunner, H. Algorithms in Combinatorial Geometry, Brauer, W., Rozenberg, G., and Salomaa, A., eds., Springer-Verlag, Berlin, 1987.

[6] Edelsbrunner, H., Seidel, R., and Sharir, M. On the Zone Theorem for Hyperplane Arrangements, manuscript, 1991.

[7] Edelsbrunner, H., O’Rourke, J., and Seidel, R. Constructing Arrangements of Lines and Hyperplanes with Applications, SIAM J. Comput. 15 (1986), pp. 341-363.

[8] McMullen, P. and Shephard, G. C. Convex Polytopes and the Upper Bound Conjecture, London Math. Soc. Lec. Note 3, Cambridge Univ. Press, 1971.

[9] Pellegrini, M. On the Zone of a Co-dimension p Surface in a Hyperplane Arrangement, in “Proc. 3^{rd} Canadian Conf. on Computational Geometry,” Vancouver, Aug. 1991, pp. 307-313.