Minimum Dilation Triangulation: Reaching Optimality Efficiently.
Aléx Fernando Brandt, Miguel M. Gaiowski, Cid C. de Souza, Pedro J. de Rezende · Canadian Conference on Computational Geometry · 2014
Let G(P ) = (P,E) be the geometric graph associated to a given set P of points in the plane, i.e., the complete 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 between 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 programming 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.