Paper Info
Title
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).
Year
DOI
Venue
1994
10.1145/177424.177511
Symposium on Computational Geometry 2013
Keywords
Field
DocType
optimal parallel algorithm,deterministic parallel algorithm,problem use reduction,3-d convex hull construction,direct optimal algorithm,line segment,related problem,optimal parallel randomized algorithm,crcw pram,sequential time,voronoi diagram,efficient randomized search technique,spanning tree,np hard,convex hull,randomized algorithm,graph drawing,random search,parallel algorithm,tree,random sampling
Discrete mathematics,Randomized algorithm,Combinatorics,Ramer–Douglas–Peucker algorithm,Parallel algorithm,Rabin–Karp algorithm,Voronoi diagram,Fortune's algorithm,Output-sensitive algorithm,Freivalds' algorithm,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89791-648-4
7
0.55
References 
Authors
22
2
Name
Order
Citations
PageRank
Sanguthevar Rajasekaran11508190.34
Suneeta Ramaswami222823.87