In computational geometry, the farthest-first traversal of a compact 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 In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...

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, also known as the greedy permutation. Every prefix of a farthest-first traversal provides a set of points that is widely spaced and close to all remaining points. More precisely, no other set of equally many points can be spaced more than twice as widely, and no other set of equally many points can be less than half as far to its farthest remaining point. In part because of these properties, farthest-point traversals have many applications, including the approximation of the

traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

and the metric -center problem. They may be constructed in polynomial time, or (for low-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

s) approximated in near- linear time.

Definition and properties

A farthest-first traversal is a

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...

of points in a compact metric space, with each point appearing at most once. If the space is finite, each point appears exactly once, and the traversal is a permutation of all of the points in the space. The first point of the sequence may be any point in the space. Each point after the first must have the maximum possible distance to the set of points earlier than in the sequence, where the distance from a point to a set is defined as the minimum of the pairwise distances to points in the set. A given space may have many different farthest-first traversals, depending both on the choice of the first point in the sequence (which may be any point in the space) and on ties for the maximum distance among later choices. Farthest-point traversals may be characterized by the following properties. Fix a number , and consider the prefix formed by the first points of the farthest-first traversal of any metric space. Let 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 from each other, and *All points of the metric space are at distance at most from the subset. Conversely any sequence having these properties, for all choices of , must be a farthest-first traversal. These are the two defining properties of a

Delone set In the mathematical theory of metric spaces, ε-nets, ε-packings, ε-coverings, uniformly discrete sets, relatively dense sets, and Delone sets (named after Boris Delone) are several closely related definitions of well-spaced sets of points, a ...

, so each prefix of the farthest-first traversal forms a Delone set.

Applications

used the farthest-first traversal to define the farthest-insertion

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...

for the

travelling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

. 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. To add each point to the tour, one edge of the previous tour is broken and replaced by a pair of edges through the added point, in the cheapest possible way. Although Rosenkrantz et al. prove only a logarithmic

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

for this method, they show that in practice it often works better than other insertion methods with better provable approximation ratios. Later, the same sequence of points was popularized by , who used it as part of greedy approximation algorithms for two problems in clustering, in which the goal is to partition a set of points into clusters. One of the two problems that Gonzalez solve in this way seeks to minimize the maximum

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

of a cluster, while the other, known as the metric -center problem, seeks to minimize the maximum radius, the distance from a chosen central point of a cluster to the farthest point from it in the same cluster. For instance, the -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. For both clustering problems, Gonzalez chooses a set of cluster centers by selecting the first points of a farthest-first traversal, and then creates clusters by assigning each input point to the nearest cluster center. If is the distance from the set of selected centers to the next point at position in the traversal, then with this clustering every point is within distance of its center and every cluster has diameter at most . However, the subset of centers together with the next point are all at distance at least from each other, and any -clustering would put some two of these points into a single cluster, with one of them at distance at least from its center and with diameter at least . Thus, Gonzalez's heuristic gives an

of 2 for both clustering problems. Gonzalez's heuristic was independently rediscovered for the metric -center problem by , who applied it more generally to weighted -center problems. Another paper on the -center problem from the same time, , achieves the same approximation ratio of 2, but its techniques are different. Nevertheless, Gonzalez's heuristic, and the name "farthest-first traversal", are often incorrectly attributed to Hochbaum and Shmoys. For both the min-max diameter clustering problem and the metric -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 The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used above ...

. 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 different facilities so that they are as far apart from each other as possible. More precisely, the goal in this problem is to choose 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 points of a farthest-first traversal. If denotes the distance of the th point from all previous points, then every point of the metric space or the candidate set is within distance of the first points. By the

pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...

, some two points of the optimal solution (whatever it is) must both be within distance of the same point among these first chosen points, and (by the

triangle inequality In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. This statement permits the inclusion of degenerate triangles, but ...

) within distance of each other. Therefore, the heuristic solution given by the farthest-first traversal is within a factor of two of optimal. Other applications of the farthest-first traversal include

