On the randomized construction of the Delaunay tree

DOI10.1016/0304-3975(93)90024-NzbMath0780.68110MaRDI QIDQ1210297

Monique Teillaud, Jean-Daniel Boissonnat

Publication date: 24 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Delaunay triangulationDelaunay tree

Mathematics Subject Classification ID

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

Related Items

Expected time analysis for Delaunay point location, An introduction to randomization in computational geometry, Incremental topological flipping works for regular triangulations, Kinetic Euclidean minimum spanning tree in the plane, Markov incremental constructions, Applications of random sampling to on-line algorithms in computational geometry, Fuzzy clustering using the convex hull as geometrical model, Fully dynamic Delaunay triangulation in logarithmic expected per operation, THE DELAUNAY HIERARCHY, A comparison of sequential Delaunay triangulation algorithms., Fast reconstruction of Delaunay triangulations, Unnamed Item, Kinetic and dynamic Delaunay tetrahedralizations in three dimensions, On lazy randomized incremental construction, Randomized incremental construction of Delaunay triangulations of nice point sets, Union and split operations on dynamic trapezoidal maps, Regular triangulations of dynamic sets of points, Dog Bites Postman

Cites Work

• On the complexity of d-dimensional Voronoi diagrams
• On the construction of abstract Voronoi diagrams
• Higher-dimensional Voronoi diagrams in linear expected time
• A sweepline algorithm for Voronoi diagrams
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• 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
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Convex hulls of finite sets of points in two and three dimensions
• Computing Dirichlet Tessellations in the Plane
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item