Output-sensitive algorithms for computing nearest-neighbour decision boundaries

David Bremner; Erik Demaine; Jeff Erickson; John Iacono; Stefan Langerman; Pat Morin; Godfried Toussaint

Output-sensitive algorithms for computing nearest-neighbour decision boundaries

David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

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

Original language	English (US)
Pages (from-to)	451-461
Number of pages	11
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2748
State	Published - Dec 1 2003

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Cite this

Output-sensitive algorithms for computing nearest-neighbour decision boundaries. / Bremner, David; Demaine, Erik; Erickson, Jeff et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2748, 01.12.2003, p. 451-461.

Research output: Contribution to journal › Article › peer-review

@article{7989635c830a43499dfe023163d7c146,

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",

month = dec,

day = "1",

language = "English (US)",

volume = "2748",

pages = "451--461",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - Output-sensitive algorithms for computing nearest-neighbour decision boundaries

AU - Bremner, David

AU - Demaine, Erik

AU - Erickson, Jeff

AU - Iacono, John

AU - Langerman, Stefan

AU - Morin, Pat

AU - Toussaint, Godfried

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35248827671&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248827671&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:35248827671

SN - 0302-9743

VL - 2748

SP - 451

EP - 461

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Output-sensitive algorithms for computing nearest-neighbour decision boundaries

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this