Fully dynamic Delaunay triangulation in logarithmic expected per operation

DOI10.1016/0925-7721(92)90025-NzbMath0773.68066MaRDI QIDQ1199828

Olivier Devillers, Monique Teillaud, Stefan Meiser

Publication date: 17 January 1993

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

randomized algorithms; dynamic algorithms; Delaunay triangulation; Delaunay tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Dog Bites Postman, Markov incremental constructions, Four results on randomized incremental constructions, An introduction to randomization in computational geometry, Union and split operations on dynamic trapezoidal maps, Expected time analysis for Delaunay point location, A compact piecewise-linear Voronoi diagram for convex sites in the plane, THE DELAUNAY HIERARCHY, An extended finite element library

Cites Work

• On the construction of abstract Voronoi diagrams
• The design of dynamic data structures
• On levels in arrangements and Voronoi diagrams
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A sweepline algorithm for Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• On the randomized construction of the Delaunay tree
• Applications of random sampling in computational geometry. II
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two algorithms for constructing a Delaunay triangulation
• Design and implementation of an efficient priority queue
• Computing Dirichlet Tessellations in the Plane
• Four results on randomized incremental constructions
• Unnamed Item
• Unnamed Item