What can be parallelized in computational geometry?

Chee Keng Yap

doi:10.1007/3-540-18099-0_45

What can be parallelized in computational geometry?

Chee Keng Yap

Computer Science

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

Abstract

This paper has two goals. First, we point out that most problems in computational geometry in fact have fast parallel algorithms (that is, in NC*) by reduction to the cell decomposition result of Kozen and Yap. We illustrate this using a new notion of generalized Voronoi diagrams that subsumes all known instances. While the existence of NC* algorithms for computational geometry is theoretically significant, it leaves much to be desired for specific problems. Therefore, the second part of the paper surveys some recent results in a fast growing list of parallel algorithms for computational geometry.

Original language	English (US)
Title of host publication	Parallel Algorithms and Architectures - International Workshop, Proceedings
Editors	Kurt Mehlhorn, Andreas Albrecht, Hermann Jung
Publisher	Springer Verlag
Pages	184-195
Number of pages	12
ISBN (Print)	9783540180999
DOIs	https://doi.org/10.1007/3-540-18099-0_45
State	Published - 1987
Event	International Workshop on Parallel Algorithms and Architectures, 1987 - Suhl, Germany Duration: May 25 1987 → May 30 1987

Publication series

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

Other

Other	International Workshop on Parallel Algorithms and Architectures, 1987
Country/Territory	Germany
City	Suhl
Period	5/25/87 → 5/30/87

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-18099-0_45

Cite this

Yap, C. K. (1987). What can be parallelized in computational geometry? In K. Mehlhorn, A. Albrecht, & H. Jung (Eds.), Parallel Algorithms and Architectures - International Workshop, Proceedings (pp. 184-195). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 269 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-18099-0_45

What can be parallelized in computational geometry? / Yap, Chee Keng.
Parallel Algorithms and Architectures - International Workshop, Proceedings. ed. / Kurt Mehlhorn; Andreas Albrecht; Hermann Jung. Springer Verlag, 1987. p. 184-195 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 269 LNCS).

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

Yap, CK 1987, What can be parallelized in computational geometry? in K Mehlhorn, A Albrecht & H Jung (eds), Parallel Algorithms and Architectures - International Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 269 LNCS, Springer Verlag, pp. 184-195, International Workshop on Parallel Algorithms and Architectures, 1987, Suhl, Germany, 5/25/87. https://doi.org/10.1007/3-540-18099-0_45

Yap CK. What can be parallelized in computational geometry? In Mehlhorn K, Albrecht A, Jung H, editors, Parallel Algorithms and Architectures - International Workshop, Proceedings. Springer Verlag. 1987. p. 184-195. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-18099-0_45

Yap, Chee Keng. / What can be parallelized in computational geometry?. Parallel Algorithms and Architectures - International Workshop, Proceedings. editor / Kurt Mehlhorn ; Andreas Albrecht ; Hermann Jung. Springer Verlag, 1987. pp. 184-195 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dcff26fa3be346589c9fe0c34dbf76d2,

title = "What can be parallelized in computational geometry?",

abstract = "This paper has two goals. First, we point out that most problems in computational geometry in fact have fast parallel algorithms (that is, in NC*) by reduction to the cell decomposition result of Kozen and Yap. We illustrate this using a new notion of generalized Voronoi diagrams that subsumes all known instances. While the existence of NC* algorithms for computational geometry is theoretically significant, it leaves much to be desired for specific problems. Therefore, the second part of the paper surveys some recent results in a fast growing list of parallel algorithms for computational geometry.",

author = "Yap, {Chee Keng}",

note = "Publisher Copyright: {\textcopyright} 1987, Akademie-Verlag.; International Workshop on Parallel Algorithms and Architectures, 1987 ; Conference date: 25-05-1987 Through 30-05-1987",

year = "1987",

doi = "10.1007/3-540-18099-0_45",

language = "English (US)",

isbn = "9783540180999",

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

publisher = "Springer Verlag",

pages = "184--195",

editor = "Kurt Mehlhorn and Andreas Albrecht and Hermann Jung",

booktitle = "Parallel Algorithms and Architectures - International Workshop, Proceedings",