2002 · 43 citations · 6 references
ComputingComputer ScienceComputer SystemsAlgorithmsParallel AlgorithmsParallel ComputingConvex HullsData ParallelismDistributed ComputingParallel Computational GeometryParallel Geometric AlgorithmsVoronoi DiagramsComputational Geometry FoundationsConvex Hull ComplexityParallel Convex Hull
We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly distributed random input data. Our methods apply to multicomputers with arbitrary interconnection network or bus system. The following problems are studied in this paper: (1) lower envelope of line segments, (2) visibility of parallelepipeds, (3) convex hull, (4) maximal elements, (5) Voronoi diagram, (6) all-nearest neighbors, (7) largest empty circle, and (8) largest empty hyperrectangle. Problems 2-8 are studied for d-dimensional space, d=O(1). We implemented and tested the lower envelope algorithm and convex hull algorithm (for d=3 and d=4) on a CM5. The results indicate that our methods are of considerable practical relevance.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
6
On the Average Number of Maxima in a Set of Vectors and Applications
Jon Bentley, H. T. Kung, Mario Schkolnick et al. · Journal of the ACM · 1978 · 372 citations · Full text