Related Experiment Video
Updated: Aug 13, 2025
08:21
Aesthetically Enhanced Silica Aerogel Via Incorporation of Laser Etching and Dyes
Published on: March 12, 2021
3.0K
A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes
Herbert Edelsbrunner1, Georg Osang1
1IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria.
Algorithmica
|January 23, 2023
Summary
We developed a straightforward algorithm for calculating higher-order Delaunay mosaics in any dimension. This method efficiently constructs complex mosaics using combinatorial operations and provides open-source tools for broader application.
Area of Science:
- Computational Geometry
- Topology
- Data Analysis
Background:
- Delaunay mosaics are fundamental structures in computational geometry.
- Higher-order Delaunay mosaics generalize standard Delaunay triangulations to higher dimensions and orders.
- Efficient algorithms are needed for their computation and application.
Purpose of the Study:
- To present a simple, generalizable algorithm for computing higher-order Delaunay mosaics.
- To extend the algorithm for computing higher-order shapes.
- To provide open-source implementations and analyze mosaic properties.
Main Methods:
- An incremental approach selecting vertices from lower-order mosaics.
- Utilizing a black-box algorithm for weighted first-order Delaunay mosaics.
- Employing combinatorial operations for constructing higher-order mosaics.
Main Results:
- A computationally simple algorithm for higher-order Delaunay mosaics in any finite dimension.
- Extension of the algorithm to compute higher-order shapes.
- Open-source implementations are available for practical use.
Conclusions:
- The presented algorithm offers an accessible method for generating higher-order Delaunay mosaics.
- The combinatorial approach simplifies implementation and extends applicability.
- Experimental results demonstrate the utility for analyzing random point sets.
