Probing a scene of non convex polyhedra
Jean Daniel Boissonnat, Mariette Yvinec · 1989
We show, in this paper, how one can probe a class of non convex polyhedra and scenes of disjoint such polyhedra. A polyhedron of that class has convex faces; any two faces are not coplanar and any two edges are not colinear. The basic step of our method is a strategy for probing a single simple polygon with no colinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that discovers the exact shape of a simple polygon with no colinear edges by means of at most 3n - 3 probes, which is shown to be optimal in the worst-case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in the supporting planes of the faces of a scene of polyhedra of the class above. If the scene consists of k polyhedra with altogether n faces, we show that 8n2 - 6n + k probes are sufficient to discover the exact shapes of the polyhedra.