A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case

DOI10.1016/S0925-7721(00)00017-1zbMath0971.68182WikidataQ127797727 ScholiaQ127797727MaRDI QIDQ1841245

C. Lemaire, J.-M. Moreau

Publication date: 22 February 2001

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

zbMATH Keywords

Delaunay triangulations

Mathematics Subject Classification ID

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

Related Items

Parallel Delaunay triangulation in three dimensions ⋮ Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions

Uses Software

• CGAL
• LEDA
• DeWall
• Triangle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay triangulation and the convex hull of n points in expected linear time
• Higher-dimensional Voronoi diagrams in linear expected time
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• Hashing lazy numbers
• DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\).
• A comparison of sequential Delaunay triangulation algorithms.
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two algorithms for constructing a Delaunay triangulation
• Multidimensional binary search trees used for associative searching
• An Algorithm for Finding Best Matches in Logarithmic Expected Time
• Geometry. I, II. Transl. from the French by M. Cole and S. Levy