Testing orthogonal shapes

A testing algorithm takes a model and produces a set of points that can be used to test whether or not an unknown object is sufficiently similar to the model. A testing algorithm performs a complementary task to that performed by a learning algorithm, which takes a set of examples and builds a model that succinctly describes them. Testing can also be viewed as a type of geometric probing that uses point probes (i.e. test points) to verify that an unknown geometric object is similar to a given model. In this paper we examine the problem of verifying orthogonal shapes using test points. In particular, we give testing algorithms for sets of disjoint rectangles in two and higher dimensions and for general orthogonal shapes in 2-D and 3-D. This work is a first step towards developing efficient testing algorithms for objects with more general shapes, including those with non-orthogonal and curved surfaces.