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

TLDR

The Delaunay tessellation in n‑dimensional space is a space‑filling aggregate of n‑simplices dual to Voronoi vertices, and while 2‑D Voronoi tessellations have been simulated, higher‑dimensional implementations face problems that can be mitigated by computing the dual Delaunay tessellation. The study presents an algorithm that determines the topological relationships in these tessellations. The algorithm computes the dual Delaunay tessellation to avoid higher‑dimensional issues and extracts the topological relationships among the n‑simplices.

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.