A simple algorithm for higher-order Delaunay mosaics and alpha shapes

Download
OA 2023_Algorithmica_Edelsbrunner.pdf 911.02 KB

Journal Article | Published | English

Scopus indexed
Department
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 α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.
Publishing Year
Date Published
2023-01-01
Journal Title
Algorithmica
Acknowledgement
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.
Volume
85
Page
277-295
ISSN
eISSN
IST-REx-ID
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2023-01-20
MD5 Checksum
71685ca5121f4c837f40c3f8eb50c915


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar