Fast identification of geometric objects with membership queries
William J. Bultman, Wolfgang Maass · Conference on Learning Theory · 1991
We investigate the number of membership queries that are needed to identify polygons (i.e., intersections of halfplanes) over a two-dimensional grid {0, …, n - l} 2 . We exhibit a learning algorithm that learns 100% correctly, while requiring no random examples and not more membership queries than previous algorithms needed in addition to their random examples for probably almost correctly learning (even for moderate values of δ). Furthermore, the learning algorithm in this paper only uses grid points for its membership queries. This appears to be appropriate in situations where the probing device only has a limited resolution, and for applications to the set of pixels on a two-dimensional screen.