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 α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.
Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.
Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 2023;85:277-295. doi:10.1007/s00453-022-01027-6
Edelsbrunner, H., & Osang, G. F. (2023). A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-022-01027-6
Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-022-01027-6.
H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay mosaics and alpha shapes,” Algorithmica, vol. 85. Springer Nature, pp. 277–295, 2023.
Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 85, 277–295.
Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” Algorithmica, vol. 85, Springer Nature, 2023, pp. 277–95, doi:10.1007/s00453-022-01027-6.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
2023_Algorithmica_Edelsbrunner.pdf 911.02 KB