Farthest-first traversal
Fix a number k, and consider the prefix formed by the first k points of the farthest-first traversal of any metric space.
[3] Rosenkrantz, Stearns & Lewis (1977) used the farthest-first traversal to define the farthest-insertion heuristic for the travelling salesman problem.
This heuristic finds approximate solutions to the travelling salesman problem by building up a tour on a subset of points, adding one point at a time to the tour in the ordering given by a farthest-first traversal.
For instance, the k-center problem can be used to model the placement of fire stations within a city, in order to ensure that every address within the city can be reached quickly by a fire truck.
However, the subset of k centers together with the next point are all at distance at least r from each other, and any k-clustering would put some two of these points into a single cluster, with one of them at distance at least r/2 from its center and with diameter at least r. Thus, Gonzalez's heuristic gives an approximation ratio of 2 for both clustering problems.
[5] Another paper on the k-center problem from the same time, Hochbaum & Shmoys (1985), achieves the same approximation ratio of 2,[6] but its techniques are different.
[5] Nevertheless, Gonzalez's heuristic, and the name "farthest-first traversal", are often incorrectly attributed to Hochbaum and Shmoys.
[7] For both the min-max diameter clustering problem and the metric k-center problem, these approximations are optimal: the existence of a polynomial-time heuristic with any constant approximation ratio less than 2 would imply that P = NP.
[8][9][10] Other applications of the farthest-first traversal include color quantization (clustering the colors in an image to a smaller set of representative colors),[11] progressive scanning of images (choosing an order to display the pixels of an image so that prefixes of the ordering produce good lower-resolution versions of the whole image rather than filling in the image from top to bottom),[12] point selection in the probabilistic roadmap method for motion planning,[13] simplification of point clouds,[14] generating masks for halftone images,[15][16] hierarchical clustering,[1] finding the similarities between polygon meshes of similar surfaces,[17] choosing diverse and high-value observation targets for underwater robot exploration,[18] fault detection in sensor networks,[19] modeling phylogenetic diversity,[20] matching vehicles in a heterogenous fleet to customer delivery requests,[21] uniform distribution of geodetic observatories on the Earth's surface[22] or of other types of sensor network,[23] generation of virtual point lights in the instant radiosity computer graphics rendering method,[24] and geometric range searching data structures.
Instead, a different approximation method based on the Johnson–Lindenstrauss lemma and locality-sensitive hashing has running time
For metrics defined by shortest paths on weighted undirected graphs, a randomized incremental construction based on Dijkstra's algorithm achieves time
[26] For selecting points from a continuous space such as the Euclidean plane, rather than from a finite set of candidate points, these methods will not work directly, because there would be an infinite number of distances to maintain.
In this formulation the method for constructing farthest-first traversals has also been called incremental Voronoi insertion.
[27] It is similar to Delaunay refinement for finite element mesh generation, but differs in the choice of which Voronoi vertex to insert at each step.
