Learning separations by Boolean combinations of half-spaces

Given two subsets S₁ and S₂ (not necessarily finite) of ℜ^d separable by a Boolean combination of N halfspaces, the authors consider the problem of learning the separation function from a finite set of examples. The solution consists of a system of N perceptrons and a single consolidator which combines the outputs of the individual perceptrons. The authors show that an off-line version of this problem where the examples are given in a batch, can be solved in time polynomial in the number of examples. The authors also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm