A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon

Piotr Berman; Andrzej Lingas

doi:10.1007/3-540-58218-5_7

A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon

Piotr Berman, Andrzej Lingas

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

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.

Original language	English (US)
Title of host publication	Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Erik M. Schmidt, Sven Skyum
Publisher	Springer Verlag
Pages	73-82
Number of pages	10
ISBN (Print)	9783540582182
DOIs	https://doi.org/10.1007/3-540-58218-5_7
State	Published - 1994
Event	4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 - Aarhus, Denmark Duration: Jul 6 1994 → Jul 8 1994

Publication series

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

Other

Other	4th Scandinavian Workshop on Algorithm Theory, SWAT 1994
Country/Territory	Denmark
City	Aarhus
Period	7/6/94 → 7/8/94

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-58218-5_7

Cite this

Berman, P., & Lingas, A. (1994). A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon. In E. M. Schmidt, & S. Skyum (Eds.), Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 73-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 824 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58218-5_7

Berman, Piotr ; Lingas, Andrzej. / A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon. Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Erik M. Schmidt ; Sven Skyum. Springer Verlag, 1994. pp. 73-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

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

}

Berman, P & Lingas, A 1994, A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon. in EM Schmidt & S Skyum (eds), Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 824 LNCS, Springer Verlag, pp. 73-82, 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994, Aarhus, Denmark, 7/6/94. https://doi.org/10.1007/3-540-58218-5_7

A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon. / Berman, Piotr; Lingas, Andrzej.
Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Erik M. Schmidt; Sven Skyum. Springer Verlag, 1994. p. 73-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 824 LNCS).

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

TY - GEN

T1 - A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon

AU - Berman, Piotr

AU - Lingas, Andrzej

PY - 1994

Y1 - 1994

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

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

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

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

U2 - 10.1007/3-540-58218-5_7

DO - 10.1007/3-540-58218-5_7

M3 - Conference contribution

AN - SCOPUS:85028698572

SN - 9783540582182

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

SP - 73

EP - 82

BT - Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Schmidt, Erik M.

A2 - Skyum, Sven

PB - Springer Verlag

T2 - 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994

Y2 - 6 July 1994 through 8 July 1994

ER -

Berman P, Lingas A. A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon. In Schmidt EM, Skyum S, editors, Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Verlag. 1994. p. 73-82. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58218-5_7

A nearly optimal parallel algorithm for the voronoi diagram of a convex polygon

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this