Title | ||
---|---|---|
Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane |
Abstract | ||
---|---|---|
Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem
is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, Ó'Dúnlaing, and Yap, which runs in
O( log
2
n) time using O(n) processors. We obtain this result by using a new ``two-stage'' random sampling technique. By choosing large samples in the
first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up'' that is typical in recursive parallel geometric
algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm.
This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel
algorithms for this problem use the transformation to three-dimensional half-space intersection).
|
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/s00453-001-0115-6 | Algorithmica |
Keywords | Field | DocType |
Key words. Voronoi diagrams,Line segments,Parallel algorithms,Randomized algorithms. | Discrete mathematics,Line segment,Randomized algorithm,Combinatorics,Parallel algorithm,Computational geometry,Voronoi diagram,Fortune's algorithm,Time complexity,Freivalds' algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 1432-0541 |
Citations | PageRank | References |
0 | 0.34 | 30 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sanguthevar Rajasekaran | 1 | 1508 | 190.34 |
Suneeta Ramaswami | 2 | 228 | 23.87 |