@inproceedings{ef48137f3dd7452ab397f9299e411e6b,

title = "Constructing the Voronoi diagram of a set of line segments in parallel",

abstract = "In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log2n) time using O(n) processors in the CREW PRAM model.",

author = "Goodrich, {Michael T.} and Colm {\'O}{\textquoteright}D{\'u}nlaing and Yap, {Chee K.}",

note = "Funding Information: We are interested in solving this problem in parallel. This is motivated by the fact that one cannot speed-up its construction by anything more than a constant factor over the previous methods without using more than a single processor, due to known lower bounds (Shamos [25]). Specifically, the goal of this research is to find an algorithm that runs as fast as possible and is efficient in the following sense: if P(n) is its processor complexity, T(n) is its time complexity, and Seq(n) is the time complexity of the best *Research supported by NSF Grant CCR-8810568. tResearch supported in part by NSF grants DCR-84-01898, DCR-84-01633, and CCR-8703458. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1989.; Workshop on Algorithms and Data Structures, WADS 1989 ; Conference date: 17-08-1989 Through 19-08-1989",

year = "1989",

doi = "10.1007/3-540-51542-9_3",

language = "English (US)",

isbn = "9783540515425",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "12--23",

editor = "Frank Dehne and Jorg-Rudige Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - Workshop, WADS 1989, Proceedings",

}