An algorithm for deciding congruence of polyhedra.

Abstract

The problem of deciding whether two objects are of the same shape, i. e., similar or not, is very important in the classification of shapes of objects for robot vision and in the creation of knowledge-based systems. A new algorithm for this problem, which is based on the idea of decomposing a polyhedron into convex polyhedra and connecting them with the hierarchical tree structure, is presented. The algorithm consists of the following two procedures : 1) Whether two hierarchical tree structures for two polyhedra equal each other or not is tested. 2) Whether two convex polyhedra belonging to each node equal each other or not is decided. The number of operations is proportional to the number of vertices, if the vertices are uniformly distributed in 3-D space. Otherwise, the running time becomes proportional to n log n, where n is the number of vertices of a polyhedron. The program is written in FORTRAN language and the running times for the various polyhedra are measured. The results guarantee the theoretical considerations.