A time-optimal solution to a classification problem in ordered functional domains, with applications

摘要

Consider a family C of classifiers represented by continuous functions stored, in discretized form, one function per processor in one column of a mesh with multiple broadcasting of size √n × √n In a number of contexts in pattern recognition, morphology, and knowledge engineering applications, it is necessary to answer point location queries with respect to the given classifiers. The main contribution of this work is to show that in such a domain a collection of m (1 ⪕ m ⪕ n), point location (i.e. classification) queries can be answered in Θ(m/ √m) time. As it turns out, this is best possible on this platform.