Randomized incremental construction of Delaunay triangulations of nice point sets
type: Item
instance of: scholarly article
title: Randomized incremental construction of Delaunay triangulations of nice point sets
zbMATH Open document ID: 1467.52002
author: Jean-Daniel Boissonnat
author: Olivier Devillers
author: Kunal Dutta
author: Marc Glisse
published in: Discrete \& Computational Geometry
publication date: 2021-07-02T00:00:00Z
Mathematics Subject Classification ID: 52-08
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 52C15
Mathematics Subject Classification ID: 52C17
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 7367370
zbMATH Keywords: randomized incremental construction
zbMATH Keywords: Delaunay triangulations
zbMATH Keywords: Voronoi diagrams
zbMATH Keywords: flat torus
zbMATH Keywords: polyhedral surfaces
zbMATH Keywords: probabilistic analysis
MaRDI profile type: Publication
full work available at URL: s00454-020-00235-7
OpenAlex ID: W3085548081
cites work: Q2934705
cites work: Surface reconstruction by Voronoi filtering
cites work: Incremental constructions con BRIO
cites work: A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
cites work: Complexity of the delaunay triangulation of points on surfaces the smooth case
cites work: Q4827469
cites work: Smooth surface reconstruction via natural neighbour interpolation of distance functions
cites work: Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension
cites work: On the randomized construction of the Delaunay tree
cites work: Delaunay triangulations of closed Euclidean \(d\)-orbifolds
cites work: Applications of random sampling in computational geometry. II
cites work: Multiscale dissipative particle dynamics
cites work: RANDOMIZATION YIELDS SIMPLE O(n log⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
cites work: THE DELAUNAY HIERARCHY
cites work: Higher-dimensional Voronoi diagrams in linear expected time
cites work: The expected number of \(k\)-faces of a Voronoi diagram
cites work: Nice point sets can have nasty Delaunay triangulations
cites work: Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty''
cites work: Random Subdivisions of Space into Crystals
cites work: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
cites work: Q5824629
cites work: The Random Division of Space
cites work: A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations
cites work: A fast algorithm for well-spaced points and approximate delaunay graphs
cites work: Random tessellations in ℝd
cites work: Q4856179
cites work: Q3134498
DOI: 10.1007/S00454-020-00235-7
description: scientific article; zbMATH DE number 7367370