Optimal parallel algorithms for direct dominance problems
Amitava Datta, Anil Maheshwari, Jörg-Rüdiger Sack · Nordic journal of computing · 1996
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 O(log n) time using O(n) processors; the reporting algorithm runs in O(log n) time using O(n + k/ log n) processors, where k is the size of the output. The parallel work of our algorithms matches the time complexity of known optimal sequential algorithms. As an application of our results, we present a parallel algorithm for the maximum empty rectangle problem.