LNCS 2748 Output Sensitive Algorithms for
Computing Nearest Neighbour Decision Boundaries
1st Edition by David Bremner, Erik Demaine, Jeff
Erickson, John Iacono, Stefan Langerman, Pat
Morin, Godfried Toussaint ISBN 3540450785
https://ebookball.com/product/lncs-2748-output-sensitive-
9783540450788 pdf download
algorithms-for-computing-nearest-neighbour-decision-
boundaries-1st-edition-by-david-bremner-erik-demaine-jeff-
erickson-john-iacono-stefan-langerman-pat-morin-godfried-toussa/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
LNCS 2748 Distribution Sensitive Binomial Queues 1st Edition by Amr
Elmasry ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-distribution-sensitive-
binomial-queues-1st-edition-by-amr-elmasry-
isbn-3540450785-9783540450788-13892/
LNCS 2748 The Traveling Salesman Problem for Cubic Graphs 1st Edition
by David Eppstein ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-the-traveling-salesman-
problem-for-cubic-graphs-1st-edition-by-david-eppstein-
isbn-3540450785-9783540450788-11358/
LNCS 2748 Bandwidth Constrained Allocation in Grid Computing 1st
Edition by Anshul Kothari, Subhash Suri, Yunhong Zhou ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-bandwidth-constrained-
allocation-in-grid-computing-1st-edition-by-anshul-kothari-
subhash-suri-yunhong-zhou-isbn-3540450785-9783540450788-13666/
Geometric Restrictions on Producible Polygonal Protein Chains 1st
edition by Erik Demaine, Stefan Langerman, Joseph O’Rourke ISBN
3540206958 9783540206958
https://ebookball.com/product/geometric-restrictions-on-
producible-polygonal-protein-chains-1st-edition-by-erik-demaine-
stefan-langerman-joseph-oaeurtmrourke-
isbn-3540206958-9783540206958-10614/
,LNCS 2748 Multi way Space Partitioning Trees 1st Edition by Christian
Duncan ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-multi-way-space-
partitioning-trees-1st-edition-by-christian-duncan-
isbn-3540450785-9783540450788-11918/
LNCS 2748 Multi party Pseudo Telepathy 1st Edition by Gilles
Brassard, Anne Broadbent, Alain Tapp ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-multi-party-pseudo-
telepathy-1st-edition-by-gilles-brassard-anne-broadbent-alain-
tapp-isbn-3540450785-9783540450788-9908/
LNCS 2748 Optimal Worst Case Operations for Implicit Cache Oblivious
Search Trees 1st Edition by Gianni Franceschini, Roberto Grossi ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-optimal-worst-case-
operations-for-implicit-cache-oblivious-search-trees-1st-edition-
by-gianni-franceschini-roberto-grossi-
isbn-3540450785-9783540450788-9926/
LNCS 2748 Sorting Circular Permutations by Reversal 1st Edition by
Andrew Solomon, Paul Sutcliffe, Raymond Lister ISBN 3540450785
9783540450788
https://ebookball.com/product/lncs-2748-sorting-circular-
permutations-by-reversal-1st-edition-by-andrew-solomon-paul-
sutcliffe-raymond-lister-isbn-3540450785-9783540450788-13756/
LNCS 2748 Common Deadline Lazy Bureaucrat Scheduling Problems 1st
Edition by Behdad Esfahbod, Mohammad Ghodsi, Ali Sharifi ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-common-deadline-lazy-
bureaucrat-scheduling-problems-1st-edition-by-behdad-esfahbod-
mohammad-ghodsi-ali-sharifi-isbn-3540450785-9783540450788-13214/
, Output-Sensitive Algorithms for Computing
Nearest-Neighbour Decision Boundaries
David Bremner1 , Erik Demaine2 , Jeff Erickson3 , John Iacono4 ,
Stefan Langerman5 , Pat Morin6 , and Godfried Toussaint7
1
Faculty of Computer Science, University of New Brunswick,
2
MIT Laboratory for Computer Science,
3
Computer Science Department, University of Illinois,
4
Polytechnic University,
5
Chargé de recherches du FNRS, Université Libre de Bruxelles,
6
School of Computer Science, Carleton University,
7
School of Computer Science, McGill University,
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 (respec-
tively, 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 bound-
ary 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.
1 Introduction
Let S be a set of n points in the plane that is partitioned into a set of red points
denoted by R and a set of blue points denoted by B. The nearest-neighbour
decision rule classifies a new point q as the color of the closest point to q in
S. The nearest-neighbour decision rule is popular in pattern recognition as a
means of learning by example. For this reason, the set S is often referred to as
a training set.
Several properties make the nearest-neighbour decision rule quite attractive,
including its intuitive simplicity and the theorem that the asymptotic error rate
of the nearest-neighbour rule is bounded from above by twice the Bayes error
rate [6,8,16]. (See [17] for an extensive survey of the nearest-neighbour decision
rule and its relatives.) Furthermore, for point sets in small dimensions, there are
efficient and practical algorithms for preprocessing a set S so that the nearest
neighbour of a query point q can be found quickly.
This research was partly funded by the Alexander von Humboldt Foundation and
The Natural Sciences and Engineering Research Council of Canada.
F. Dehne, J.-R. Sack, M. Smid (Eds.): WADS 2003, LNCS 2748, pp. 451–461, 2003.
c Springer-Verlag Berlin Heidelberg 2003
Computing Nearest Neighbour Decision Boundaries
1st Edition by David Bremner, Erik Demaine, Jeff
Erickson, John Iacono, Stefan Langerman, Pat
Morin, Godfried Toussaint ISBN 3540450785
https://ebookball.com/product/lncs-2748-output-sensitive-
9783540450788 pdf download
algorithms-for-computing-nearest-neighbour-decision-
boundaries-1st-edition-by-david-bremner-erik-demaine-jeff-
erickson-john-iacono-stefan-langerman-pat-morin-godfried-toussa/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
LNCS 2748 Distribution Sensitive Binomial Queues 1st Edition by Amr
Elmasry ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-distribution-sensitive-
binomial-queues-1st-edition-by-amr-elmasry-
isbn-3540450785-9783540450788-13892/
LNCS 2748 The Traveling Salesman Problem for Cubic Graphs 1st Edition
by David Eppstein ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-the-traveling-salesman-
problem-for-cubic-graphs-1st-edition-by-david-eppstein-
isbn-3540450785-9783540450788-11358/
LNCS 2748 Bandwidth Constrained Allocation in Grid Computing 1st
Edition by Anshul Kothari, Subhash Suri, Yunhong Zhou ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-bandwidth-constrained-
allocation-in-grid-computing-1st-edition-by-anshul-kothari-
subhash-suri-yunhong-zhou-isbn-3540450785-9783540450788-13666/
Geometric Restrictions on Producible Polygonal Protein Chains 1st
edition by Erik Demaine, Stefan Langerman, Joseph O’Rourke ISBN
3540206958 9783540206958
https://ebookball.com/product/geometric-restrictions-on-
producible-polygonal-protein-chains-1st-edition-by-erik-demaine-
stefan-langerman-joseph-oaeurtmrourke-
isbn-3540206958-9783540206958-10614/
,LNCS 2748 Multi way Space Partitioning Trees 1st Edition by Christian
Duncan ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-multi-way-space-
partitioning-trees-1st-edition-by-christian-duncan-
isbn-3540450785-9783540450788-11918/
LNCS 2748 Multi party Pseudo Telepathy 1st Edition by Gilles
Brassard, Anne Broadbent, Alain Tapp ISBN 3540450785 9783540450788
https://ebookball.com/product/lncs-2748-multi-party-pseudo-
telepathy-1st-edition-by-gilles-brassard-anne-broadbent-alain-
tapp-isbn-3540450785-9783540450788-9908/
LNCS 2748 Optimal Worst Case Operations for Implicit Cache Oblivious
Search Trees 1st Edition by Gianni Franceschini, Roberto Grossi ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-optimal-worst-case-
operations-for-implicit-cache-oblivious-search-trees-1st-edition-
by-gianni-franceschini-roberto-grossi-
isbn-3540450785-9783540450788-9926/
LNCS 2748 Sorting Circular Permutations by Reversal 1st Edition by
Andrew Solomon, Paul Sutcliffe, Raymond Lister ISBN 3540450785
9783540450788
https://ebookball.com/product/lncs-2748-sorting-circular-
permutations-by-reversal-1st-edition-by-andrew-solomon-paul-
sutcliffe-raymond-lister-isbn-3540450785-9783540450788-13756/
LNCS 2748 Common Deadline Lazy Bureaucrat Scheduling Problems 1st
Edition by Behdad Esfahbod, Mohammad Ghodsi, Ali Sharifi ISBN
3540450785 9783540450788
https://ebookball.com/product/lncs-2748-common-deadline-lazy-
bureaucrat-scheduling-problems-1st-edition-by-behdad-esfahbod-
mohammad-ghodsi-ali-sharifi-isbn-3540450785-9783540450788-13214/
, Output-Sensitive Algorithms for Computing
Nearest-Neighbour Decision Boundaries
David Bremner1 , Erik Demaine2 , Jeff Erickson3 , John Iacono4 ,
Stefan Langerman5 , Pat Morin6 , and Godfried Toussaint7
1
Faculty of Computer Science, University of New Brunswick,
2
MIT Laboratory for Computer Science,
3
Computer Science Department, University of Illinois,
4
Polytechnic University,
5
Chargé de recherches du FNRS, Université Libre de Bruxelles,
6
School of Computer Science, Carleton University,
7
School of Computer Science, McGill University,
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 (respec-
tively, 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 bound-
ary 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.
1 Introduction
Let S be a set of n points in the plane that is partitioned into a set of red points
denoted by R and a set of blue points denoted by B. The nearest-neighbour
decision rule classifies a new point q as the color of the closest point to q in
S. The nearest-neighbour decision rule is popular in pattern recognition as a
means of learning by example. For this reason, the set S is often referred to as
a training set.
Several properties make the nearest-neighbour decision rule quite attractive,
including its intuitive simplicity and the theorem that the asymptotic error rate
of the nearest-neighbour rule is bounded from above by twice the Bayes error
rate [6,8,16]. (See [17] for an extensive survey of the nearest-neighbour decision
rule and its relatives.) Furthermore, for point sets in small dimensions, there are
efficient and practical algorithms for preprocessing a set S so that the nearest
neighbour of a query point q can be found quickly.
This research was partly funded by the Alexander von Humboldt Foundation and
The Natural Sciences and Engineering Research Council of Canada.
F. Dehne, J.-R. Sack, M. Smid (Eds.): WADS 2003, LNCS 2748, pp. 451–461, 2003.
c Springer-Verlag Berlin Heidelberg 2003
