Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.pdf

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries? David Bremner1, Erik Demaine2, Jeff Erickson3, John Iacono4, Stefan Langerman5, Pat Morin6, and Godfried Toussaint7 1 Faculty of Computer Science, University of New Brunswick, bremner@unb.ca 2 MIT Laboratory for Computer Science, edemaine@mit.edu 3 Computer Science Department, University of Illinois, jeffe@cs.uiuc.edu 4 Polytechnic University, jiacono@poly.edu 5 Charge? de recherches du FNRS, Universite? Libre de Bruxelles, stefan.langerman@ulb.ac.be 6 School of Computer Science, Carleton University, morin@cs.carleton.ca 7 School of Computer Science, McGill University, godfried@cs.mcgill.ca Abstract. 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 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 R2. 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. 1 Introduction Let S be a set of n points in the plane that is partitioned into a set of red points denoted by R and a set of blue points denoted by B. The nearest-neighbour deci- sion rule classifies a new point q as the color of the closest point to q in S. The nearest-neighbour decision rule is popular in pattern recognition as a means of learning by example. For this reason, the set S is often referred to as a training set. Several properties make the nearest-neighbour decision rule quite attractive, including its intuitive simplicity and the theorem that the asymptotic error rate of the nearest-neighbour rule is bounded from above by twice