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.
Keywords
Voronoi diagramCentroidal Voronoi tessellationDelaunay triangulationTessellation (computer graphics)Bowyer–Watson algorithmComputer sciencePitteway triangulationCombinatoricsPolytopeMathematicsTopology (electrical circuits)GeometryComputer graphics (images)
Affiliated Institutions
Related Publications
Spatial Tessellations: Concepts and Applications of Voronoi Diagrams
Definitions and basic properties of the Voronoi diagram generalizations of the Voronoi diagram algorithms for computing Voronoi diagrams poisson Voronoi diagrams spatial interpo...
The integrity of geometrical boundaries in the two‐dimensional delaunay triangulation
Abstract The Delaunay triangulation has recently received attention as a viable method for construction computational meshes. However, an arbitrary boundary definition which mus...
Publication Info
- Year
- 1981
- Type
- article
- Volume
- 24
- Issue
- 2
- Pages
- 167-172
- Citations
- 1451
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1451
OpenAlex
Cite This
David F. Watson
(1981).
Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes.
The Computer Journal
, 24
(2)
, 167-172.
https://doi.org/10.1093/comjnl/24.2.167
Identifiers
- DOI
- 10.1093/comjnl/24.2.167