Efficient Convexity and Domination Algorithms
for Fine and MediumGrain 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 finegrain
and mediumgrain 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 finegrain model using
worstcase 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 expectedcase 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, worstcase, expected case, parallel algorithm,
parallel computer, supercomputing, computer science
Complete paper.
This appeared in Algorithmica 7 (1992), pp. 5175,
and was scanned at The Hong Kong University of Science and Technology.
Other papers in parallel computing
Overview of work on parallel computing

Copyright © 20052016
Quentin F. Stout 