TY - GEN
T1 - Merging free trees in parallel for efficient voronoi diagram construction
AU - Cole, Richard
AU - Goodrich, Michael T.
AU - Dúnlaing, Colm
N1 - Funding Information:
1Computer Science Department, Courant Institute, 251 Mercer Street, New York, NY 10012, U.S.A. Supported by the U.S. National Science Foundation under grants CCR 8902221 and CCR 8906949 ~Department of Computer Science, Johns Hopkins University, Baltimore, Maryland 21218, U.S.A. Supported by the U.S. National Science Foundation under Grant CCR-8810568 and by the NSF and DARPA under Grant CCR-8908092. 3School of Mathematics, Trinity College, Dublin 2, Irish Republic. Supported by the E.C. under Esprit BRA 3075 (ALCOM).
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - This paper describes a new approach for constructing the Voronoi diagram of n points in the plane in parallel. Our approach is based on a divide-and-conquer procedure where we implement the “marry” step by merging forests of free trees (to build the “contour” between the subproblem solutions) in O(log log n) time. This merging procedure is based an a √n -divide-and-merge technique reminiscent of the list-merging approach of Valiant. Our method also involves an optimal parallel method for computing the proximity envelope of a point set with respect to a given line. This structure facilitates the use of our fast mering procedure, for it allows the divide-and-conquer procedure to continue without needing to explicitly remove edges of recursively constructed diagrams that are not part of the final diagram. We use this approach to derive two results regarding the deterministic parallel construction of a Voronoi diagram. Specifically, we show that one can solve the Voronoi diagram problem in O(log n log log n) time and O(n log2n) work (which improves the previous time bound while maintaining the same work bound) or, alternatively, in O(log2n) time and O(n log n) work (which improves the previous work bound while maintaining the same time bound). Our model of computation is the CREW PRAM.
AB - This paper describes a new approach for constructing the Voronoi diagram of n points in the plane in parallel. Our approach is based on a divide-and-conquer procedure where we implement the “marry” step by merging forests of free trees (to build the “contour” between the subproblem solutions) in O(log log n) time. This merging procedure is based an a √n -divide-and-merge technique reminiscent of the list-merging approach of Valiant. Our method also involves an optimal parallel method for computing the proximity envelope of a point set with respect to a given line. This structure facilitates the use of our fast mering procedure, for it allows the divide-and-conquer procedure to continue without needing to explicitly remove edges of recursively constructed diagrams that are not part of the final diagram. We use this approach to derive two results regarding the deterministic parallel construction of a Voronoi diagram. Specifically, we show that one can solve the Voronoi diagram problem in O(log n log log n) time and O(n log2n) work (which improves the previous time bound while maintaining the same work bound) or, alternatively, in O(log2n) time and O(n log n) work (which improves the previous work bound while maintaining the same time bound). Our model of computation is the CREW PRAM.
UR - http://www.scopus.com/inward/record.url?scp=33646465247&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646465247&partnerID=8YFLogxK
U2 - 10.1007/bfb0032049
DO - 10.1007/bfb0032049
M3 - Conference contribution
AN - SCOPUS:33646465247
SN - 9783540528265
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 432
EP - 445
BT - Automata, Languages and Programming - l7th International Colloquium, Proceedings
A2 - Paterson, Michael S.
PB - Springer Verlag
T2 - 17th International Colloquium on Automata, Languages and Programming, 1990
Y2 - 16 July 1990 through 20 July 1990
ER -