---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Raimund
foaf_name: Seidel, Raimund
foaf_surname: Seidel
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
bibo_doi: 10.1007/BFb0038185
bibo_volume: 555
dct_date: 1991^xs_gYear
dct_publisher: Springer@
dct_title: On the zone theorem for hyperplane arrangements@
...