Sanguthevar Rajasekaran
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 Ω(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).
- 1.A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dfinlaing, and C. K. Yap. Parallel Computational Geometry. Algorithmica, 3:293-327, 1988.Google Scholar
Digital Library
- 2.N. M. Amato and F. P. Preparata. An NC1 Parallel 3D Convex Hull Algorithm. In Proc. 9th A CM Syrup. on Computational Geometry, 1993. Google ScholarDigital Library
- 3.M. J. Atallah, R. Cole, and M. T. Goodrich. Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms. SIAM J. Uomput., 18(3):499-532, 1989. Google ScholarDigital Library
- 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.Google Scholar
- 5.A. Chow. Parallel Algorithms for Geometric Problems. P hD thesis, Univ. of Illinois at Urbana-Champaign, 1980. Google ScholarDigital Library
- 6.K. L. Clarkson and P. W. Shor. Applications of Random Sampling in Computational Geometry, Ii. Discrete Comput. Geom., 4:387-421, 1989.Google ScholarDigital Library
- 7.R. Cole. Parallel Merge Sort. SiAM J. Comput., 17(4):770-785, 1988. Google ScholarDigital Library
- 8.R. Cole and M. T. Goodrich. Optimal Parallel Algorithms for Polygon and Point*set Problems. Algorithmica, 7:3-23, 1992.Google ScholarCross Ref
- 9.N. Dadoun and D. Kirkpatrick. Parallel Processing for Efficient Subdivision Search. In Proc. Third A CM Syrup. on Computational Geometry, pages 205-214, 1987. Google ScholarDigital Library
- 10.S. Fortune. A Sweepline Algorithm for Voronoi Diagrams. In Proc. 2nd A CM Syrup. on Computational Geometry, pages 313-322, 1986. Google ScholarDigital Library
- 11.J. Gil, Y. Matias, and U. Vishkin. Towards a Theory of Nearly Constant Time Parallel Algorithms. in Proc. of Syrup. on FOCS, 1992. Google ScholarDigital Library
- 12.M. T. Goodrich. Geometric Partitioning Made Easier, Even in Parallel. In Proc. 9th A CM Syrup. on Computational Geometry, 1993. Google ScholarDigital Library
- 13.M. T. Goodrich, C. O'Dfinlaing, and C. K. Yap. Constructing the Voronoi Diagram of a Set of Line Segments in Parallel. In Lecture Notes in Computer Science: 382, Algorithms and Data Structures, WADS, pages 12-23. Springer-Verlag, 1989. Google ScholarDigital Library
- 14.D. Itaussler and E. Welzl. e-nets and Simplex Range Queries. Discrete and Computational Geometry, 2:127- 152, 1987.Google ScholarDigital Library
- 15.D. G. Kirkpatrick. Efficient Computation of Continuous Skeletons. In Proc. 20th iEEE Syrup. on Foundations of Computer Science, pages 18-27, 1979.Google ScholarDigital Library
- 16.D. G. Kirkpatrick. Optimal Search in Planar Subdivisions. SIAM J. Comput., 12(1):28-35, 1983.Google ScholarCross Ref
- 17.D. T. Lee and R. L. Drysdale. Generalization of Voronoi Diagrams in the Plane. SIAM J. Comput., 10(1):73-87, February 1981.Google ScholarCross Ref
- 18.K. Mulmuley. A Fast Planar Partition Algorithm. In Proc. 20th iEEE Syrup. on the Foundations of Computer Science, pages 580-589, 1988.Google ScholarDigital Library
- 19.C. O'Dfinlaing and C. K. Yap. A 'Retraction' Method for Planning the Motion of a Disc. J. Algorithms, 6:104-111, 1985.Google ScholarCross Ref
- 20.J. H. Reif and S. Sen. Polling: A New Randomized Sampling Technique for Computational Geometry. Manuscript.Google Scholar
- 21.J.H. Reif and S. Sen. Optimal Parallel Randomized Algorithms for Three Dimensional Convex Hulls and Related Problems. SIAM J. Comput., 21(3):466-485, 1992. Google ScholarDigital Library
- 22.J.H. Reif and S. Sen. Optimal Randomized Parallel Algorithms for Computational Geometry. Algorithmica, 7:91- 117, 1992.Google Scholar
- 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.Google ScholarDigital Library
Index Terms
- Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems
Recommendations
Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel
FST TCS '01: Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer ScienceIn this paper we focus on the problem of designing very fast parallel algorithms for constructing the upper envelope of straight-line segments that achieve the O(n log H) work-bound for input size n and output size H. Our algorithms are designed for the ...
A Randomized Algorithm for Voronoi Diagram of Line Segments on Coarse-Grained Multiprocessors
IPPS '96: Proceedings of the 10th International Parallel Processing SymposiumWe present a randomized parallel algorithm for the Voronoi diagram of line segments on coarse grained parallel machines, which, for any input of n line segments on P processors (n= O (P3 +), for any> 0) requires (with high probability) O([n log n/P]) ...
Cost-Optimal Parallel Algorithms for the Tree Bisector and Related Problems
An edge is a bisector of a simple path if it contains the middle point of the path. Let T=(V, E) be a tree. Given a source vertex s \in V, the single-source tree bisector problem is to find, for every vertex v \in V, a bisector of the simple path from s ...
Comments