A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
From MaRDI portal
Publication:2366225
DOI10.1007/BF01228508zbMath0780.68109OpenAlexW1989130580MaRDI QIDQ2366225
Olivier Devillers, Jean-Daniel Boissonnat, Monique Teillaud
Publication date: 29 June 1993
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01228508
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
An introduction to randomization in computational geometry, A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams, Degree distributions in \(AB\) random geometric graphs, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, Higher order mobile coverage control with applications to clustering of discrete sets, Applications of random sampling to on-line algorithms in computational geometry, Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay, The \(k\)-nearest-neighbor Voronoi diagram revisited, Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes
Cites Work
- Unnamed Item
- On the construction of abstract Voronoi diagrams
- 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
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Applications of random sampling to on-line algorithms in computational geometry
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Constructing Arrangements of Lines and Hyperplanes with Applications
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Computing Dirichlet Tessellations in the Plane
