What can be parallelized in computational geometry?

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Number of pages12
ISBN (Print)9783540180999
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


OtherInternational Workshop on Parallel Algorithms and Architectures, 1987

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this