Edelsbrunner, HerbertIST Austria ; Seidel, Raimund; Sharir, Micha
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.
SIAM Journal on Computing
National Science Foundation under grant CCR-89- 21421.
418 - 429
Edelsbrunner H, Seidel R, Sharir M. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. 1993;22(2):418-429. doi:10.1137/0222031
Edelsbrunner, H., Seidel, R., & Sharir, M. (1993). On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222031
Edelsbrunner, Herbert, Raimund Seidel, and Micha Sharir. “On the Zone Theorem for Hyperplane Arrangements.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222031.
H. Edelsbrunner, R. Seidel, and M. Sharir, “On the zone theorem for hyperplane arrangements,” SIAM Journal on Computing, vol. 22, no. 2. SIAM, pp. 418–429, 1993.
Edelsbrunner H, Seidel R, Sharir M. 1993. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. 22(2), 418–429.
Edelsbrunner, Herbert, et al. “On the Zone Theorem for Hyperplane Arrangements.” SIAM Journal on Computing, vol. 22, no. 2, SIAM, 1993, pp. 418–29, doi:10.1137/0222031.