In computational geometry, the farthest-first traversal of a bounded metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, known as the greedy permutation.
Farthest-point traversals have many applications, including the approximation of the traveling salesman problem and the metric k-center problem. They may be constructed in polynomial time, or (for low-dimensional Euclidean spaces) approximated in near-linear time.
Fix a number k, and consider the subset formed by the first k points of the farthest-first traversal of any metric space. Let r be the distance between the final point of the prefix and the set of previously-selected points. Then this subset has the following two properties:
In other words, each prefix of the farthest-first traversal forms a Delone set.
The first use of the farthest-first traversal was by Rosenkrantz, Stearns & Lewis (1977) in connection with heuristics for the travelling salesman problem. In the farthest-insertion heuristic, discussed by Rosenkrantz et al., a tour is built up incrementally, by adding one point at a time in the ordering given by a farthest-first traversal. To add each point to the traveling salesman tour of the previous points, this heuristic considers all possible ways of breaking one edge of the tour and replacing it by two edges through the new point, and chooses the cheapest of these replacements. Although Rosenkrantz et al. prove only a logarithmic approximation ratio for this method, they show that in practice it often works better than other insertion methods with better provable approximation ratios.