Optimal computation of the contour of maximal elements on mesh-connected computers
Manzur Murshed, Markus Hegland · ANU Open Research (Australian National University) · 1998
: Dehne presented an optimal algorithm to compute the contour of the maximal elements of n planar points on a p n \\Theta p n mesh. We have calculated that Dehne's algorithm requires 23 p n steps and we have been able to reduce the required steps to 19 p n through pre-sorting and using an efficient strategy in dividing the mesh into halves. It has also been established that any implementation of Dehne's algorithm requires at least 15 p n steps. We have further developed a new optimal algorithm which requires at most 10 p n steps. Key Words: Mesh-Connected Computer, Parallel Algorithm, Computational Geometry. 1 Introduction Despite the large communication diameter, the meshconnected computer, defined in Sec. 2.1, has been given considerable attention because of its simplicity, regularity of interconnection pattern, and modularity of the layout which make it an ideal model for VLSI applications. A large number of efficient algorithms have been developed on meshes for a variety...