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 -