A Short Proof of the Toughness of Delaunay Triangulations

Abstract

We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-tough. An important implication of this result is that Delaunay triangulations have perfect matchings. Another implication of our result is a proof of the conjecture of Aichholzer et al. (2010) that at least $n$ points are required to block any $n$-vertex Delaunay triangulation

A new result about blocking Delaunay triangulations, SOSA 2020