@inproceedings{4054,
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 ge 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. Our proof is based on an inductive argument, which also applies in the case of pseudo-hyperplane arrangements. We also briefly discuss the fallacies of the old proof along with some ways of partially saving that approach.},
author = {Edelsbrunner, Herbert and Seidel, Raimund and Sharir, Micha},
pages = {108 -- 123},
publisher = {Springer},
title = {{On the zone theorem for hyperplane arrangements}},
doi = {10.1007/BFb0038185},
volume = {555},
year = {1991},
}