Title: Learning Unions of Rectangles  with Queries 
Author: Zhixiang Chen and Steve Homer, Boston University 
Date: September 1993


Abstract:

We investigate the efficient learnability of unions of $k$ rectangles
in the discrete plane $\{1,\ldots,n\}^{2}$ with equivalence and
membership queries. We exhibit a learning algorithm that learns any
union of $k$ rectangles with $O(k^{3}\log n)$ queries, while the time
complexity of this algorithm is bounded by $O(k^{5}\log n)$.  We
design our learning algorithm by finding ``corners'' and ``edges'' for
rectangles contained in the target concept and then constructing the
target concept from those ``corners'' and ``edges''.  Our result
provides a first approach to on-line learning of nontrivial subclasses
of unions of intersections of halfspaces with equivalence and
membership queries.