AI Glossary / AI and machine learning / Advanced

Farthest-first traversal

Definition

Farthest-first traversal orders points by repeatedly selecting the point whose distance to its nearest previously selected point is greatest. Starting from an initial point, it builds a sequence that progressively covers poorly represented parts of a dataset.

What it means

The phrase farthest-first can be misleading unless the reference is clear. Each new point is farthest from the selected set in the nearest-neighbor sense. It is not necessarily farthest from the most recently chosen point or from the original starting point.

Taking the first k selected points gives a simple approach to choosing representative centers. The method is associated with greedy approximation for metric k-center problems. Its usefulness depends on whether the distance measure represents meaningful differences for the task.

How it works

Choose the first point and calculate every other point's distance to it. Select the point with the largest distance. After each selection, update every unselected point's distance to its nearest selected center, keeping the smaller of its previous value and its distance to the new center.

Repeat until the desired number of centers is reached, or continue to order all points. For the standard metric k-center setting, this greedy approach has a factor-two approximation guarantee for the maximum nearest-center distance. That guarantee depends on the problem assumptions and does not turn arbitrary similarity scores into metrics.

Three practical examples

1. A data-review team can choose examples spread across a feature space to inspect a broader range of patterns than a single dense cluster would provide.

2. A geographical planning exercise can choose candidate centers to limit worst-case distance under a specified metric, before adding real operating constraints.

3. A visualization tool can select a manageable set of diverse points from a large collection. The selected points provide coverage, but should not be treated as a statistically representative random sample.

Think of it this way

Imagine placing help desks on a map by repeatedly serving the location currently farthest from any desk. Each new desk addresses the largest remaining gap in coverage.

The analogy leaves out capacity, staffing and road restrictions. If those factors matter, they need additional modeling; farthest-first traversal alone does not solve a complete facility-planning problem.

Worked example

Take points at positions 0, 2, 3, 8 and 10 on a line, using ordinary distance. Start at 0. The farthest point is 10, so select it next.

The remaining nearest-center distances are: point 2 has distance 2; point 3 has distance 3; point 8 has distance 2. Therefore the third selected point is 3, not 8, even though 8 is far from the initial point 0.

With centers 0, 10 and 3, the nearest-center distances of the two remaining points are 1 for point 2 and 2 for point 8. The current maximum coverage distance is 2. This illustrates the update rule and why distance must be measured against the whole selected set.

Illustrative case study

Fictional image-curation team FrameDesk needs a small set of images for an initial review. It runs farthest-first selection on image embeddings to cover different visual patterns.

Some selected images are corrupted files that sit far from normal images. The team separates data-quality checks from diversity selection and repeats the exercise on valid images. It also keeps a random sample for estimating ordinary error rates. The diverse subset helps exploration, while the random sample serves a different statistical purpose. The example does not claim that embedding distance perfectly captures human visual meaning.

Common misconceptions and mistakes

Selecting the point farthest from the latest center is a different procedure. Always maintain distance to the nearest member of the entire selected set. Ties and the initial point can change the resulting order, so record those choices when reproducibility matters.

Another mistake is assuming coverage equals representativeness. The method can emphasize outliers and sparse regions. It also does not minimize the same objective as k-means, which concerns squared distances to centroids. State the actual objective before comparing the methods or claiming one is better.

Business use

Farthest-first traversal can support exploration, prototype selection and simplified coverage problems. It is attractive because the selection rule is straightforward to explain. Its output is only as meaningful as the representation and distance measure behind it.

For a review workflow, decide whether the purpose is finding varied cases, estimating typical performance or discovering rare failures. Those goals may require different samples. For location planning, assess capacity, access and feasible candidate sites separately. A geometric approximation guarantee does not certify that the resulting operational plan meets every business requirement.

People also ask

Does it need labels?

No. The basic selection uses distances between points, not class labels.

Is the first point important?

It can affect the order and selected centers, even though the standard approximation guarantee allows an arbitrary starting point under its assumptions.

Is this the same as k-means++?

No. They use different selection rules and support different optimization objectives; k-means++ uses a probabilistic initialization based on squared distances.

Check your understanding

A point is far from the first center but very close to a later center. Should its selection priority remain high?

Answer: No. Its distance to the selected set is the distance to the nearest selected center. Once a nearby center exists, that point is already well covered under the metric.

Related terms

• Greedy algorithms
• Clustering
• Outlier
• k-means
• Metric k-center
• greedy algorithm
• approximation algorithm
• representative sampling
• distance metric

Learn next

Repeat the worked example from a different starting point. Then add one distant outlier and observe its effect. Compare a coverage-oriented selection with a random sample and explain which questions each can answer.

• Outlier

More in AI and machine learning

• Extremal Ensemble Learning - Extremal Ensemble Learning, or EEL, is a research approach that iteratively updates an ensemble of candidate solutions using their relative quality.
• Extremal optimization - Extremal optimization is a heuristic search method that preferentially changes poorly performing components of a candidate solution.
• Factor graph - A factor graph represents how a function of several variables can be written as a product of smaller functions called factors.
• Feature - A feature is one measurable input field a model learns from, such as a customer's age, an order's total or the hour a call arrived.
• Feature cross - A feature cross is a new input made by combining two or more existing fields, so the model can learn patterns that only appear when the fields interact.
• Feature cutoff - A feature cutoff is a threshold that drops feature values below a set frequency or importance, keeping the input space small enough to be useful.

Sources

Gonzalez, Clustering to Minimize the Maximum Intercluster Distance, 1985: https://www.cs.columbia.edu/~verma/classes/uml/ref/clustering_minimize_intercluster_distance_gonzalez.pdf. ELKI official GreedyKCenter documentation: https://elki-project.github.io/releases/current/doc/elki/clustering/kcenter/GreedyKCenter.html. The line example and FrameDesk case are original illustrations.

Previous: Fan chart (time series) Next: Fast decay