@inbook{c5ea6643a22040118037c9c1629f3b3f,
title = "Output-sensitive algorithms for computing nearest-neighbour decision boundaries",
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.",
author = "David Bremner and Erik Demaine and Jeff Erickson and John Iacono and Stefan Langerman and Pat Morin and Godfried Toussaint",
year = "2003",
doi = "10.1007/978-3-540-45078-8_39",
language = "English (US)",
isbn = "3540405453",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "451--461",
editor = "Frank Dehne and Jorg-Rudiger Sack and Michiel Smid",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}