DocumentCode
1555694
Title
Efficient parallel convex hull algorithms
Author
Miller, Russ ; Stout, Quentin F.
Author_Institution
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
Volume
37
Issue
12
fYear
1988
fDate
12/1/1988 12:00:00 AM
Firstpage
1605
Lastpage
1618
Abstract
Parallel algorithms are presented to identify (i.e. detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, exclusive-read-exclusive-write parallel random-access machine (EREW PRAM), and modified AKS network. It is shown that the problem of identifying the convex hull for a set of planar points given arbitrarily, cannot be solved faster than sorting
Keywords
computational geometry; parallel algorithms; EREW PRAM; convex hull; convex hull algorithms; hypercube; mesh-of-trees; modified AKS network; parallel algorithms; planar points; pyramid; Computational geometry; Computational modeling; Concurrent computing; Data structures; Helium; Hypercubes; Parallel algorithms; Phase change random access memory; Solid modeling; Sorting;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.9737
Filename
9737
Link To Document