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

• DOI: 10.48550/arxiv.2011.03617
• Publication Date: 2022-08-28
• Authors: Herbert Edelsbrunner; Georg Osang
• Keywords: Computational Geometry (cs.CG); FOS: Computer and information sciences; Discrete Mathematics (cs.DM); G.2.1; 0102 computer and information sciences; 01 natural sciences; Article; 68U05; Computer Science - Computational Geometry; 0101 mathematics; Computer Science - Discrete Mathematics

AbstractWe 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 $$ α -shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.