An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces

2009/06/01 by Daniel Reem · 1 citation
Computer Science · Environmental Science · Mathematics · #Computational Geometry and Mesh Generation #Remote Sensing and LiDAR Applications #Data Management and Algorithms #Voronoi diagram #Weighted Voronoi diagram #Computer science #Algorithm #Simple (philosophy) #Function (biology) #Euclidean geometry #Euclidean space #Euclidean distance #Mathematics #Discrete mathematics #Combinatorics #Theoretical computer science #Artificial intelligence

paper · doi:10.1109/isvd.2009.23

openalex publication_date 2009/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Voronoi diagrams appear in many areas in science and technology and have diverse applications. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Voronoi diagrams have been the subject of extensive research during the last 35 years, and many algorithms for computing them have been published. However, these algorithms are for specific cases. They impose restrictions on either the space (often R2or R3), the generators (distinct points, special shapes), the distance function (Euclidean or variations thereof) and more. Moreover, their implementation is not always simple and their success is not always guaranteed. We present an efficient and simple algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional. We allow infinitely many generators of a general form. The algorithm computes each of the Voronoi cells independently of the others, and to any required precision. It can be generalized to other settings, such as manifolds, graphs and convex distance functions.

Citations

• Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.
• Voronoi diagrams—a survey of a fundamental geometric data structure
• Computing Dirichlet tessellations
• A sweepline algorithm for Voronoi diagrams
• Euclidean Voronoi diagram of 3D balls and its computation via tracing edges
• Higher-dimensional voronoi diagrams in linear expected time
• Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen.
• Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes

Cited by

• Voronoi diagram [wikipedia]

Related

• The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites
• Generalized Voronoi Diagrams and Lie Sphere Geometry
• A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
• The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex
• Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon