Improved Search of Relevant Points for Nearest-Neighbor Classification
  Given a training set $P \subset \mathbb{R}^d$, the nearest-neighbor
classifier assigns any query point $q \in \mathbb{R}^d$ to the class of its
closest point in $P$. To answer these classification queries, some training
points are more relevant than others. We say a training point is relevant if
its omission from the training set could induce the misclassification of some
query point in $\mathbb{R}^d$. These relevant points are commonly known as
border points, as they define the boundaries of the Voronoi diagram of $P$ that
separate points of different classes. Being able to compute this set of points
efficiently is crucial to reduce the size of the training set without affecting
the accuracy of the nearest-neighbor classifier.
  Improving over a decades-long result by Clarkson, in a recent paper by
Eppstein an output-sensitive algorithm was proposed to find the set of border
points of $P$ in $O( n^2 + nk^2 )$ time, where $k$ is the size of such set. In
this paper, we improve this algorithm to have time complexity equal to $O( nk^2
)$ by proving that the first steps of their algorithm, which require $O( n^2 )$
time, are unnecessary.
