Nordic Journal of Computing Bibliography

A. Datta, A. Maheshwari, and J.-R. Sack. Optimal Parallel Algorithms for Direct Dominance Problems. Nordic Journal of Computing, 3(1):72-88, Spring 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.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Additional Key Words and Phrases: dominance problems, parallel algorithms, computational geometry, direct dominance

Selected papers that cite this one

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database