Paper by Erik D. Demaine
- 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.
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.
- This paper is also available from SpringerLink.
- 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.
These pages are generated automagically from a
Last updated July 25, 2017 by