EMBEDDING PYRAMIDS INTO 3D MESHES

The pyramid architecture is a powerful topology in the area of compute r vision. On the other hand, the 3D mesh architecture possesses rich t opological features which make it suitable for building scalable paral lel processor systems. The usefulness of these two architectures has l ed us to consider the problem of embedding pyramids into 3D meshes, fo r which we present two solutions. The first solution, termed natural e mbedding, maps a pyramid into a 3D mesh such that each level of the py ramid is mapped to a single level of the 3D mesh. The second solution, termed multiple embedding, allows simultaneous embedding of multiple pyramids into a single 3D mesh. The quality of both solutions is evalu ated using dilation and expansion measures. Using the multiple embeddi ng, we are able to obtain an average dilation of 1.26 and a near-optim al expansion of 1.12. (C) 1996 Academic Press, Inc.