Farthest-first traversal
In
Every
Definition and properties
A farthest-first traversal is a
Farthest-point traversals may be characterized by the following properties. Fix a number k, and consider the prefix 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 other points in the prefix. Then this subset has the following two properties:
- All pairs of the selected points are at distance at least r from each other, and
- All points of the metric space are at distance at most r from the subset.
Conversely any sequence having these properties, for all choices of k, must be a farthest-first traversal. These are the two defining properties of a Delone set, so each prefix of the farthest-first traversal forms a Delone set.[3]
Applications
Later, the same sequence of points was popularized by
Gonzalez's heuristic was independently rediscovered for the metric k-center problem by
As well as for clustering, the farthest-first traversal can also be used in another type of facility location problem, the max-min facility dispersion problem, in which the goal is to choose the locations of k different facilities so that they are as far apart from each other as possible. More precisely, the goal in this problem is to choose k points from a given metric space or a given set of candidate points, in such a way as to maximize the minimum pairwise distance between the selected points. Again, this can be approximated by choosing the first k points of a farthest-first traversal. If r denotes the distance of the kth point from all previous points, then every point of the metric space or the candidate set is within distance r of the first k − 1 points. By the pigeonhole principle, some two points of the optimal solution (whatever it is) must both be within distance r of the same point among these first k − 1 chosen points, and (by the triangle inequality) within distance 2r of each other. Therefore, the heuristic solution given by the farthest-first traversal is within a factor of two of optimal.[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
Algorithms
Greedy exact algorithm
The farthest-first traversal of a finite point set may be computed by a greedy algorithm that maintains the distance of each point from the previously selected points, performing the following steps:[3]
- Initialize the sequence of selected points to the empty sequence, and the distances of each point to the selected points to infinity.
- While not all points have been selected, repeat the following steps:
- Scan the list of not-yet-selected points to find a point p that has the maximum distance from the selected points.
- Remove p from the not-yet-selected points and add it to the end of the sequence of selected points.
- For each remaining not-yet-selected point q, replace the distance stored for q by the minimum of its old value and the distance from p to q.
For a set of n points, this algorithm takes O(n2) steps and O(n2) distance computations.[3]
Approximations
A faster approximation algorithm, given by Har-Peled & Mendel (2006), applies to any subset of points in a metric space with bounded doubling dimension, a class of spaces that include the Euclidean spaces of bounded dimension. Their algorithm finds a sequence of points in which each successive point has distance within a 1 − ε factor of the farthest distance from the previously-selected point, where ε can be chosen to be any positive number. It takes time .[2]
The results for bounded doubling dimension do not apply to high-dimensional Euclidean spaces, because the constant factor in the big O notation for these algorithms depends on the dimension. 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 , where n and m are the numbers of vertices and edges of the input graph, respectively.[26]
Incremental Voronoi insertion
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. Instead, each new point should be selected as the center of the largest empty circle defined by the previously-selected point set.[12] This center will always lie on a vertex of the Voronoi diagram of the already selected points, or at a point where an edge of the Voronoi diagram crosses the domain boundary. 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.[28]
See also
- Lloyd's algorithm, a different method for generating evenly spaced points in geometric spaces
References
- ^ MR 2136964
- ^ S2CID 37346335
- ^ MR 0807927
- S2CID 14764079
- ^ MR 0797340
- ^ MR 0793876
- ^ For prominent examples of incorrect attribution of the farthest-first heuristic to Hochbaum & Shmoys (1985), see, e.g.,
- Dasgupta, Sanjoy (2002), "Performance guarantees for hierarchical clustering", in Kivinen, Jyrki; Sloan, Robert H. (eds.), Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2375, Springer, pp. 351–363, ISBN 978-3-540-43836-6(corrected in the 2005 journal version of the same paper)
- Agarwal, Sameer; Ramamoorthi, Ravi; Belongie, Serge J.; Jensen, Henrik Wann (2003), "Structured importance sampling of environment maps", ACM Trans. Graph., 22 (3): 605–612,
- Baram, Yoram; El-Yaniv, Ran; Luz, Kobi (2004), "Online choice of active learning algorithms" (PDF), J. Mach. Learn. Res., 5: 255–291
- Basu, Sugato; Bilenko, Mikhail; Banerjee, Arindam; Mooney, Raymond J. (2006), "Probabilistic semi-supervised clustering with constraints", in Chapelle, Olivier; Schölkopf, Bernhard; Zien, Alexander (eds.), Semi-Supervised Learning, The MIT Press, pp. 73–102, ISBN 978-0-262-03358-9
- Lima, Christiane Ferreira Lemos; Assis, Francisco M.; de Souza, Cleonilson Protásio (2011), "A comparative study of use of Shannon, Rényi and Tsallis entropy for attribute selecting in network intrusion detection", IEEE International Workshop on Measurement and Networking, M&N 2011, Anacapri, Italy, October 10-11, 2011, IEEE, pp. 77–82, S2CID 7510040
- "Class FarthestFirst", Weka, version 3.9.5, University of Waikato, December 21, 2020, retrieved 2021-11-06 – via SourceForge
- Dasgupta, Sanjoy (2002), "Performance guarantees for hierarchical clustering", in Kivinen, Jyrki; Sloan, Robert H. (eds.), Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2375, Springer, pp. 351–363,
- MR 1154657; White credits the use of the farthest-first traversal as a heuristic for this problem to Steuer, R. E. (1986), Multiple-Criteria Optimization: Theory, Computation, and Applications, New York: Wiley
- MR 1129392
- S2CID 16489402
- S2CID 17713417
- ^ PMID 18283019
- doi:10.1613/jair.468
- ^ Moenning, C.; Dodgson, N. A. (2003), "A new point cloud simplification algorithm", 3rd IASTED International Conference on Visualization, Imaging, and Image Processing
- S2CID 10608234
- S2CID 6001942
- ^ Girdhar, Y.; Giguère, P.; Dudek, G. (2012), "Autonomous adaptive underwater exploration using online topic modelling" (PDF), Proc. Int. Symp. Experimental Robotics
- PMID 19085326
- ISBN 978-3-642-00922-8
- ISBN 978-3-642-64107-7
- ^ Vieira, Luiz Filipe M.; Vieira, Marcos Augusto M.; Ruiz, Linnyer Beatrys; Loureiro, Antonio A. F.; Silva, Diógenes Cecílio; Fernandes, Antônio Otávio (2004), "Efficient Incremental Sensor Network Deployment Algorithm" (PDF), Proc. Brazilian Symp. Computer Networks, pp. 3–14
- S2CID 18626929
- S2CID 6286186
- S2CID 18316279
- hdl:2433/84849