Carleton University
Technical Report TR-03-01
February 2003
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfired Toussaint
Abstract
iven 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 R ∪ B 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 R 2. 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.