What can be parallelized in computational geometry?

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationParallel Algorithms and Architectures - International Workshop, Proceedings
EditorsKurt Mehlhorn, Andreas Albrecht, Hermann Jung
PublisherSpringer Verlag
Pages184-195
Number of pages12
ISBN (Print)9783540180999
DOIs
StatePublished - 1987
EventInternational Workshop on Parallel Algorithms and Architectures, 1987 - Suhl, Germany
Duration: May 25 1987May 30 1987

Publication series

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

Other

OtherInternational Workshop on Parallel Algorithms and Architectures, 1987
CountryGermany
CitySuhl
Period5/25/875/30/87

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'What can be parallelized in computational geometry?'. Together they form a unique fingerprint.

  • 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