Voronoi diagrams from convex hulls

DOI10.1016/0020-0190(79)90074-7zbMath0424.68036OpenAlexW1984406695WikidataQ56070313 ScholiaQ56070313MaRDI QIDQ1135110

Kevin Q. Brown

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90074-7

zbMATH Keywords

convex hullcomputational geometryalgorithm for constructing a planar Euclidean VoronoiK-dimensional Euclidean Voronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Discrete mathematics in relation to computer science (68R99)

Related Items (66)

Voronoi diagrams and arrangements ⋮ Abstract Voronoi diagram in 3-space ⋮ ``The big sweep: On the power of the wavefront approach to Voronoi diagrams ⋮ About \(f\)-vectors of inscribed simplicial polytopes ⋮ Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\) ⋮ An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram ⋮ Edge insertion for optimal triangulations ⋮ Planar realizations of nonlinear Davenport-Schinzel sequences by segments ⋮ On the two-dimensional Davenport-Schinzel problem ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ Linearly interpolated FDH efficiency score for nonconvex frontiers ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Randomized incremental construction of simple abstract Voronoi diagrams in 3-space ⋮ Primitives for the manipulation of three-dimensional subdivisions ⋮ Parallel computational geometry ⋮ Three-dimensional unstructured mesh generation. I: Fundamental aspects of triangulation and point creation ⋮ Average case analysis of dynamic geometric optimization ⋮ Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ An upper bound on the shortness exponent of inscribable polytopes ⋮ On Delaunay oriented matroids for convex distance functions ⋮ “The big sweep”: On the power of the wavefront approach to Voronoi diagrams ⋮ Realizability and inscribability for simplicial polytopes via nonlinear optimization ⋮ An interface-fitted mesh generator and virtual element methods for elliptic interface problems ⋮ Perturbations for Delaunay and weighted Delaunay 3D triangulations ⋮ Statistical Approaches for Non‐parametric Frontier Models: A Guided Tour ⋮ Universality theorems for inscribed polytopes and Delaunay triangulations ⋮ COMBINATORIAL INSCRIBABILITY OBSTRUCTIONS FOR HIGHER DIMENSIONAL POLYTOPES ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore ⋮ Voronoi diagrams in the moscow metric ⋮ A faster circle-sweep Delaunay triangulation algorithm ⋮ Meissner polyhedra ⋮ Exact computation of the topology and geometric invariants of the Voronoi diagram of spheres in 3D ⋮ A straightforward iterative algorithm for the planar Voronoi diagram ⋮ Realizability of Delaunay triangulations ⋮ Neighborly inscribed polytopes and Delaunay triangulations ⋮ Efficient mesh optimization schemes based on optimal Delaunay triangulations ⋮ Unnamed Item ⋮ An axiomatic approach to Voronoi-diagrams in 3D ⋮ A simple method for resolving degeneracies in Delaunay triangulations ⋮ A parallel algorithm based on convexity for the computing of Delaunay tessellation ⋮ Three-dimensional convex hull as a fruitful source of diagrams ⋮ The farthest point Delaunay triangulation minimizes angles ⋮ The \(\gamma\)-neighborhood graph ⋮ A new duality result concerning Voronoi diagrams ⋮ Fuzzy clustering using the convex hull as geometrical model ⋮ Randomized incremental construction of abstract Voronoi diagrams ⋮ Algorithms for weak and wide separation of sets ⋮ PAINT: Pareto front interpolation for nonlinear multiobjective optimization ⋮ General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties ⋮ A comparison of sequential Delaunay triangulation algorithms. ⋮ Many projectively unique polytopes ⋮ FURTHEST SITE ABSTRACT VORONOI DIAGRAMS ⋮ The natural element method in solid mechanics ⋮ Measure of circularity for parts of digital boundaries and its fast computation ⋮ On polyhedral realization with isosceles triangles ⋮ On the construction of abstract Voronoi diagrams ⋮ New applications of random sampling in computational geometry ⋮ Voronoi diagrams with barriers and on polyhedra for minimal path planning ⋮ Parallel geometric algorithms on a mesh-connected computer ⋮ An optimal convex hull algorithm in any fixed dimension ⋮ Toughness and Delaunay triangulations ⋮ On levels in arrangements and Voronoi diagrams ⋮ Voronoi diagrams on the sphere ⋮ Voronoi Diagrams of Moving Points ⋮ Fast segment insertion and incremental construction of constrained Delaunay triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Divide and conquer for linear expected time
• Finding the intersection of n half-spaces in time O(n log n)
• Parallel concepts in graph theory
• An efficient algorithm for determining the convex hull of a finite planar set
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Printer graphics for clustering
• Convex hulls of finite sets of points in two and three dimensions
• Location of a Point in a Planar Subdivision and Its Applications
• A New Convex Hull Algorithm for Planar Sets
• An Algorithm for Convex Polytopes

This page was built for publication: Voronoi diagrams from convex hulls