Computational complexity of Minimum Average Distance Triangulations with metric and Euclidean weights

A triangulation of a planar point set (or of a simple polygon) is a maximal crossing-free straight-line graph on the given vertices. The Minimum Average Distance Triangulation problem (MADT) asks for a triangulation minimizing the sum, over all unordered pairs of vertices, of the shortest-path distance measured along the triangulation's edges — the graph's Wiener index. Kozma (ESA 2012) proved MADT strongly NP-complete for arbitrary positive symmetric weights and gave an $O(n^{11})$ dynamic-programming algorithm for unit weights (link distance) on simple polygons, but the complexity for weights obeying the triangle inequality — above all for Euclidean distances — was left open in both the point-set and the polygon setting, with NP-hardness conjectured for Euclidean point sets but no reduction known. The goal is to settle that classification: for Euclidean point sets, prove or refute the conjectured NP-hardness; for simple polygons with metric weights, determine whether the problem is polynomial-time solvable or NP-hard.

Background

A triangulation of a set of points in the plane is a maximal set of pairwise non-crossing straight segments between the points; if the points are the vertices of a simple polygon (a closed polygonal chain without self-intersections), a triangulation consists of the boundary edges plus $n-3$ non-crossing diagonals partitioning the interior into triangles. Finding triangulations optimal for a given criterion is a classical topic in computational geometry. The best-studied example is the minimum weight triangulation (MWT), where the criterion is the total Euclidean length of the chosen edges: for simple polygons it is solvable in $O(n^{3})$ by classical dynamic programming, while for planar point sets with Euclidean weights it is NP-hard (Mulzer and Rote, 2008).

The problem considered here replaces the total edge length by an average routing cost. Given weights $w(x,y)\ge 0$ (symmetric, zero on the diagonal) on all pairs of points, a triangulation $T$ is judged by

$\mathcal{W}(T)=\sum_{1\le i<j\le n} d_T(p_i,p_j),$

where $d_T(p_i,p_j)$ is the length of the shortest path between $p_i$ and $p_j$ along edges of $T$, each edge contributing its weight. In chemical graph theory this quantity is the Wiener index, a standard descriptor of molecular graphs; in network design it is the total (equivalently, expected) routing cost of a network whose links may not cross. The problem arises from a classical network design question of Johnson, Lenstra, and Rinnooy Kan (1978): finding a spanning subgraph of an edge-weighted graph that minimizes average pairwise distance is NP-complete, and remains so even for unit weights when a budget on total edge weight forces a tree. Kozma (ESA 2012) studied the planar version of this question — now the non-crossing constraint replaces the budget — and called it the Minimum Average Distance Triangulation problem (MADT). When all weights equal one, $d_T$ counts the number of edges on a shortest path, called the link distance; because adding an edge can never increase a distance, only maximal crossing-free graphs, i.e. triangulations, need be considered.

Kozma's results delineate the boundary of current knowledge. For unit weights, if one point (or polygon vertex) can see all others — meaning the straight segment from it to every other point lies inside the polygon (or, for a point set, passes through no other input point) — then the fan triangulation rooted at that point, which connects it directly to every other vertex, is optimal. For unit weights on arbitrary simple polygons he gave a dynamic program of time $O(n^{11})$, based on a structural lemma that decouples the cost of a subpolygon from the rest; he notes that the ideas of the classical $O(n^{3})$ MWT dynamic program do not carry over, because the MADT cost is highly nonlocal: it couples every pair of vertices, not just the boundary of each subproblem. For arbitrary positive symmetric weights — which need not satisfy the triangle inequality, so shortest paths in the plane are not simulated — he proved the decision version strongly NP-complete (NP-complete even when all weights are bounded by a polynomial in the input size) via a carefully balanced gadget reduction from Planar3SAT — the restriction of 3-SAT to formulas whose variable–clause incidence graph is planar — which also rules out a fully polynomial time approximation scheme (FPTAS) unless P=NP.

Between these extremes lies the open middle ground: weights that are nontrivial metrics, in particular Euclidean distances between the actual point locations. The known hardness proof fundamentally uses semimetric weights of wildly different magnitudes, and the known algorithms fundamentally use unit weights — which are themselves a metric, though a degenerate one; neither technique extends to general metrics such as Euclidean distances. For simple polygons with Euclidean weights, no analogue of the structural lemma behind the $O(n^{11})$ algorithm is known, and no hardness result exists — computer experiments reported in the paper show that for regular $n$-gons the optimal triangulation is the fan for all $n\le 18$ except $n=7$ and $n=9$ (where other triangulations win), and the paper conjectures these two to be the only exceptions. For Euclidean point sets, Kozma states the suspicion that the problem remains NP-hard, without a reduction. Settling the complexity status of metric, in particular Euclidean, MADT — in both the point-set and the polygon setting — is the paper's own 'main unanswered question'.

