**Reference**:- David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint, “Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries”, in
*Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS 2003)*, Lecture Notes in Computer Science, volume 2748, Ottawa, Ontario, Canada, July 30–August 1, 2003, pages 451–461. **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*union*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*. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (671k), gzipped PostScript (182k), and PDF (159k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- VoronoiBoundary_DCG (Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries)

See also other papers by Erik Demaine.

Last updated September 13, 2019 by Erik Demaine.