Dynamic maintenance of geometric structures made easy
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 197-206
- https://doi.org/10.1109/sfcs.1991.185369
Abstract
The problem of dynamically maintaining geometric structures is considered. A technique is proposed that uses randomized incremental algorithms which are augmented to allow deletions of objects. A model for distributions on the possible input sequences of insertions and deletions is developed and analyzed using R. Seidel's backwards analysis. It is further shown how to apply this to maintain Voronoi diagrams, convex hulls, and planar subdivisions. A strikingly simple algorithm for the maintenance of convex hulls in any dimension is given. The expected running time is determined.Keywords
This publication has 20 references indexed in Scilit:
- Randomized incremental construction of delaunay and Voronoi diagramsPublished by Springer Nature ,2005
- Randomized multidimensional search trees: further results in dynamic samplingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Randomized multidimensional search trees: lazy balancing and dynamic shufflingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New results on dynamic planar point locationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On levels in arrangements and voronoi diagramsDiscrete & Computational Geometry, 1991
- On the construction of abstract voronoi diagramsDiscrete & Computational Geometry, 1991
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- An efficient algorithm for hidden surface removalPublished by Association for Computing Machinery (ACM) ,1989
- A fast planar partition algorithm, IIPublished by Association for Computing Machinery (ACM) ,1989
- A fast planar partition algorithm. IPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988