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”, 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.
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 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 \copyright Springer-Verlag.
- The paper is 12 pages.
- 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.
These pages are generated automagically from a
Last updated May 5, 2021 by