@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}, }