  We analyse optimum reject strategies for prototype-based classifiers and
real-valued rejection measures, using the distance of a data point to the
closest prototype or probabilistic counterparts. We compare reject schemes with
global thresholds, and local thresholds for the Voronoi cells of the
classifier. For the latter, we develop a polynomial-time algorithm to compute
optimum thresholds based on a dynamic programming scheme, and we propose an
intuitive linear time, memory efficient approximation thereof with competitive
accuracy. Evaluating the performance in various benchmarks, we conclude that
local reject options are beneficial in particular for simple prototype-based
classifiers, while the improvement is less pronounced for advanced models. For
the latter, an accuracy-reject curve which is comparable to support vector
machine classifiers with state of the art reject options can be reached.
