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

DOI10.1007/s00453-022-01027-6OpenAlexW3098889154MaRDI QIDQ2700389

Georg Osang, Herbert Edelsbrunner

Publication date: 21 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.03617

zbMATH Keywords

softwarealgorithmscomputational experimentsVoronoi tessellationsDelaunay mosaics

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

rhomboidtiling, Computing the multicover bifiltration

Uses Software

• CGAL
• GitHub
• orderkdelaunay

Cites Work

• Unnamed Item
• Geometric inference for probability measures
• Higher-dimensional Voronoi diagrams in linear expected time
• On levels in arrangements and Voronoi diagrams
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Voronoi diagrams and arrangements
• Applications of random sampling in computational geometry. II
• On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
• Witnessed \(k\)-distance
• Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes
• On the shape of a set of points in the plane
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• The Multi-cover Persistence of Euclidean Balls
• Complexity of the delaunay triangulation of points on surfaces the smooth case
• The maximum numbers of faces of a convex polytope
• A new duality result concerning Voronoi diagrams