Hardness of minimum-dilation triangulation
Let $P \subset \mathbb{Q}^2$ be a finite set of points, not all on one line. A triangulation $T$ of $P$ is a maximal plane straight-line graph with vertex set $P$ in which no edge passes through a point of $P$ other than its endpoints, each edge weighted by its Euclidean length, and its dilation is $$\delta(T) = \max_{p \ne q \in P} \frac{d_T(p, q)}{\|p - q\|_2},$$ where $d_T$ is the shortest-path distance in $T$. Eppstein asked whether a triangulation of least dilation can be constructed in polynomial time. Mulzer and Rote proved that computing a minimum-weight triangulation is NP-hard, and Giannopoulos, Klein, Knauer, Kutz and Marx proved that computing a minimum-dilation geometric graph on given points in the plane with at most a given number of edges is NP-hard. Fekete, Keldenich and Perk computed exactly optimal triangulations for benchmark sets of up to $30{,}000$ points.
Problem. Is the following decision problem NP-hard under polynomial-time many-one reductions, with the input in the standard binary encoding: given rational coordinates of the points of $P$ and a rational threshold $\tau \ge 1$, decide whether some triangulation $T$ of $P$ satisfies $\delta(T) \le \tau$? Edge lengths and the inequality are exact. Membership in NP is not asked, since comparing sums of square roots is a separate arithmetic issue.
Source: Eppstein (1996; Handbook of Computational Geometry, 2000), who asked whether a minimum-dilation triangulation can be constructed in polynomial time (Open Problem 7 of the 1996 report); see Fekete, Keldenich and Perk (2026). Stated as an NP-hardness question by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO, OC
- Keywords
- AIM Open Applied Problems, geometric spanners, NP-hardness, triangulations
References
@incollection{eppstein2000,
author = {Eppstein, David},
title = {Spanning trees and spanners},
booktitle = {Handbook of Computational Geometry},
editor = {Sack, J{\"o}rg-R{\"u}diger and Urrutia, Jorge},
publisher = {North-Holland},
address = {Amsterdam},
year = {2000},
pages = {425--461},
doi = {10.1016/B978-044482537-7/50010-3},
}
@article{fekete2026,
author = {Fekete, S{\'a}ndor P. and Keldenich, Phillip and Perk, Michael},
title = {Exact algorithms for minimum dilation triangulation},
journal = {J. Comput. Geom.},
volume = {17},
number = {2},
year = {2026},
pages = {1--45},
doi = {10.20382/jocg.v17i2a1},
eprint = {2502.18189},
archivePrefix = {arXiv},
}
@article{mulzer2008,
author = {Mulzer, Wolfgang and Rote, G{\"u}nter},
title = {Minimum-weight triangulation is {NP}-hard},
journal = {J. ACM},
volume = {55},
number = {2},
year = {2008},
pages = {11:1--11:29},
doi = {10.1145/1346330.1346336},
}
@article{giannopoulos2010,
author = {Giannopoulos, Panos and Klein, Rolf and Knauer, Christian and Kutz, Martin and Marx, D{\'a}niel},
title = {Computing geometric minimum-dilation graphs is {NP}-hard},
journal = {Internat. J. Comput. Geom. Appl.},
volume = {20},
number = {2},
year = {2010},
pages = {147--173},
doi = {10.1142/S0218195910003244},
}
@misc{aim-minimum-dilation-hardness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Hardness of minimum-dilation triangulation}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/560-minimum-dilation-hardness.md},
note = {Entry 560 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00877, "Hardness of minimum-dilation triangulation", clopen.solutions.