An optimal parallel algorithm for building a data structure for planar point location

Richard Cole, Ofer Zajlcek

Research output: Contribution to journalArticlepeer-review

Abstract

Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors.

Original languageEnglish (US)
Pages (from-to)280-285
Number of pages6
JournalJournal of Parallel and Distributed Computing
Volume8
Issue number3
DOIs
StatePublished - Mar 1990

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An optimal parallel algorithm for building a data structure for planar point location'. Together they form a unique fingerprint.

Cite this