Probing a scene of non convex polyhedra

ABSTRACT

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.

REFERENCES

• 1: P. D. Alevizos , J. Boissonnat , M. Yvinec, An optimal O(n log n) algorithm for contour reconstruction from rays, Proceedings of the third annual symposium on Computational geometry, p.162-170, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41975]
• 2: Alevizos P.D., Boissonnat J.D., Yvinec M., Probing non convex polygons, Proc. IEEE Int. Conf. on Robotics and Automation, Phoenix (May 1989).
• 3: H. J. Bernstein, Determining the shape of a convex n-sided polygon by using 2n+k tactile probes, Information Processing Letters, v.22 n.5, p.255-260, April 1986 [doi>10.1016/0020-0190(86)90103-1]
• 4: Richard Cole , Chee K. Yap, Shape from probing, Journal of Algorithms, v.8 n.1, p.19-38, March 1987 [doi>10.1016/0196-6774(87)90025-3]
• 5: D Dobkin , H Edelsbrunner , C K Yap, Probing convex polytopes, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.424-432, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12174]
• 6: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 7: Steven Sol Skiena , Herbert Edelsbrunner, Geometric probing, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  E. Data

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Measurement, Theory