On the zone theorem for hyperplane arrangements
Edelsbrunner H, Seidel R, Sharir M. 1991. On the zone theorem for hyperplane arrangements. New Results and New Trends in Computer Science , LNCS, vol. 555, 108–123.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Edelsbrunner, HerbertISTA 
;
Seidel, Raimund;
Sharir, Micha
;
Seidel, Raimund;
Sharir, MichaSeries Title
LNCS
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.
Publishing Year
Date Published
1991-11-13
Publisher
Springer
Acknowledgement
Research of Herbert Edelsbrunner was supported by the National Science Foundation under grant CCR-89-21421. Raimund Seidel acknowledges support by an NSF Presidential Young Investigator Grant CCR-90-58440. Micha Sharir has been supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research of the Israeli Academy of Sciences.
Volume
555
Page
108 - 123
Conference
New Results and New Trends in Computer Science
IST-REx-ID
Cite this
Edelsbrunner H, Seidel R, Sharir M. On the zone theorem for hyperplane arrangements. In: Vol 555. Springer; 1991:108-123. doi:10.1007/BFb0038185
Edelsbrunner, H., Seidel, R., & Sharir, M. (1991). On the zone theorem for hyperplane arrangements (Vol. 555, pp. 108–123). Presented at the New Results and New Trends in Computer Science , Springer. https://doi.org/10.1007/BFb0038185
Edelsbrunner, Herbert, Raimund Seidel, and Micha Sharir. “On the Zone Theorem for Hyperplane Arrangements,” 555:108–23. Springer, 1991. https://doi.org/10.1007/BFb0038185.
H. Edelsbrunner, R. Seidel, and M. Sharir, “On the zone theorem for hyperplane arrangements,” presented at the New Results and New Trends in Computer Science , 1991, vol. 555, pp. 108–123.
Edelsbrunner H, Seidel R, Sharir M. 1991. On the zone theorem for hyperplane arrangements. New Results and New Trends in Computer Science , LNCS, vol. 555, 108–123.
Edelsbrunner, Herbert, et al. On the Zone Theorem for Hyperplane Arrangements. Vol. 555, Springer, 1991, pp. 108–23, doi:10.1007/BFb0038185.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar