Recognition of polyhedral objects: concepts and algorithms
Lakshmi Sankara Narasimhan · 1988
This dissertation deals with the problem of recognizing a polyhedral object in two and three dimensions. We first consider different models for gathering information and state different assumptions that could be made about an unknown object to be recognized. We then consider the problem of recognizing a convex polygon in 2D. We present an algorithm that takes at most 3n - 2 silhouette pictures to recognize a convex polygon with n sides. After establishing this we show that any algorithm will require at least 3n - 5 silhouette pictures in the worst case. We provide a scheme that recognizes a convex polygon in 2D using six nodules pictures. We show that three x-ray histogram pictures are necessary and sufficient to recognize any polygon in 2D under a mild assumption. We present an algorithm that takes 2h + 6 nodules pictures to recognize polygons from certain class of nonconvex polygons in 2D, where h stands for the number of vertices of the convex hull of the object. After that we give a procedure that uses at most 3n + 6 nodules pictures and 6n finger probes to recognize objects from another class of nonconvex polygons in 2D. We then consider the problem of recognizing a convex polyhedron in three dimensions. We develop an algorithm that uses at most 5f + v finger probes, where f and v stand for the number of faces (facets) and vertices of the polyhedron respectively. We provide another algorithm that takes at most 2v + f silhouette pictures for this problem. We show that four line drawings (photographs) are necessary and sufficient for the recognition of a convex polyhedron in 3D. In this work, we also compare and contrast these models in an attempt to develop a hierarchical ordering of models for gathering information.