Problem Statement

Determine the computational complexity of the Minimum Average Distance Triangulation problem (MADT) when the edge weights obey the triangle inequality, in particular when they are Euclidean distances, in each of the two settings in which the problem is posed.

(1) Point sets: given a set $S=\{p_1,\dots,p_n\}$ of points in the plane, weights $w(x,y)$ equal to the Euclidean distance between $x$ and $y$ (or, more generally, any symmetric weight function on pairs satisfying the triangle inequality), and a threshold $W^*$, decide whether $S$ admits a crossing-free straight-line triangulation $T$ with $\mathcal{W}(T)=\sum_{1\le i<j\le n} d_T(p_i,p_j)\le W^*$, where $d_T$ is the shortest-path distance along edges of $T$ weighted by $w$. Kozma suspects this problem is NP-hard but has no reduction: prove NP-hardness (for Euclidean weights, or for some metric weight class), or give a polynomial-time algorithm.

(2) Simple polygons: given a simple polygon with $n$ vertices and metric (in particular Euclidean) weights, decide whether a triangulation of the polygon's interior achieves $\mathcal{W}(T)\le W^*$. Determine whether metric (in particular Euclidean) polygon MADT is polynomial-time solvable or NP-hard.

The classification is asked in both the point-set and the polygon setting. Any resolution must be consistent with the known boundary cases: the known polynomially solvable unit-weight cases are one-point-visible instances (fan triangulations) and simple polygons (the $O(n^{11})$ dynamic program), while unit-weight MADT on point sets not admitting a fan remains open; the arbitrary-positive-weight (semimetric) case is strongly NP-complete; and regular $n$-gons — where the fan is conjectured optimal for all $n$ except $n=7$ and $n=9$ — are contained special cases of the Euclidean polygon setting.

References

1. László Kozma. Minimum Average Distance Triangulations. In Algorithms – ESA 2012, Proc. 20th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 7501, pp. 695–706. Springer, 2012. DOI: 10.1007/978-3-642-33090-2_60, arXiv:1112.1828. https://arxiv.org/abs/1112.1828
2. D. S. Johnson, J. K. Lenstra, A. H. G. Rinnooy Kan. The complexity of the network design problem. Networks 8(4):279–285, 1978. DOI: 10.1002/net.3230080402. https://doi.org/10.1002/net.3230080402
3. Wolfgang Mulzer, Günter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM 55(2), Article 11, pp. 1–29, 2008. DOI: 10.1145/1346330.1346336, arXiv:cs/0601002. https://doi.org/10.1145/1346330.1346336
4. Matias Korman, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber. The Dual Diameter of Triangulations. Computational Geometry: Theory and Applications 68:243–252, 2018. DOI: 10.1016/j.comgeo.2017.06.008, arXiv:1503.08518. https://doi.org/10.1016/j.comgeo.2017.06.008
5. Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant. Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. arXiv:2207.07708, 2022. https://arxiv.org/abs/2207.07708
6. Éva Czabarka, Peter Dankelmann, Trevor Olsen, László A. Székely. Wiener index and remoteness in triangulations and quadrangulations. Discrete Mathematics & Theoretical Computer Science 23(1), 2021. DOI: 10.46298/dmtcs.6473, arXiv:1905.06753. https://doi.org/10.46298/dmtcs.6473
7. Éva Czabarka, Trevor V. Olsen, Stephen J. Smith, László A. Székely. Minimum Wiener index of triangulations and quadrangulations. Discrete Applied Mathematics 322:295–310, 2022. DOI: 10.1016/j.dam.2022.08.025, arXiv:2003.03873. https://doi.org/10.1016/j.dam.2022.08.025
8. A. Karim Abu-Affash, Paz Carmi, Ori Luwisch, Joseph S. B. Mitchell. Geometric Spanning Trees Minimizing the Wiener Index. arXiv:2303.01096, 2023. https://arxiv.org/abs/2303.01096
9. Sándor P. Fekete, Phillip Keldenich, Michael Perk. Exact Algorithms for Minimum Dilation Triangulation. arXiv:2502.18189, 2025. https://arxiv.org/abs/2502.18189
10. Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer. Parameterized Algorithms for Computing MAD Trees. arXiv:2603.29381, 2026. https://arxiv.org/abs/2603.29381