Open problems in geometric methods for instance-based learning

In the typical approach to instance-based learning, random data (the training set of patterns) are collected and used to design a decision rule (classifier). One of the most well known such rules is the k-nearest-neighbor decision rule in which an unknown pattern is classified into the majority class among its k nearest neighbors in the training set. In the past fifty years many approaches have been proposed to improve the performance of this rule. More recently geometric methods have been found to be the best. Here we mention a variety of open problems of a computational geometric nature that arize in these methods. To provide some context and motivation for these open problems we briefly describe the methods and list some key references.