ANU Computer Science Technical Reports

TR-CS-98-06

M. Manzur Murshed.
Optimal computation of the contour of maximal elements on mesh-connected computers.
July 1998.

[POSTSCRIPT (156877 bytes)] [PDF (275769 bytes)] [EPrints archive]

Abstract: Dehne presented an optimal algorithm to compute the contour of the maximal elements of n planar points on a sqrt(n) × sqrt(n) mesh. We have calculated that Dehne's algorithm requires 23 sqrt(n) steps and we have been able to reduce the required steps to 19 sqrt(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 sqrt(n) steps. We have further developed a new optimal algorithm which requires at most 10 sqrt(n) steps.

Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>

Last modified: Tue May 31 12:56:00 EST 2011