ABSTRACT
We introduce a new randomized sampling technique, called Polling which has applications to deriving efficient parallel algorithms. As an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree. Our algorithms run in time T = O(logn) for worst-case inputs and uses P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only O(log2 n) random bits and terminate in the claimed time bound with probability 1 - n-α for any α > 0. They are also optimal in P . T product since the sequential time bound for all these problems is Ω(nlogn). The best known determistic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log2 n) and O(log2 nlog * n) time respectively while using O(n) processors.
- 1.A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap. Parallel computational geometry. Proc. of 25th Annual Symposium on Foundations o/Computer Science, pages 468- 477, 1985. also appears in full version in Algorithmica, Vol. 3, No. 3, 1988, pp. 293-327.Google ScholarDigital Library
- 2.M.J. AtaIlah, R. Cole, and M.T. Goodrich. Cascading divide-and-conquer: A technique for designing parallel algorithms. Proc. of the 28th Annual Symposium on the Foundations of Computer Science, pages 151- 160, 1987.Google ScholarDigital Library
- 3.K.Q. Brown. Voronoi diagram from convex hulls. Informal. Process Lett., 9:223- 228.Google ScholarCross Ref
- 4.Anita Chow. Parallel Algorithms for Geometric Problems. PhD thesis, University of Illinois at Urbana-Champaign, 1980. Google ScholarDigital Library
- 5.K.L. Clarkson. A probabilistic algorithm for the post-office problem. Proc of the 17th Annual $IGACT Symposium, pages 174- 184, 1985. Google ScholarDigital Library
- 6.K.L. Clarkson. New applications of random sampling in computational geometry. Discrete and Computational Geometry, pages 195- 222, 1987.Google Scholar
- 7.K.L. Clarkson. Applications of random sampling in computational geometry it. Proc of the 4th Annual A CM Syrup on Computational Geometry, pages 1 - 11, 1988. Google ScholarDigital Library
- 8.K.L. Clarkson and P. Shor. Algorithms for diametral pairs and convex hulls that are optimal, randomized and incremental. Proc. of the jth A CM Syrup. on Computational Geometry, 1988. Google ScholarDigital Library
- 9.R. Cole. Parallel merge sort. Proc. of the 2?th Annual IEEE Syrup. on Foundations of Computer Science, pages 511- 516, 1986.Google ScholarDigital Library
- 10.R. Cole and M.T. Goodrich. Optimal parallel algorithms for polygon and point-set problems. Proc. of the dth A CM Syrup. on Computational Geometry, pages 201- 210, 1988. Google ScholarDigital Library
- 11.N. Dadoun and D.G. Kirkpatrick. Parallel processing for efficient subdivision search. Proc. of the 3rd Annual ACM Syrup on Comput. Geom, pages 205 - 214, 1987. Google ScholarDigital Library
- 12.D. Dobkin and D. Kirkpatrick. A linear time algorithm for determining the separation of covex polyhedra. Journal of Algorithms, 6(3):381- 392, 1985.Google ScholarCross Ref
- 13.D. Dobkin and R.J. Lipton. Multidimensional searching problems. SIAM J. on Computing, 5:181 - 186, 1976.Google Scholar
- 14.H. Edelsbrunner. Algorithms in combinatorial geometry. EATCS Monographs on Theoetical Computer Science. Springer Verlag, 1987. Google ScholarDigital Library
- 15.S. Fortune. A sweepline algorthm for voronoi diagrams. Proc of the ~nd A CM Syrup. on Comput., pages 511 - 516, 1986.Google Scholar
- 16.H. Gazit. An optimal r~ndomized parallel algorithm for finding connected components in a graph. Proc. of the 27th Annual IEEE Syrup. on Foundations of Computer Science, pages 492 - 501, 1986.Google ScholarDigital Library
- 17.D. ttaussler and E. Welzl. e-nets and simplex range queries. Discrete and Computational Geometry, 2(2):127- 152, lOS7.Google Scholar
- 18.H. Karloff and P. Raghavan. Randomized algorithms and pseudorandom numbers. Proc. of the 20th Annual STOC, 1988. Google ScholarDigital Library
- 19.D.G. Kirkpatrick. private communication.Google Scholar
- 20.C. Levcopoulos, J. Katajainen, and A. Lingas. An optima/ expected-time parallel algorithm for voronoi diagrams. Scandenavian conference on theoretical computer science, 1988.Google Scholar
- 21.K. Mulmuley. A fast planar partition algorithm 1. Proc. of the 29th IEEE FOCS, pages 580- 589, 1988.Google ScholarDigital Library
- 22.S. Rajasekaran and j. Reif. Optimal and sublogarithmic time radomized parallel sorting algorithms. Technical Rept, Aiken Compuiing lab, Harvard University, 1986. To appear in SIAM Journal on Computing. Google ScholarDigital Library
- 23.J.H. Reif and S. Sen. Optimal randomized parallel algorithms for computational geometry. Proc. of the 16th ~nternational conference on Parallel Processing, 1987. A revised version is available as Duke University technical report CS-88-01. Google ScholarDigital Library
- 24.J.H. Reif and L.G. Valiant. A logarithmic time sort for linear size networks. Journal of the A CM, 34:60 - 76, 1987. Google ScholarDigital Library
- 25.R. Reischuk. A fast probabilistic parallel sorting algorithm. Proc. of the 2~nd IEEE FOC~, pages 212- 219, 1981.Google ScholarDigital Library
- 26.M. Shamos and D. Hoey. Closest-point problems. Proc. of the 7th A CM STOC, pages 224- 233. Google ScholarDigital Library
- 27.L.G. Valiant. A scheme for fast parallel communication. SIAM J. on Computing, 11'350- 361, 1982.Google Scholar
Index Terms
- Polling: a new randomized sampling technique for computational geometry
Recommendations
New applications of random sampling in computational geometry
This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from ...
Applications of random sampling in computational geometry, II
We use random sampling for several new geometric algorithms. The algorithms are "Las Vegas," and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for ...
Comments