Convexity and Domination Algorithms for Hypercube Computers

Efficient Convexity and Domination Algorithms for Fine- and Medium-Grain Hypercube Computers

Ed Cohen, Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Elias M. Sarraf
Amherst Systems Inc.

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. A hypercube is a type of parallel computer, with the processors linked together as a hypercube graph. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine-grain and medium-grain hypercube computers. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the time. On a hypercube computer the time required to sort is still not fully understood, so the times of some of our algorithms for unsorted data are not completely determined. For the fine-grain model using worst-case timing we show that if the data are presorted then faster algorithms are possible, provided that sorting one item per processor requires time growing faster than the dimension of the hypercube. For both models we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.

Keywords: convex hull, domination, sorting, hypercube algorithms, computational geometry, worst-case, expected case, parallel algorithm, parallel computer, supercomputing, computer science

Complete paper. This appeared in Algorithmica 7 (1992), pp. 51-75, and was scanned at The Hong Kong University of Science and Technology.

Other papers in parallel computing
Overview of work on parallel computing