Minimum Dilation Triangulation: Reaching Optimality Efficiently

Let G(P) = (P,E) be the geometric graph associated to a given set P of points in the plane, i.e., the com-plete graph whose vertex set is P and whose edges have weights defined by the Euclidean distance between their endpoints. On a planar triangulation of P, T ⊆ G(P), the dilation of a pair of points i, j ∈ P is the ratio be-tween the length of the shortest path between i and j in T and their Euclidean distance. The dilation of T is the maximum dilation between the pairs of points in P. The Minimum Dilation Triangulation Problem (mdtp) asks for a triangulation of P with smallest dilation. We developed an exact algorithm that combines an efficient heuristic, a set of preprocessing routines that exploit geometric properties of the problem (using the primal bound given by the heuristic) and an integer program-ming model for the mdtp. We report on computational experiments in which, for the first time, instances of up to 70 points have been solved to proven optimality. The impact of the heuristic and the preprocessing on the algorithm’s performance are demonstrated through a careful analysis of the results.