Parallel geometric algorithms on a mesh-connected computer

C. S. Jeong, D. T. Lee

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) in O(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. The O(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.

Original languageEnglish
Pages (from-to)155-177
Number of pages23
Issue number1
Publication statusPublished - 1990 Mar
Externally publishedYes


  • Computational geometry
  • Mesh-connected computer
  • Multipoint location
  • Parallel algorithms
  • Voronoi diagrams

ASJC Scopus subject areas

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


Dive into the research topics of 'Parallel geometric algorithms on a mesh-connected computer'. Together they form a unique fingerprint.

Cite this