Fast geometric approximation techniques and geometric embedding problems (Q1202926)

A new notion of approximate geometric sorting is used to devise an algorithm that gives a \((1+\varepsilon)\)-approximation to the 1- dimensional minimum spanning tree (MSP) (or traveling sales man path (TSP)) of \(n\) colinear points in time \(O(n+n\log(1/\varepsilon)/\log n)\). The same notion is used to devise two schemes that approximate the Euclidean minimum spanning tree (EMST) to within a factor of \(1+\varepsilon\). A consequence of this EMST approximations is a \((2+\varepsilon)\)- approximation scheme for the Euclidean TSP, running in time \(O(n\log\log n)\) for any fixed \(\varepsilon\). In the final section, the approximate sorting and MST algorithms are used to get fast approximation algorithms for three geometric embedding problems---for a star in the plane, a complete binary tree onto points on the line and a tree of fixed maximum degree onto the points on the plane.