A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes

Herbert Edelsbrunner, Georg Osang

Algorithmica · 2022 · 11 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

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.

References

22