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 ℝ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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Bremner, D., Demaine, E., Erickson, J. et al. Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries. Discrete Comput Geom 33, 593–604 (2005). https://doi.org/10.1007/s00454-004-1152-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-004-1152-0