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

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

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)128-141
Number of pages14
JournalAlgorithmica
Volume9
Issue number2
DOIs
StatePublished - Feb 1993

Keywords

  • PRAM
  • Parallel algorithm
  • Voronoi diagram

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

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