Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries |
| |
| Authors: | David Bremner Erik Demaine Jeff Erickson John Iacono Stefan Langerman Pat Morin Godfried Toussaint |
| |
| Institution: | (1) Faculty of Computer Science, University of New Brunswick, Fredericton, New Brunswick, E3B 5A3, Canada;(2) Laboratory for Computer Science, MIT, 32 Vassar Street, Cambridge, MA 02139, USA;(3) Computer Science Department, University of Illinois, Urbana, IL 61801-2302, USA;(4) Department of Computer and Information Science, Polytechnic University, 6 MetroTech Center, Brooklyn, NY 11201, USA;(5) Charge de recherches du FNRS, Universite Libre de Bruxelles, ULB CP212, boulevard du Triomphe, 1050 Bruxelles , Belgium;(6) School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5BL , Canada;(7) School of Computer Science, McGill University, Montreal, Quebec H3A 2A7, Canada |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
