Scalable and architecture independent parallel geometric algorithmswith high probability optimal time

摘要

We present parallel computational geometry algorithms that arenscalable, architecture independent, easy to implement, and have, withnhigh probability, an optimal time complexity for uniformly distributednrandom input data. Our methods apply to multicomputers with arbitraryninterconnection network or bus system. The following problems arenstudied in this paper: (1) lower envelope of line segments, (2)nvisibility of parallelepipeds, (3) convex hull, (4) maximal elements,n(5) Voronoi diagram, (6) all-nearest neighbors, (7) largest emptyncircle, and (8) largest empty hyperrectangle. Problems 2-8 are studiednfor d-dimensional space, d=O(1). We implemented and tested the lowernenvelope algorithm and convex hull algorithm (for d=3 and d=4) on a CM5.nThe results indicate that our methods are of considerable practicalnrelevance