Carleton University
Technical Report TR-229
October 1993
Optimal Parallel Algorithms for Direct Dominance Problems
Abstract
We present optimal parallel solutions to direct dominance problems for planar point sets and provide an application. The algorithms presented here are deterministic and designed to run on the concurrent read exclusive write parallel random-access machine (CREW PRAM). In particular, we provide algorithms for counting the number of points that are directly dominated by each point of an n-point set and for reporting these point sets. The counting algorithm runs in 0(log n) time using 0( n) processors; the reporting algorithm runs in 0(log n) time using 0( n + k / log n) processors, where k is the size of the output. The algorithms are therefore optimal. As an application of our results, we present an algorithm for the maximum empty rectangle problem, which is work optimal in the expected case.