Voronoi diagrams—a survey of a fundamental geometric data structure

1991/09/01 by Franz Aurenhammer · 8 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #3D Modeling in Geospatial Applications #Data Management and Algorithms #Voronoi diagram #Computer science #Citation #Data structure #Information retrieval #Data science #Computer graphics (images) #World Wide Web #Programming language #Mathematics #Geometry

paper · doi:10.1145/116873.116880

openalex publication_date 1991/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

This paper presents a survey of the Voronoi diagram, one of the most fundamental data structures in computational geometry. It demonstrates the importance and usefulness of the Voronoi diagram in a wide variety of fields inside and outside computer science and surveys the history of its development. The paper puts particular emphasis on the unified exposition of its mathematical and algorithmic properties. Finally, the paper provides the first comprehensive bibliography on Voronoi diagrams and related structures.

Citations

• XLV. On reciprocal figures and diagrams of forces
• Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A faster divide-and-conquer algorithm for constructing delaunay triangulations
• Generalized Dirichlet tessellations
• Generalized delaunay triangulation for planar graphs
• Shortest Connection Networks And Some Generalizations
• Convex hulls of finite sets of points in two and three dimensions
• Computing Dirichlet tessellations
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Randomized incremental construction of Delaunay and Voronoi diagrams
• A sweepline algorithm for Voronoi diagrams
• On the Constitution of Metallic Sodium
• The Discrete Geodesic Problem
• Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen.
• Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes
• Finding Minimum Spanning Trees
• On the shape of a set of points in the plane
• An Analysis of Several Heuristics for the Traveling Salesman Problem

Cited by

• Learning a Safety Verifiable Adaptive Cruise Controller from Human Driving Data
• An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces
• Dispelling the N3 myth for the kt jet-finder
• A Novel Type of Skeleton for Polygons
• Voronoi diagrams of polygons: A framework for shape representation
• Grid generation and optimization based on centroidal Voronoi tessellations
• Tessellation [wikipedia]
• Voronoi diagram [wikipedia]