Constructing the Voronoi diagram of a set of line segments in parallel

Michael T. Goodrich; Colm Ó’Dúnlaing; Chee K. Yap

doi:10.1007/3-540-51542-9_3

Constructing the Voronoi diagram of a set of line segments in parallel

Michael T. Goodrich, Colm Ó’Dúnlaing, Chee K. Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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(log²n) time using O(n) processors in the CREW PRAM model.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - Workshop, WADS 1989, Proceedings
Editors	Frank Dehne, Jorg-Rudige Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	12-23
Number of pages	12
ISBN (Print)	9783540515425
DOIs	https://doi.org/10.1007/3-540-51542-9_3
State	Published - 1989
Event	Workshop on Algorithms and Data Structures, WADS 1989 - Ottawa, Canada Duration: Aug 17 1989 → Aug 19 1989

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	382 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Workshop on Algorithms and Data Structures, WADS 1989
Country	Canada
City	Ottawa
Period	8/17/89 → 8/19/89

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-51542-9_3

Fingerprint Dive into the research topics of 'Constructing the Voronoi diagram of a set of line segments in parallel'. Together they form a unique fingerprint.

Cite this

Goodrich, M. T., Ó’Dúnlaing, C., & Yap, C. K. (1989). Constructing the Voronoi diagram of a set of line segments in parallel. In F. Dehne, J-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - Workshop, WADS 1989, Proceedings (pp. 12-23). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 382 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-51542-9_3

Constructing the Voronoi diagram of a set of line segments in parallel. / Goodrich, Michael T.; Ó’Dúnlaing, Colm; Yap, Chee K.

Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. ed. / Frank Dehne; Jorg-Rudige Sack; Nicola Santoro. Springer Verlag, 1989. p. 12-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 382 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Goodrich, MT, Ó’Dúnlaing, C & Yap, CK 1989, Constructing the Voronoi diagram of a set of line segments in parallel. in F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 382 LNCS, Springer Verlag, pp. 12-23, Workshop on Algorithms and Data Structures, WADS 1989, Ottawa, Canada, 8/17/89. https://doi.org/10.1007/3-540-51542-9_3

Goodrich MT, Ó’Dúnlaing C, Yap CK. Constructing the Voronoi diagram of a set of line segments in parallel. In Dehne F, Sack J-R, Santoro N, editors, Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. Springer Verlag. 1989. p. 12-23. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-51542-9_3

Goodrich, Michael T. ; Ó’Dúnlaing, Colm ; Yap, Chee K. / Constructing the Voronoi diagram of a set of line segments in parallel. Algorithms and Data Structures - Workshop, WADS 1989, Proceedings. editor / Frank Dehne ; Jorg-Rudige Sack ; Nicola Santoro. Springer Verlag, 1989. pp. 12-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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.}",

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",

note = "Workshop on Algorithms and Data Structures, WADS 1989 ; Conference date: 17-08-1989 Through 19-08-1989",

}

TY - GEN

T1 - Constructing the Voronoi diagram of a set of line segments in parallel

AU - Goodrich, Michael T.

AU - Ó’Dúnlaing, Colm

AU - Yap, Chee K.

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84983639860&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983639860&partnerID=8YFLogxK

U2 - 10.1007/3-540-51542-9_3

DO - 10.1007/3-540-51542-9_3

M3 - Conference contribution

AN - SCOPUS:84983639860

SN - 9783540515425

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 12

EP - 23

BT - Algorithms and Data Structures - Workshop, WADS 1989, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudige

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - Workshop on Algorithms and Data Structures, WADS 1989

Y2 - 17 August 1989 through 19 August 1989

ER -