A characterization of nearest-neighbor rule decision surfaces and a new approach to generate them

摘要

The paper considers generating nearest-neighbor rule decision surfaces as an application of a maxmin problem. The maxmin problem is to locate a point in a given convex polyhedron which maximizes the minimum distance from a given set of points in the polyhedron. A characterization of the decision surfaces in n-dimensions is given, and the difficulty involved in generating the decision surfaces in higher dimensional spaces is brought out through this characterization. However, a novel method is presented to generate the surfaces in three dimensions using the algorithm for the maxmin problem.