Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes

1981/02/01 by David F. Watson · 5 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #3D Modeling in Geospatial Applications #Robotic Path Planning Algorithms #Voronoi diagram #Centroidal Voronoi tessellation #Delaunay triangulation #Tessellation (computer graphics) #Bowyer–Watson algorithm #Computer science #Pitteway triangulation #Combinatorics #Polytope #Mathematics #Topology (electrical circuits) #Geometry #Computer graphics (images)

paper · doi:10.1093/comjnl/24.2.167

openalex publication_date 1981/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

The Delaunay tessellation in n-dimensional space is a space-filling aggregate of n-simplices. These n-simplices are the dual forms of the vertices in the commonly used Voronoi tessellation. Several efforts have been made to simulate the 2-dimensional Voronoi tessellation on the computer. Additional problems occur for the 3 and higher dimensional implementations but some of these can be avoided by alternatively computing the dual Delaunay tessellation. An algorithm that finds the topological relationships in these tessellations is given.

Cited by

• Voronoi diagrams—a survey of a fundamental geometric data structure
• An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces
• Estimating Seal Pup Production in The Greenland Sea by Using Bayesian Hierarchical Modelling
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Voronoi diagram [wikipedia]