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”, Discrete & Computational Geometry, volume 33, number 4, April 2005, pages 593–604.

BibTeX

@Article{VoronoiBoundary_DCG,
  AUTHOR        = {David Bremner and Erik Demaine and Jeff Erickson and
                   John Iacono and Stefan Langerman and Pat Morin and
                   Godfried Toussaint},
  TITLE         = {Output-Sensitive Algorithms for Computing Nearest-Neighbour
                   Decision Boundaries},
  JOURNAL       = {Discrete \& Computational Geometry},
  journalurl    = {http://link.springer.de/link/service/journals/00454/},
  VOLUME        = 33,
  NUMBER        = 4,
  PAGES         = {593--604},
  YEAR          = 2005,
  MONTH         = {April},

  COMMENTS      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-540-45078-8_39">SpringerLink</A>.},
  PAPERS        = {VoronoiBoundary_WADS2003},
  replaces      = {VoronoiBoundary_WADS2003},
  dblp          = {https://dblp.org/rec/journals/dcg/BremnerDEILMT05},
  doi           = {https://dx.doi.org/10.1007/S00454-004-1152-0},
}

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