ISSN:
1432-0541
Keywords:
Arrangements of planes
;
Power diagrams
;
Computational geometry
;
Asymptotic complexity
;
Dynamic data structures
;
Perturbation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840438
Permalink
