AbstractWe 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
- Maria Andreou and Stavros D. Nikolopoulos. NC Coloring Algorithms for Permutation Graphs. Nordic Journal of Computing, 6(4):422-445, Winter 1999.
- Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, and Jorge Urrutia. Planar stage graphs: Characterizations and applications. Theoretical Computer Science, 175(2):239-255, 10 April 1997.
Selected references
- Mikhail J. Atallah, Richard Cole, and Michael T. Goodrich. Cascading divide-and-conquer: A technique for designing parallel algorithms. SIAM Journal on Computing, 18(3):499-532, June 1989.
- Mikhail J. Atallah and S. Rao Kosaraju. An efficient algorithm for maxdominance, with applications. Algorithmica, 4:221-236, 1989.
- B. Chazelle, R. L. Drysdale, and D. T. Lee. Computing the largest empty rectangle. SIAM Journal on Computing, 15(1):300-315, February 1986.
- Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, August 1988.
- Richard Cole and Uzi Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329-346, 1988.
- Richard Cole and Uzi Vishkin. Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM Journal on Computing, 17(1):128-142, February 1988.
- Michael T. Goodrich. Intersecting line segments in parallel with an output-sensitive number of processors. SIAM Journal on Computing, 20(4):737-755, August 1991.
- M. Orlowski. A new algorithm for the largest empty rectangle problem. Algorithmica, 5:65-73, 1990.
- Mark H. Overmars and Derick Wood. On rectangular visibility. Journal of Algorithms, 9(3):372-390, September 1988.
- Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing, 17(6):1253-1262, December 1988.
- Robert E. Tarjan and Uzi Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, November 1985.