Paper by Erik D. Demaine

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². 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)