An improved parallel algorithm for constructing voronoi diagram on a mesh-connected computer

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


While constructing a Voronoi diagram VP for a set P of n points on a mesh-connected computer (MCC), it is necessary to find a set B of edges which are intersected by the dividing chain C during the merge process of two Voronoi diagrams VL and VR, where L and R contain the leftmost [n/2] points and the rightmost [n/2] points of P respectively. The computation of B requires two operations: First decide for each edge e in VL and VR whether its end vertices are closer to L or R, and then from that information, determine whether e is intersected by C. However, in the previous parallel algorithm each of the former and latter operations requires planar point location which takes O(√n) time on a √n × √n MCC, and in addition the former operation needs to compute convex hulls of L and R. In this paper, we shall show that the latter operation can be done in O(1) time without executing planar point location and the former operation can be executed without the computation of convex hulls. Therefore, the computation of B is reduced to only one planar point location.

Original languageEnglish
Pages (from-to)505-514
Number of pages10
JournalParallel Computing
Issue number4-5
Publication statusPublished - 1991 Jul
Externally publishedYes


  • Parallel algorithm
  • Voronoi diagram
  • mesh-connected computer

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'An improved parallel algorithm for constructing voronoi diagram on a mesh-connected computer'. Together they form a unique fingerprint.

Cite this