HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Probing a scene of non convex polyhedra

Abstract : We show, in this paper, how one can compute the exact shapes of a class of polyhedral scenes by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces and such that no edge is contained in the supporting plane of a non incident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows to compute the exact shape of a simple polygon with no collinear edges by means of at most 3n - 3 probes, where n is the number of edges of the polygon. This is optimal in the worst-case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists of k polyhedra with altogether n faces and m edges, we show that (10,3) n(m + k) - 2m - 3k probes are sufficient to compute the exact shapes of the polyhedra.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:14:45 PM
Last modification on : Thursday, March 17, 2022 - 10:08:26 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:05:17 PM


  • HAL Id : inria-00075449, version 1



Jean-Daniel Boissonnat, Mariette Yvinec. Probing a scene of non convex polyhedra. [Research Report] RR-1110, INRIA. 1989. ⟨inria-00075449⟩



Record views


Files downloads