Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems

ABSTRACT

In this paper, we present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n non-intersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(logn) time with very high probability and uses O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of P.T bounds since the sequential time bound for this problem is &OHgr;(nlogn). Our algorithm improves by an O(logn) factor the previously best known deterministic parallel algorithm which runs in O(log2n) time using O(n) processors. We obtain this result by using random sampling at “two stages” of our algorithm and using efficient randomized search techniques. This technique gives a direct optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use reduction from the 3-d convex hull construction).

REFERENCES

• 1: A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dfinlaing, and C. K. Yap. Parallel Computational Geometry. Algorithmica, 3:293-327, 1988.
• 2: Nancy M. Amato , Franco P. Preparata, An NC parallel 3D convex hull algorithm, Proceedings of the ninth annual symposium on Computational geometry, p.289-297, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161152]
• 3: M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
• 4: M. J. Atallah and M. T. Goodrich. Efficient Parallel Solutions to Geometric Problems. In Proc. 1985 IEEE Conf. on Parallel Processing, pages 411-417, 1985.
• 5: Anita Liu Chow, Parallel algorithms for geometric problems, 1980
• 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: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 8: R. Cole and M. T. Goodrich. Optimal Parallel Algorithms for Polygon and Point*set Problems. Algorithmica, 7:3-23, 1992.
• 9: 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]
• 10: S Fortune, A sweepline algorithm for Voronoi diagrams, Proceedings of the second annual symposium on Computational geometry, p.313-322, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10549]
• 11: Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
• 12: Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
• 13: Michael T. Goodrich , Colm Ó'Dúnlaing , Chee-Keng Yap, Constructing the Voronoi Diagram of a Set of Line Segments in Parallel (Preliminary Version), Proceedings of the Workshop on Algorithms and Data Structures, p.12-23, August 17-19, 1989
• 14: D. Itaussler and E. Welzl. e-nets and Simplex Range Queries. Discrete and Computational Geometry, 2:127- 152, 1987.
• 15: D. G. Kirkpatrick. Efficient Computation of Continuous Skeletons. In Proc. 20th iEEE Syrup. on Foundations of Computer Science, pages 18-27, 1979.
• 16: D. G. Kirkpatrick. Optimal Search in Planar Subdivisions. SIAM J. Comput., 12(1):28-35, 1983.
• 17: D. T. Lee and R. L. Drysdale. Generalization of Voronoi Diagrams in the Plane. SIAM J. Comput., 10(1):73-87, February 1981.
• 18: K. Mulmuley. A Fast Planar Partition Algorithm. In Proc. 20th iEEE Syrup. on the Foundations of Computer Science, pages 580-589, 1988.
• 19: C. O'Dfinlaing and C. K. Yap. A 'Retraction' Method for Planning the Motion of a Disc. J. Algorithms, 6:104-111, 1985.
• 20: J. H. Reif and S. Sen. Polling: A New Randomized Sampling Technique for Computational Geometry. Manuscript.
• 21: John H. Reif , Sandeep Sen, Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.21 n.3, p.466-485, June 1992 [doi>10.1137/0221031]
• 22: J.H. Reif and S. Sen. Optimal Randomized Parallel Algorithms for Computational Geometry. Algorithmica, 7:91- 117, 1992.
• 23: C. K. Yap. An O(n log n) Algorithm for the Voronoi Diagram of a Set of Simple Curve Segments. Discrete and Computational Geometry, 2:365-393, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory