Voronoi diagrams and Delaunay triangulations

DOI10.1142/8685zbMATH Open1295.52001OpenAlexW4300926135MaRDI QIDQ2854053FDOQ2854053

Authors: Franz Aurenhammer, Rolf Klein, Der-Tsai Lee 

Publication date: 17 October 2013

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

Recommendations

• scientific article; zbMATH DE number 1455125
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• scientific article; zbMATH DE number 1424293
• Voronoi diagrams and Delaunay triangulations: ubiquitous siamese twins
• scientific article; zbMATH DE number 1079755

zbMATH Keywords

clusteringcomputational complexityalgorithmDelaunay triangulationVoronoi diagrampath planningmedial axisminimal spanning treepower diagramconvex distancezone diagramalpha-shapebeta-skeletonleast square matching

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Complex systems: features, similarity and connectivity
• Power Diagrams: Properties, Algorithms and Applications
• Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity
• Near optimal minimal convex hulls of disks
• The higher-order Voronoi diagram of line segments
• QuickhullDisk: a faster convex hull algorithm for disks
• A note on visibility-constrained Voronoi diagrams
• On the complexity of higher order abstract Voronoi diagrams
• Hamiltonicity for convex shape Delaunay and Gabriel graphs
• Distributed partitioning algorithms for multi-agent networks with quadratic proximity metrics and sensing constraints
• On Bregman Voronoi diagrams
• Bregman Voronoi diagrams
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• The state of the art of Voronoi diagram research
• A multicellular model of intestinal crypt buckling and fission
• Heterogeneous domain decomposition method for high contrast dense composites
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Abstract Voronoi diagrams from closed bisecting curves
• Voronoi diagrams and arrangements
• The mixed center location problem
• Optimal recovery of integral operators and its applications
• Hierarchical Voronoi diagrams for spatial data indexing and paging
• Macroscopic damping model for structural dynamics with random polycrystalline configurations
• Cluster size distributions of extreme values for the Poisson-Voronoi tessellation
• Mitered offsets and skeletons for circular arc polygons
• Voronoi polygons and polyhedra
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms
• Stabbing circles for sets of segments in the plane
• Nearest-neighbor searching under uncertainty. I
• Spatial context. An introduction to fundamental computer algorithms for spatial analysis
• On triangulation axes of polygons
• Geometric relations among Voronoi diagrams
• Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations. I. Theoretical foundations
• Non-simplicial Delaunay meshing via approximation by radical partitions
• Title not available (Why is that?)
• Parallel computation of alpha complexes for biomolecules
• Title not available (Why is that?)
• Title not available (Why is that?)
• Centroidal Power Diagrams, Lloyd's Algorithm, and Applications to Optimal Location Problems
• On clustering induced Voronoi diagrams
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations
• From proximity to utility: a Voronoi partition of Pareto optima
• Straight skeletons and mitered offsets of nonconvex polytopes
• Ideal hyperbolic polyhedra and discrete uniformization
• A randomized incremental approach for the Hausdorff Voronoi diagram of non-crossing clusters
• Convex-straight-skeleton Voronoi diagrams for segments and convex polygons
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• Title not available (Why is that?)
• Stable Delaunay graphs
• Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
• Voronoi diagrams and Delaunay triangulations: ubiquitous siamese twins
• Orphan-free anisotropic Voronoi diagrams
• Curved Voronoi diagrams
• Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams
• Constrained clustering via diagrams: a unified theory and its application to electoral district design
• Midsets and Voronoi type decomposition with respect to closed convex sets
• Separation by convex pseudo-circles
• On Voronoi diagrams and medial axes
• Forest-like abstract Voronoi diagrams in linear time
• Multiple covers with balls. II: Weighted averages
• Starshaped sets
• Voronoi diagrams on the sphere
• Asymptotic optimality of the triangular lattice for a class of optimal location problems
• Polygonal and Polyhedral Delaunay Meshing
• HERMES: persistent spectral graph software
• Minimizing the diameter of a spanning tree for imprecise points
• The hypermetric cone and polytope on eight vertices and some generalizations
• 10-Gabriel graphs are Hamiltonian
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• Enforcing essential boundary conditions on domains defined by point clouds
• Price competition with differentiated products on a two-dimensional plane: the impact of partial cartel on firms' profits and behavior
• Tropical bisectors and Voronoi diagrams
• Algorithms and Computation
• On 2-site Voronoi diagrams under geometric distance functions
• Discontinuous Galerkin method with Voronoi partitioning for quantum simulation of chemistry
• Data-driven selection of tessellation models describing polycrystalline microstructures
• Assessment of implicit adaptive mesh-free CFD modelling
• An invitation to tropical Alexandrov curvature
• On the Triangle-Perimeter Two-Site Voronoi Diagram
• The obnoxious competitive facility location model
• Title not available (Why is that?)
• The maximal degree in a Poisson-Delaunay graph
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• The obnoxious facilities planar \(p\)-median problem
• Extremely non-convex optimization problems: the case of the multiple obnoxious facilities location
• On the restricted 1-Steiner tree problem
• Union of hypercubes and 3D Minkowski sums with random sizes
• Union of hypercubes and 3D Minkowski sums with random sizes
• The \(\beta\)-Delaunay tessellation. III: Kendall's problem and limit theorems in high dimensions
• Title not available (Why is that?)
• Voronoi diagram for convex polygonal sites with convex polygon-offset distance function
• Voronoi Diagrams for Parallel Halflines and Line Segments in Space
• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• On groups \(G_n^k\) and \(\Gamma_n^k\): a study of manifolds, dynamics, and invariants
• Location problems with continuous demand and unreliable facilities: applications of families of incremental Voronoi diagrams
• A spatial extension of weather forecasts
• Review of obnoxious facilities location problems

This page was built for publication: Voronoi diagrams and Delaunay triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2854053)