color quantization In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as v ...

(clustering the colors in an image to a smaller set of representative colors), progressive scanning of images (choosing an order to display the

pixel In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device. In most digital display devices, pixels are the ...

s 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), point selection in the probabilistic roadmap method for

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is use ...

, simplification of

point cloud Point or points may refer to: Places * Point, Lewis, a peninsula in the Outer Hebrides, Scotland * Point, Texas, a city in Rains County, Texas, United States * Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland * Poin ...

s, generating masks for halftone images, hierarchical clustering, finding the similarities between

polygon mesh In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles ( triangle mesh), quadrilaterals (quads), or other simple convex p ...

es of similar surfaces, choosing diverse and high-value observation targets for underwater robot exploration,

fault detection Fault detection, isolation, and recovery (FDIR) is a subfield of control engineering which concerns itself with monitoring a system, identifying when a fault has occurred, and pinpointing the type of fault and its location. Two approaches can be ...

sensor network Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental c ...

s, modeling

phylogenetic diversity Phylogenetic diversity is a measure of biodiversity which incorporates phylogenetic difference between species. It is defined and calculated as "the sum of the lengths of all those branches that are members of the corresponding minimum spanning path ...

, matching vehicles in a heterogenous fleet to customer delivery requests, uniform distribution of geodetic observatories on the Earth's surface or of other types of sensor network, generation of virtual point lights in the instant radiosity

computer graphics rendering Rendering or image synthesis is the process of generating a photorealistic or non-photorealistic image from a 2D or 3D model by means of a computer program. The resulting image is referred to as the render. Multiple models can be defined ...

method, and geometric range searching data structures.

Algorithms

Greedy exact algorithm

The farthest-first traversal of a finite point set may be computed by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

that maintains the distance of each point from the previously selected points, performing the following steps: *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 that has the maximum distance from the selected points. **Remove 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 , replace the distance stored for by the minimum of its old value and the distance from to . For a set of points, this algorithm takes steps and distance computations.

Approximations

A faster approximation algorithm, given by , applies to any subset of points in a metric space with bounded

doubling dimension In mathematics, a metric space with metric is said to be doubling if there is some doubling constant such that for any and , it is possible to cover the ball with the union of at most balls of radius . The base-2 logarithm of is called the d ...

, a class of spaces that include the

s of bounded dimension. Their algorithm finds a sequence of points in which each successive point has distance within a factor of the farthest distance from the previously-selected point, where can be chosen to be any positive number. It takes time

O(n\log n)

. 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 In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a ...

and

locality-sensitive hashing In computer science, locality-sensitive hashing (LSH) is an algorithmic technique that hashes similar input items into the same "buckets" with high probability. (The number of buckets is much smaller than the universe of possible input items.) Since ...

has running time

O(\varepsilon^ n^).

For metrics defined by shortest paths on weighted undirected graphs, a randomized incremental construction based on

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

achieves time

O(\varepsilon^ m\log n\log\tfrac)

, where and are the numbers of vertices and edges of the input graph, respectively.

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. This center will always lie on a vertex of the

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...

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. It is similar to

Delaunay refinement In mesh generation, Delaunay refinement are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulat ...

for

finite element The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat t ...

mesh generation Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. ...

, but differs in the choice of which Voronoi vertex to insert at each step.

References

