Delaunay triangulations with disconnected realization spaces

Authors: Arnau Padrol and Louis Theran
Proc. of: ACM Symposium on Computational Geometry SoCG’14, 2014.
Full text: DOI

We study realization spaces of Delaunay triangulations and show that they can be arbitrarily complicated, and in particular disconnected. Our smallest example consists of two configurations of \(29\) labeled points in \(\mathbb{R}^{25}\) whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the triangulation. In general, we prove that the realization space of a Delaunay triangulation in \(\mathbb{R}^2\) can have \(\Omega(2^d)\) connected components. Our proof uses Mnëv’s Universality Theorem and also shows that the realizability problem for Delaunay triangulations is polynomially equivalent to the existential theory of the reals.