Finding Relevant Points for Nearest-Neighbor Classification
  In nearest-neighbor classification problems, a set of $d$-dimensional
training points are given, each with a known classification, and are used to
infer unknown classifications of other points by using the same classification
as the nearest training point. A training point is relevant if its omission
from the training set would change the outcome of some of these inferences. We
provide a simple algorithm for thinning a training set down to its subset of
relevant points, using as subroutines algorithms for finding the minimum
spanning tree of a set of points and for finding the extreme points (convex
hull vertices) of a set of points. The time bounds for our algorithm, in any
constant dimension $d\ge 3$, improve on a previous algorithm for the same
problem by Clarkson (FOCS 1994).
