**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”,
*Discrete & Computational Geometry*, volume 33, number 4, April 2005, pages 593–604. **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**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.
**Availability**:- The paper is available in PostScript (646k), gzipped PostScript (177k), and PDF (223k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- VoronoiBoundary_WADS2003 (Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries)

See also other papers by Erik Demaine.

Last updated July 21, 2021 by Erik Demaine.