O(log log n)-time integer geometry on the CRCW PRAM

B. S. Chlebus, K. Diks, M. Kowaluk

Research output: Contribution to journalArticlepeer-review


We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points with O(log n)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time O(log log n). The following five specific problems are investigated:closest pair of points, intersection of convex polygons, intersection of manhattan line segments, dominating set, and largest empty square. Algorithms solving them are developed which operate in time O(log log n) on the arbitrary CRCW PRAM. The number of processors used is either O(n) or O(n log n).

Original languageEnglish (US)
Pages (from-to)52-69
Number of pages18
Issue number1
StatePublished - Jul 1 1995
Externally publishedYes


  • Computational geometry
  • Highly parallelizable problems
  • PRAM

ASJC Scopus subject areas

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


Dive into the research topics of 'O(log log n)-time integer geometry on the CRCW PRAM'. Together they form a unique fingerprint.

Cite this