On the zone theorem for hyperplane arrangements

H. Edelsbrunner, R. Seidel, M. Sharir, SIAM Journal on Computing 22 (1993) 418–429.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
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 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.
Publishing Year
Date Published
1993-04-01
Journal Title
SIAM Journal on Computing
Acknowledgement
National Science Foundation under grant CCR-89- 21421.
Volume
22
Issue
2
Page
418 - 429
IST-REx-ID

Cite this

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, 22(2), 418–429. https://doi.org/10.1137/0222031
Edelsbrunner, Herbert, Raimund Seidel, and Micha Sharir. “On the Zone Theorem for Hyperplane Arrangements.” SIAM Journal on Computing 22, no. 2 (1993): 418–29. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar