Voronoi Diagrams and Delaunay Triangulations

DOI10.1142/8685zbMath1295.52001OpenAlexW4300926135MaRDI QIDQ2854053

Franz Aurenhammer, Rolf Klein, Der-Tsai Lee

Publication date: 17 October 2013

Full work available at URL: https://doi.org/10.1142/8685

algorithm computational complexity clustering power diagram path planning Voronoi diagram Delaunay triangulation medial axis minimal spanning tree convex distance zone diagram alpha-shape beta-skeleton least square matching

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Continuous location (90B85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Combinatorial aspects of tessellation and tiling problems (05B45) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) Combinatorial complexity of geometric structures (52C45)

Related Items

Enforcing essential boundary conditions on domains defined by point clouds, Complex systems: features, similarity and connectivity, Distributed partitioning algorithms for multi-agent networks with quadratic proximity metrics and sensing constraints, Extremely non-convex optimization problems: the case of the multiple obnoxious facilities location, Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing, Optimal recovery of integral operators and its applications, The mixed center location problem, Minkowski Geometry—Some Concepts and Recent Developments, Macroscopic damping model for structural dynamics with random polycrystalline configurations, Cluster size distributions of extreme values for the Poisson-Voronoi tessellation, Empirical Voronoi wavelets, The -Delaunay tessellation: Description of the model and geometry of typical cells, Centroidal Power Diagrams, Lloyd's Algorithm, and Applications to Optimal Location Problems, From proximity to utility: a Voronoi partition of Pareto optima, Straight skeletons and mitered offsets of nonconvex polytopes, Competitive Online Routing on Delaunay Triangulations, Non-simplicial Delaunay meshing via approximation by radical partitions, Nearest-neighbor searching under uncertainty. I, Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models, Review of obnoxious facilities location problems, Deletion in abstract Voronoi diagrams in expected linear time and related problems, A note on visibility-constrained Voronoi diagrams, Power diagram detection with applications to information elicitation, Ideal hyperbolic polyhedra and discrete uniformization, Fitting Spherical Laguerre Voronoi Diagrams to Real-World Tessellations Using Planar Photographic Images, The Mixed Center Location Problem, The discrete and mixed minimax 2-center problems, Mean-to-max ratio of the torsion function and honeycomb structures, Constrained clustering via diagrams: a unified theory and its application to electoral district design, The obnoxious competitive facility location model, The $\beta$-Delaunay tessellation III: Kendall's problem and limit theorems in high dimensions, Unnamed Item, Unnamed Item, A spatial extension of weather forecasts, Forest-like abstract Voronoi diagrams in linear time, Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions, Stable Delaunay graphs, Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function, Parallel computation of alpha complexes for biomolecules, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Minimizing the diameter of a spanning tree for imprecise points, On triangulation axes of polygons, Starshaped sets, A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations, Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity, Union of Hypercubes and 3D Minkowski Sums with Random Sizes., Existence, uniqueness and regularity of the projection onto differentiable manifolds, Stabbing circles for sets of segments in the plane, A multicellular model of intestinal crypt buckling and fission, The hypermetric cone and polytope on eight vertices and some generalizations, The obnoxious facilities planar $p$-median problem, Heterogeneous domain decomposition method for high contrast dense composites, Asymptotic optimality of the triangular lattice for a class of optimal location problems, Data-driven selection of tessellation models describing polycrystalline microstructures, On groups Gnk and Γnk: A study of manifolds, dynamics, and invariants, On the restricted 1-Steiner tree problem, Unnamed Item, Union of hypercubes and 3D Minkowski sums with random sizes, Separation by convex pseudo-circles, Location problems with continuous demand and unreliable facilities: applications of families of incremental Voronoi diagrams, On Kinetic Delaunay Triangulations, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Elastic-plastic deformation decomposition algorithm for metal clusters at the atomic scale, QuickhullDisk: a faster convex hull algorithm for disks, Convex-straight-skeleton Voronoi diagrams for segments and convex polygons, A random walk approach to transport in tissues and complex media: from microscale descriptions to macroscale models, Unnamed Item, The maximal degree in a Poisson-Delaunay graph, Near optimal minimal convex hulls of disks, Hamiltonicity for convex shape Delaunay and Gabriel graphs, Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity, A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon, Laguerre Voronoi diagram as a model for generating the tessellation patterns on the sphere, Persistent homology in $\ell_\infty$ metric, Affine invariant triangulations, HERMES: persistent spectral graph software, Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams, Tropical bisectors and Voronoi diagrams, Mitered Offsets and Skeletons for Circular Arc Polygons, Abstract Voronoi Diagrams from Closed Bisecting Curves, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, Discontinuous Galerkin method with Voronoi partitioning for quantum simulation of chemistry, Polygonal and Polyhedral Delaunay Meshing, Voronoi Diagrams for Parallel Halflines and Line Segments in Space, On the complexity of randomly weighted multiplicative Voronoi diagrams, Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended, 10-Gabriel graphs are Hamiltonian, On the complexity of higher order abstract Voronoi diagrams, The higher-order Voronoi diagram of line segments, On The Characterization and Uniqueness of Centroidal Voronoi Tessellations