Voronoi diagrams and arrangements

DOI10.1007/BF02187681zbMath0598.52013OpenAlexW2035774625MaRDI QIDQ1079823

Raimund Seidel, Herbert Edelsbrunner

Publication date: 1986

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/130979

zbMATH Keywords

survey algorithm hyperplane and paraboloid arrangements order-equivalent function collections Voronoi diagram with respect to \(f_ E\)- arrangements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Inequalities and extremum problems involving convexity in convex geometry (52A40) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items

Adaptive, anisotropic and hierarchical cones of discrete convex functions, Computing circular separability, Abstract Voronoi diagram in 3-space, ``The big sweep: On the power of the wavefront approach to Voronoi diagrams, Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\), The Voronoi inverse mapping, Abstract Voronoi diagrams revisited, Almost tight upper bounds for lower envelopes in higher dimensions, Edge-skeletons in arrangements with applications, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, On the two-dimensional Davenport-Schinzel problem, Tetrahedrizing point sets in three dimensions, Computing the volume of the union of spheres, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, On the geodesic Voronoi diagram of point sites in a simple polygon, On-line construction of the upper envelope of triangles and surface patches in three dimensions, Non-simplicial Delaunay meshing via approximation by radical partitions, An upper bound on the shortness exponent of inscribable polytopes, On Delaunay oriented matroids for convex distance functions, Degree distributions in \(AB\) random geometric graphs, Topological relations between separating circles, “The big sweep”: On the power of the wavefront approach to Voronoi diagrams, An interface-fitted mesh generator and virtual element methods for elliptic interface problems, Perturbations for Delaunay and weighted Delaunay 3D triangulations, Incremental Voronoi diagrams, On one approach to the estimation of a triangular element degeneration in a triangulation, Sensitivity analysis and tailored design of minimization diagrams, Constrained clustering via diagrams: a unified theory and its application to electoral district design, Straight skeletons for general polygonal figures in the plane, Arrangements on parametric surfaces. I: General framework and infrastructure, Arrangements on parametric surfaces. II: Concretizations and applications, Constructing Voronoi diagrams from hollow spheres using conformal geometric algebra, A framework for controllable Pareto front learning with completed scalarization functions and its applications, Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance, Range minima queries with respect to a random permutation, and approximate range counting, Computing the multicover bifiltration, Farthest-point Voronoi diagrams in the presence of rectangular obstacles, Asymmetric tropical distances and power diagrams, A generic topology library, The overlay of minimization diagrams in a randomized incremental construction, Finding nearest neighbors with Voronoi tessellations, Parallel computation of alpha complexes for biomolecules, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, On the Optimality of the FCC Lattice for Soft Sphere Packing, A simple algorithm for higher-order Delaunay mosaics and alpha shapes, Efficient mesh optimization schemes based on optimal Delaunay triangulations, Constructing the relative neighborhood graph in 3-dimensional Euclidean space, An axiomatic approach to Voronoi-diagrams in 3D, A parallel algorithm based on convexity for the computing of Delaunay tessellation, Three-dimensional convex hull as a fruitful source of diagrams, Stabbing circles for sets of segments in the plane, Piecewise linear interpolants to Lagrange and Hermite convex scattered data, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Randomized incremental construction of abstract Voronoi diagrams, Algorithms for weak and wide separation of sets, Convexity preserving interpolation and Powell-Sabin elements, CONFORMAL GEOMETRY OF ESCORT PROBABILITY AND ITS APPLICATIONS, On bisectors for different distance functions, General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties, A comparison of sequential Delaunay triangulation algorithms., The upper envelope of Voronoi surfaces and its applications, Witness (Delaunay) graphs, VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FRÉCHET DISTANCE, The multi-cover persistence of Euclidean balls, FURTHEST SITE ABSTRACT VORONOI DIAGRAMS, DATA GENERATION FOR GEOMETRIC ALGORITHMS ON NON-UNIFORM DISTRIBUTIONS, Fully Inverse Parametric Linear/Quadratic Programming Problems via Convex Liftings, A step in the Delaunay mosaic of order \(k\), Conformal Flattening on the Probability Simplex and Its Applications to Voronoi Partitions and Centroids, On overlays and minimization diagrams, Construction of Voronoi diagrams in the plane by using maps, On the construction of abstract Voronoi diagrams, New applications of random sampling in computational geometry, Ready, set, go! The Voronoi diagram of moving points that start from a line, THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS, Computing the topology of Voronoï diagrams of parallel half-lines, The Multi-cover Persistence of Euclidean Balls, A lower bound on Voronoi diagram complexity., Abstract Voronoi Diagrams from Closed Bisecting Curves, An optimal convex hull algorithm in any fixed dimension, Toughness and Delaunay triangulations, Higher-dimensional Voronoi diagrams in linear expected time, On levels in arrangements and Voronoi diagrams, Polygonal and Polyhedral Delaunay Meshing, Triangulations in CGAL, Heterogeneous locational optimisation using a generalised Voronoi partition, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, Finding extreme points in three dimensions and solving the post-office problem in the plane, Fast segment insertion and incremental construction of constrained Delaunay triangulations, Optimal partitioning for spatiotemporal coverage in a drift field

Cites Work