@inproceedings{2c13682251a848558c52c407f59b6191,

title = "A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon",

abstract = "We present a parMlel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(log n) and uses O(nloglog n/log n) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time and O(n log log n log n)-proceor CRCW PRAM algorithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling problem due to Cole and Vishkin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in the sense that for any given I > 0 they terminate in time O(log n) with probability greater than 1-n -1.",

author = "Piotr Berman and Andrzej Lingas",

note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 ; Conference date: 06-07-1994 Through 08-07-1994",

year = "1994",

doi = "10.1007/3-540-58218-5_7",

language = "English (US)",

isbn = "9783540582182",

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

publisher = "Springer Verlag",

pages = "73--82",

editor = "Schmidt, {Erik M.} and Sven Skyum",

booktitle = "Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "Germany",

}