Fully dynamic Delaunay triangulation in logarithmic expected per operation

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

Stefan Meiser, Monique Teillaud, Olivier Devillers

Publication date: 17 January 1993

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

zbMATH Keywords

randomized algorithmsdynamic algorithmsDelaunay triangulationDelaunay tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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