DocumentCode :
2181225
Title :
Constructing arrangements of lines and hyperplanes with applications
Author :
Edelsbrunner, Herbert ; Rourke, Joseph O. ; Seidel, Raimund
fYear :
1983
fDate :
7-9 Nov. 1983
Firstpage :
83
Lastpage :
91
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0508-1
Type :
conf
DOI :
10.1109/SFCS.1983.11
Filename :
4568064
Link To Document :
بازگشت