On the zone theorem for hyperplane arrangements Journal Article


Author(s): Edelsbrunner, Herbert; Seidel, Raimund; Sharir, Micha
Article Title: On the zone theorem for hyperplane arrangements
Affiliation
Abstract: The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n(d-1)). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d greater-than-or-equal-to 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.
Keywords: arrangements; discrete and computational geometry; hyperplanes; zones; counting faces; induction; sweep
Journal Title: SIAM Journal on Computing
Volume: 22
Issue 2
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 1993-04-01
Start Page: 418
End Page: 429
Sponsor: National Science Foundation under grant CCR-89- 21421.
DOI: 10.1137/0222031
Open access: no
IST Austria Authors
Related IST Austria Work