Title :
Constructing arrangements of lines and hyperplanes with applications
Author :
Edelsbrunner, Herbert ; Rourke, Joseph O. ; Seidel, Raimund
Abstract :
An optimal algorithm is presented for constructing an arrangement of hyperplanes in arbitrary dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to improve known worst-case time complexities for five problems: computing all order-k Voronoi diagrams, computing the λ-matrix, estimating halfspace queries, degeneracy testing, and finding the minimum volume simplex determined by a set of points.
Keywords :
Application software; Computational geometry; Computer science; Data structures; Parallel processing; Testing;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.11