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 root n x root 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 less than or equal to m less than or equal to n), point location (i.e. classification) queries can be answered in Theta(m/root n) time. As it turns out, this is best possible on this platform. (C) 1997 Pattern Recognition Society. Published by Elsevier Science Ltd. [References: 36]