Output-sensitive algorithms for computing nearest-neighbor decision boundaries

Written with David Bremner, Erik D. Demaine, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint.

Proceedings of the 2003 Workshop on Algorithms and Data Structures, 451-461, 2003.

Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in RUB comes from R (respectively, B). This rule implicitly partitions space into a red set and a blue set that are separated by a red-blue decision boundary. In this paper we develop output-sensitive algorithms for computing this decision boundary for point sets on the line and in the plane. Both algorithms run in time O(n log k), where k is the number of points that contribute to the decision boundary. This running time is the best possible when parameterizing with respect to n and k.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Dec 2003