Fully dynamic Delaunay triangulation in logarithmic expected per operation
From MaRDI portal
Publication:1199828
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)
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