Edelsbrunner, H.; O’Rourke, J.; Seidel, R. Constructing arrangements of lines and hyperplanes with applications. (English) Zbl 0603.68104 SIAM J. Comput. 15, 341-363 (1986). 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\). Cited in 3 ReviewsCited in 146 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68Q25 Analysis of algorithms and problem complexity 51M20 Polyhedra and polytopes; regular figures, division of spaces 52Bxx Polytopes and polyhedra 52A37 Other problems of combinatorial convexity Keywords:configurations; geometric transformation; combinatorial geometry; computational geometry; optimal algorithm; cell complex; Voronoi diagrams PDFBibTeX XMLCite \textit{H. Edelsbrunner} et al., SIAM J. Comput. 15, 341--363 (1986; Zbl 0603.68104) Full Text: DOI