Polling: a new randomized sampling technique for computational geometry

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-&agr; for any &agr; > 0. They are also optimal in P . T product since the sequential time bound for all these problems is &OHgr;(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.

REFERENCES

• 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.
• 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.
• 3: K.Q. Brown. Voronoi diagram from convex hulls. Informal. Process Lett., 9:223- 228.
• 4: Anita Liu Chow, Parallel algorithms for geometric problems, 1980
• 5: K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22165]
• 6: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 7: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• 8: K. L. Clarkson , P. W. Shor, Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, Proceedings of the fourth annual symposium on Computational geometry, p.12-17, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73395]
• 9: R. Cole. Parallel merge sort. Proc. of the 2?th Annual IEEE Syrup. on Foundations of Computer Science, pages 511- 516, 1986.
• 10: R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73414]
• 11: N. Dadoun , D. G. Kirkpatrick, Parallel processing for efficient subdivision search, Proceedings of the third annual symposium on Computational geometry, p.205-214, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41980]
• 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.
• 13: D. Dobkin and R.J. Lipton. Multidimensional searching problems. SIAM J. on Computing, 5:181 - 186, 1976.
• 14: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 15: S. Fortune. A sweepline algorthm for voronoi diagrams. Proc of the ~nd A CM Syrup. on Comput., pages 511 - 516, 1986.
• 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.
• 17: D. ttaussler and E. Welzl. e-nets and simplex range queries. Discrete and Computational Geometry, 2(2):127- 152, lOS7.
• 18: Howard Karloff , Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.310-321, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62242]
• 19: D.G. Kirkpatrick. private communication.
• 20: C. Levcopoulos, J. Katajainen, and A. Lingas. An optima/ expected-time parallel algorithm for voronoi diagrams. Scandenavian conference on theoretical computer science, 1988.
• 21: K. Mulmuley. A fast planar partition algorithm 1. Proc. of the 29th IEEE FOCS, pages 580- 589, 1988.
• 22: S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
• 23: H J Reif , Sandeep Sen, Optimal Randomized Parallel Algorithms for Computational Geometry I, Duke University, Durham, NC, 1988
• 24: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
• 25: R. Reischuk. A fast probabilistic parallel sorting algorithm. Proc. of the 2~nd IEEE FOC~, pages 212- 219, 1981.
• 26: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 27: L.G. Valiant. A scheme for fast parallel communication. SIAM J. on Computing, 11'350- 361, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing

General Terms:
Algorithms, Theory