Parallel voronoi diagram in L1 (L) metric on a mesh-connected computer

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In this paper, we consider the problem of constructing a Voronoi diagram in L1(L) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An O(√n) parallel algorithm on a √n × √n mesh-connected computer is given for solving that problem. This is the first solution on a √n × √n MCC to achieve an asymptotically optimal θ(√n) running time for L1(L) metric.

Original languageEnglish
Pages (from-to)241-252
Number of pages12
JournalParallel Computing
Issue number2-3
Publication statusPublished - 1991 Jun
Externally publishedYes

Bibliographical note

Funding Information:
* Research supported in part by KOSEF grant.


  • 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 'Parallel voronoi diagram in L1 (L) metric on a mesh-connected computer'. Together they form a unique fingerprint.

Cite this