Algorithmica · 2022 · 11 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryDelaunay TriangulationsFinite GeometryGeometry ProcessingDelaunay Triangulation AlgorithmsIncremental Delaunay TriangulationSimple AlgorithmWeighted Delaunay Triangulation
Abstract We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order- k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order- k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> -shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.
22
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Computing Dirichlet tessellations
Adrian Bowyer · The Computer Journal · 1981 · 1.1K citations · Full text
Michael Ian Shamos, Dan Hoey · 1975 · 1.1K citations