Edelsbrunner, HerbertISTA ; 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 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.
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.
108 - 123
New Results and New Trends in Computer Science
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)