A short proof of the toughness of Delaunay triangulations

DOI10.20382/JOCG.V12I1A2zbMATH Open1477.68460arXiv1907.01617OpenAlexW3003947026MaRDI QIDQ5854568

Ahmad Biniaz

Publication date: 17 March 2021

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

Full work available at URL: https://arxiv.org/abs/1907.01617

zbMATH Keywords

Delaunay triangulationblocking Delaunay triangulations

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

A weak characterisation of the Delaunay triangulation

Recommendations

• A tight bound for the Delaunay triangulation of points on a polyhedron 👍 👎
• A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces 👍 👎
• Toughness and Delaunay triangulations 👍 👎
• Realizability of Delaunay triangulations 👍 👎
• A weak characterisation of the Delaunay triangulation 👍 👎
• Minimal roughness property of the Delaunay triangulation: A shorter approach 👍 👎
• Simpler proof of a realizability theorem on Delaunay triangulations 👍 👎
• THE STABILITY OF DELAUNAY TRIANGULATIONS 👍 👎
• CHARACTERIZING DELAUNAY GRAPHS VIA FIXED POINT THEOREM: A SIMPLE PROOF 👍 👎
• Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract] 👍 👎

This page was built for publication: A short proof of the toughness of Delaunay triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854568)