ALGORITHMS AND LOWER BOUNDS FOR ONLINE LEARNING OF GEOMETRICAL CONCEPTS

The complexity of on-line learning is investigated for the basic class es of geometrical objects over a discrete (''digitized'') domain. In p articular, upper and lower bounds are derived for the complexity of le arning algorithms for axis-parallel rectangles, rectangles in general position, balls, halfspaces, intersections of half-spaces, and semi-al gebraic sets. The learning model considered is the standard model for on-line learning from counterexamples.