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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence