Proceedings of the 2003 Workshop on Algorithms and Data Structures, 451-461, 2003.

- Download WADS submission:
- Official WADS version from Springer-Verlag (subscription required)

Abstract:

Given a setRof red points and a setBof blue points, thenearest-neighbour decision ruleclassifies a new pointqas red (respectively, blue) if the closest point toqinRUBcomes fromR(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 the plane. Both algorithms run in time O(nlogk), wherekis the number of points that contribute to the decision boundary. This running time is the best possible when parameterizing with respect tonandk.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Dec 2003