{{reflist, refs= {{citation , last1 = Abbar , first1 = S. , last2 = Amer-Yahia , first2 = S. , last3 = Indyk , first3 = P. , author3-link = Piotr Indyk , last4 = Mahabadi , first4 = S. , last5 = Varadarajan , first5 = K. R. , contribution = Diverse near neighbor problem , doi = 10.1145/2462356.2462401 , hdl = 1721.1/87000 , hdl-access = free , pages = 207–214 , title = Proceedings of the 29th Annual Symposium on Computational Geometry , year = 2013, s2cid = 6286186 {{citation , last1 = Altinisik , first1 = U. , last2 = Yildirim , first2 = M. , last3 = Erkan , first3 = K. , doi = 10.1021/ie201850k , issue = 32 , journal = Ind. Eng. Chem. Res. , pages = 10641–10648 , title = Isolating non-predefined sensor faults by using farthest first traversal algorithm , volume = 51 , year = 2012 {{citation , last1 = Bordewich , first1 = Magnus , last2 = Rodrigo , first2 = Allen , last3 = Semple , first3 = Charles , doi = 10.1080/10635150802552831 , doi-access = free , issue = 6 , journal = Systematic Biology , pages = 825–834 , title = Selecting taxa to save or sequence: Desirable criteria and a greedy solution , volume = 57 , year = 2008, pmid = 19085326 {{citation , last1 = Dasgupta , first1 = S. , last2 = Long , first2 = P. M. , doi = 10.1016/j.jcss.2004.10.006 , issue = 4 , journal = Journal of Computer and System Sciences , mr = 2136964 , pages = 555–569 , title = Performance guarantees for hierarchical clustering , volume = 70 , year = 2005 {{citation , last1 = Dyer , first1 = M. E. , author1-link = Martin Dyer , last2 = Frieze , first2 = A. M. , author2-link = Alan M. Frieze , doi = 10.1016/0167-6377(85)90002-1 , issue = 6 , journal = Operations Research Letters , mr = 797340 , pages = 285–288 , title = A simple heuristic for the {{mvar, p-centre problem , url = https://www.math.cmu.edu/~af1p/Texfiles/simpheur.pdf , volume = 3 , year = 1985 {{citation , last1 = Eldar , first1 = Y. , last2 = Lindenbaum , first2 = M. , last3 = Porat , first3 = M. , last4 = Zeevi , first4 = Y. Y. , bibcode = 1997ITIP....6.1305E , doi = 10.1109/83.623193 , issue = 9 , journal = IEEE Transactions on Image Processing , pages = 1305–1315 , title = The farthest point strategy for progressive image sampling , volume = 6 , year = 1997, pmid = 18283019 {{citation , last1 = Eppstein , first1 = David , author1-link = David Eppstein , last2 = Har-Peled , first2 = Sariel , author2-link = Sariel Har-Peled , last3 = Sidiropoulos , first3 = Anastasios , doi = 10.20382/jocg.v11i1a25 , issue = 1 , journal =

Journal of Computational Geometry The ''Journal of Computational Geometry'' (JoCG) is an open access mathematics journal that was established in 2010. It covers research in all aspects of computational geometry. All its papers are published free of charge to both authors and reader ...

, mr = 4194877 , pages = 629–652 , title = Approximate greedy clustering and distance selection for graph metrics , volume = 11 , year = 2020, s2cid = 18316279 {{citation , last1 = Fisher , first1 = Marshall L. , last2 = Jaikumar , first2 = Ramchandran, authorlink2=Ramchandran Jaikumar , doi = 10.1002/net.3230110205 , issue = 2 , journal = Networks , mr = 618209 , pages = 109–124 , title = A generalized assignment heuristic for vehicle routing , volume = 11 , year = 1981; as cited by {{citation , last1 = Gheysens , first1 = Filip , last2 = Golden , first2 = Bruce , last3 = Assad , first3 = Arjang , editor1-last = Gallo , editor1-first = Giorgio , editor2-last = Sandi , editor2-first = Claudio , contribution = A new heuristic for determining fleet size and composition , doi = 10.1007/bfb0121103 , pages = 233–236 , publisher = Springer , series = Mathematical Programming Studies , title = Netflow at Pisa , volume = 26 , year = 1986 {{citation , last1 = Girdhar , first1 = Y. , last2 = Giguère , first2 = P. , last3 = Dudek , first3 = G. , contribution = Autonomous adaptive underwater exploration using online topic modelling , contribution-url = http://cim.mcgill.ca/~yogesh/publications/iser2012.pdf , title = Proc. Int. Symp. Experimental Robotics , year = 2012 {{citation , last = Gonzalez , first = T. F. , authorlink = Teofilo F. Gonzalez , doi = 10.1016/0304-3975(85)90224-5 , issue = 2–3 , journal =

Theoretical Computer Science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

, mr = 807927 , pages = 293–306 , title = Clustering to minimize the maximum intercluster distance , volume = 38 , year = 1985 {{citation , last1 = Gotsman , first1 = Craig , last2 = Allebach , first2 = Jan P. , editor1-last = Rogowitz , editor1-first = Bernice E. , editor2-last = Allebach , editor2-first = Jan P. , contribution = Bounds and algorithms for dither screens , contribution-url = https://www.cs.technion.ac.il/~gotsman/AmendedPubl/BoundsAndAlgorithms/BoundsAndAlg-scanned.pdf , doi = 10.1117/12.238746 , pages = 483–492 , series = Proc. SPIE , title = Human Vision and Electronic Imaging , volume = 2657 , year = 1996, s2cid = 10608234 {{citation , last1 = Har-Peled , first1 = S. , author1-link = Sariel Har-Peled , last2 = Mendel , first2 = M. , arxiv = cs/0409057 , doi = 10.1137/S0097539704446281 , issue = 5 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...

, mr = 2217141 , pages = 1148–1184 , title = Fast construction of nets in low-dimensional metrics, and their applications , volume = 35 , year = 2006, s2cid = 37346335 {{citation , last = Hase , first = Hayo , editor1-last = Rummel , editor1-first = Reinhard , editor2-last = Drewes , editor2-first = Hermann , editor3-last = Bosch , editor3-first = Wolfgang , display-editors = 3 , editor4-last = Hornik , editor4-first = Helmut , contribution = New method for the selection of additional sites for the homogenisation of an inhomogeneous cospherical point distribution , doi = 10.1007/978-3-642-59745-9_35 , pages = 180–183 , publisher = Springer , series = International Association of Geodesy Symposia , title = Towards an Integrated Global Geodetic Observing System (IGGOS): IAG Section II Symposium Munich, October 5-9, 1998, Posters – Session B , year = 2000 {{citation , last1 = Hochbaum , first1 = Dorit S. , author1-link = Dorit S. Hochbaum , last2 = Shmoys , first2 = David B. , author2-link = David Shmoys , doi = 10.1287/moor.10.2.180 , issue = 2 , journal =

Mathematics of Operations Research ''Mathematics of Operations Research'' is a quarterly peer-reviewed scientific journal established in February 1976. It focuses on areas of mathematics relevant to the field of operations research such as continuous optimization, discrete optimiz ...

, mr = 793876 , pages = 180–184 , title = A best possible heuristic for the {{mvar, k-center problem , volume = 10 , year = 1985 For prominent examples of incorrect attribution of the farthest-first heuristic to {{harvtxt, Hochbaum, Shmoys, 1985, see, e.g., *{{citation , last = Dasgupta , first = Sanjoy , editor1-last = Kivinen , editor1-first = Jyrki , editor2-last = Sloan , editor2-first = Robert H. , contribution = Performance guarantees for hierarchical clustering , doi = 10.1007/3-540-45435-7_24 , pages = 351–363 , publisher = Springer , series = Lecture Notes in Computer Science , title = Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings , volume = 2375 , year = 2002 (corrected in the 2005 journal version of the same paper) *{{citation , last1 = Agarwal , first1 = Sameer , last2 = Ramamoorthi , first2 = Ravi , last3 = Belongie , first3 = Serge J. , last4 = Jensen , first4 = Henrik Wann , doi = 10.1145/882262.882314 , issue = 3 , journal = ACM Trans. Graph. , pages = 605–612 , title = Structured importance sampling of environment maps , volume = 22 , year = 2003 *{{citation , last1 = Baram , first1 = Yoram , last2 = El-Yaniv , first2 = Ran , last3 = Luz , first3 = Kobi , journal = J. Mach. Learn. Res. , pages = 255–291 , title = Online choice of active learning algorithms , url = https://jmlr.org/papers/volume5/baram04a/baram04a.pdf , volume = 5 , year = 2004 *{{citation , last1 = Basu , first1 = Sugato , last2 = Bilenko , first2 = Mikhail , last3 = Banerjee , first3 = Arindam , last4 = Mooney , first4 = Raymond J. , editor1-last = Chapelle , editor1-first = Olivier , editor2-last = Schölkopf , editor2-first = Bernhard , editor3-last = Zien , editor3-first = Alexander , contribution = Probabilistic semi-supervised clustering with constraints , doi = 10.7551/mitpress/9780262033589.003.0005 , pages = 73–102 , publisher = The MIT Press , title = Semi-Supervised Learning , year = 2006 *{{citation , last1 = Lima , first1 = Christiane Ferreira Lemos , last2 = Assis , first2 = Francisco M. , last3 = de Souza , first3 = Cleonilson Protásio , contribution = A comparative study of use of Shannon, Rényi and Tsallis entropy for attribute selecting in network intrusion detection , doi = 10.1109/IWMN.2011.6088496 , pages = 77–82 , publisher = IEEE , title = IEEE International Workshop on Measurement and Networking, M&N 2011, Anacapri, Italy, October 10-11, 2011 , year = 2011, s2cid = 7510040 *{{citation, contribution-url=https://weka.sourceforge.io/doc.dev/weka/clusterers/FarthestFirst.html, contribution=Class FarthestFirst, title=

Weka The weka, also known as the Māori hen or woodhen (''Gallirallus australis'') is a flightless bird species of the rail family. It is endemic to New Zealand. It is the only extant member of the genus '' Gallirallus''. Four subspecies are recogni ...

, version 3.9.5, date=December 21, 2020, access-date=2021-11-06, publisher=University of Waikato, via=SourceForge {{citation , last1 = Laine , first1 = Samuli , last2 = Saransaari , first2 = Hannu , last3 = Kontkanen , first3 = Janne , last4 = Lehtinen , first4 = Jaakko , last5 = Aila , first5 = Timo , contribution = Incremental instant radiosity for real-time indirect illumination , doi = 10.2312/EGWR/EGSR07/277-286 , isbn = 978-3-905673-52-4 , location = Aire-la-Ville, Switzerland, Switzerland , pages = 277–286 , publisher = Eurographics Association , title = Proceedings of the 18th Eurographics Conference on Rendering Techniques (EGSR'07) , year = 2007, s2cid = 18626929 {{citation , last1 = Lipman , first1 = Y. , last2 = Funkhouser , first2 = T. , contribution = Möbius voting for surface correspondence , doi = 10.1145/1576246.1531378 , pages = 72:1–72:12 , title = Proc. ACM SIGGRAPH , year = 2009, s2cid = 6001942 {{citation , last1 = Mazer , first1 = E. , last2 = Ahuactzin , first2 = J. M. , last3 = Bessiere , first3 = P. , doi = 10.1613/jair.468 , doi-access = free , journal =

Journal of Artificial Intelligence Research The ''Journal of Artificial Intelligence Research'' (''JAIR'') is an open access peer-reviewed scientific journal covering research in all areas of artificial intelligence. History It was established in 1993 as one of the first scientific journa ...

, pages = 295–316 , title = The Ariadne's clew algorithm , volume = 9 , year = 1998 {{citation , last1 = Moenning , first1 = C. , last2 = Dodgson , first2 = N. A. , contribution = A new point cloud simplification algorithm , title = 3rd IASTED International Conference on Visualization, Imaging, and Image Processing , year = 2003 {{citation , last1 = Ravi , first1 = S. S. , last2 = Rosenkrantz , first2 = D. J. , last3 = Tayi , first3 = G. K. , doi = 10.1287/opre.42.2.299 , issue = 2 , journal =

Operations Research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...

, jstor = 171673 , pages = 299–310 , title = Heuristic and special case algorithms for dispersion problems , volume = 42 , year = 1994 {{citation , last1 = Rosenkrantz , first1 = D. J. , last2 = Stearns , first2 = R. E. , last3 = Lewis , first3 = P. M., II , doi = 10.1137/0206041 , issue = 3 , journal =

, mr = 0459617 , pages = 563–581 , title = An analysis of several heuristics for the traveling salesman problem , volume = 6 , year = 1977 {{citation , last = Ruppert , first = Jim , doi = 10.1006/jagm.1995.1021 , issue = 3 , journal = Journal of Algorithms , pages = 548–585 , title = A Delaunay refinement algorithm for quality 2-dimensional mesh generation , volume = 18 , year = 1995 {{citation , last1 = Shahidi , first1 = R. , last2 = Moloney , first2 = C. , last3 = Ramponi , first3 = G. , bibcode = 2004EJASP2004...45S , doi = 10.1155/S1110865704403217 , doi-access = free , journal = EURASIP Journal on Applied Signal Processing , pages = 1886–1898 , title = Design of farthest-point masks for image halftoning , volume = 2004 , year = 2004, issue = 12 {{citation , last = Tamir , first = Arie , doi = 10.1137/0404048 , issue = 4 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was estab ...

, mr = 1129392 , pages = 550–567 , title = Obnoxious facility location on graphs , volume = 4 , year = 1991 {{citation , last1 = Teramoto , first1 = Sachio , last2 = Asano , first2 = Tetsuo , author2-link = Tetsuo Asano , last3 = Katoh , first3 = Naoki , last4 = Doerr , first4 = Benjamin , bibcode = 2006IEITI..89.2348T , doi = 10.1093/ietisy/e89-d.8.2348 , issue = 8 , journal = IEICE Transactions on Information and Systems , pages = 2348–2356 , title = Inserting points uniformly at every instance , year = 2006 , url = https://search.ieice.org/bin/summary.php?id=e89-d_8_2348 , volume = E89-D {{citation , last = White , first = Douglas J. , doi = 10.1093/imaman/3.2.131 , issue = 2 , journal = IMA Journal of Mathematics Applied in Business and Industry , mr = 1154657 , pages = 131–140 (1992) , title = The maximal-dispersion problem , volume = 3 , year = 1991; White credits the use of the farthest-first traversal as a heuristic for this problem to {{citation , last = Steuer , first = R. E. , location = New York , publisher = Wiley , title = Multiple-Criteria Optimization: Theory, Computation, and Applications , year = 1986 {{citation , last1 = Vieira , first1 = Luiz Filipe M. , last2 = Vieira , first2 = Marcos Augusto M. , last3 = Ruiz , first3 = Linnyer Beatrys , author3-link = Linnyer Beatrys Ruiz Aylon , last4 = Loureiro , first4 = Antonio A. F. , last5 = Silva , first5 = Diógenes Cecílio , last6 = Fernandes , first6 = Antônio Otávio , contribution = Efficient Incremental Sensor Network Deployment Algorithm , contribution-url = http://www.lbd.dcc.ufmg.br/colecoes/sbrc/2004/001.pdf , pages = 3–14 , title = Proc. Brazilian Symp. Computer Networks , year = 2004 {{citation , last = Xiang , first = Z. , doi = 10.1145/256157.256159 , issue = 3 , journal =

ACM Transactions on Graphics ''ACM Transactions on Graphics'' (TOG) is a bimonthly peer-reviewed scientific journal that covers the field of computer graphics. It was established in 1982 and is published by the Association for Computing Machinery. TOG publishes two special iss ...

, pages = 260–276 , title = Color image quantization by minimizing the maximum intercluster distance , volume = 16 , year = 1997, s2cid = 17713417 Computational geometry Approximation algorithms Cluster analysis