Approximation algorithm improves path efficiency in plane trees
A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane
Computational Geometry
Summary
Some computer scientists want to connect points on a flat surface so that traveling between any two points by the connections doesn’t become too much longer than going straight between them. This problem is very hard to solve exactly, so finding a close solution quickly is important. The authors developed a new method that finds a reasonably good solution faster than previous ones for connecting points in this way. Their approach gets closer to the best possible solution in a way that grows slower than the number of points, which is a big step forward. This solves a problem that had been open for many years.
geometric graphdilationminimum dilation treespanning treeEuclidean planeapproximation algorithmNP-hardminimum spanning treepolynomial timeapproximation ratio
Authors
Sarita de Berg, Jacobus Conradi, Peter Kramer, André Nusser, Sampson Wong
Abstract
The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through the ambient space. The minimum dilation tree of a point set is the spanning tree with minimum dilation, where edge lengths in the tree are given by distances in the ambient space. In the Euclidean plane, computing the minimum dilation tree is NP-hard, but no hardness of approximation result is known. On the other hand, the minimum spanning tree is an $(n-1)$-approximation to the minimum dilation tree, but no asymptotically-better approximation algorithm is known for general point sets in the Euclidean plane. We give the first sublinear approximation algorithm for the minimum dilation tree in the Euclidean plane. Our approximation ratio is $\tilde{O}(n^{14/15})$ and our algorithm runs in polynomial time. This resolves an open problem proposed by Eppstein in 1996.