Constructing arrangements of lines and hyperplanes with applications

H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986) 341–363.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
A finite set of lines partitions the Euclidean plane into a cell complex. Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions $d$-dimensional Euclidean space. An algorithm is presented that constructs a representation for the cell complex defined by $n$ hyperplanes in optimal $O(n^d )$ time in $d$ dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to lead to new methods for computing $\lambda $-matrices, constructing all higher-order Voronoi diagrams, halfspatial range estimation, degeneracy testing, and finding minimum measure simplices. In all five applications, the new algorithms are asymptotically faster than previous results, and in several cases are the only known methods that generalize to arbitrary dimensions. The algorithm also implies an upper bound of $2^{cn^d } $, $c$ a positive constant, for the number of combinatorially distinct arrangements of $n$ hyperplanes in $E^d $. © 1986 Society for Industrial and Applied Mathematics
Publishing Year
Date Published
1986-01-01
Journal Title
SIAM Journal on Computing
Volume
15
Issue
2
Page
341 - 363
IST-REx-ID

Cite this

Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 1986;15(2):341-363. doi:10.1137/0215024
Edelsbrunner, H., O’Rourke, J., & Seidel, R. (1986). Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 15(2), 341–363. https://doi.org/10.1137/0215024
Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing 15, no. 2 (1986): 341–63. https://doi.org/10.1137/0215024.
H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of lines and hyperplanes with applications,” SIAM Journal on Computing, vol. 15, no. 2, pp. 341–363, 1986.
Edelsbrunner H, O’Rourke J, Seidel R. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 15(2), 341–363.
Edelsbrunner, Herbert, et al. “Constructing Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 341–63, doi:10.1137/0215024.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar