Data communication and computational geometry on the star and pancake interconnection networks

The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, little has been done to design parallel algorithms on these networks. The paper presents several data communication algorithms that are fundamental to designing algorithms on these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the data communication algorithms proposed can be applied. It is believed that these algorithms are interesting and important in their own right, and are basic to the design of solutions on the star and pancake networks to a host of other problems.