AbstractWe investigate a new paradigm of algorithm design for geometric problems that can be termed distribution-sensitive. Our notion of distribution is more combinatorial in nature than spatial. We illustrate this on problems like planar-hulls and 2D-maxima where some of the previously known output-sensitive algorithms are recast in this setting. In a number of cases, the distribution-sensitive analysis yields superior results for the above problems. Moreover these bounds are shown to be tight in the linear decision tree model. Our approach owes its spirit to the results known for sorting multisets and we exploit this relationship further to derive fast and efficient parallel algorithms for sorting multisets along with the geometric problems.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; F.1.3 [Computation by Abstract Devices]: Complexity Classes
Additional Key Words and Phrases: convex hulls, sorting, computational geometry, parallel algorithms
Selected references
- Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 80-86, Boston, Massachusetts, 25-27 April 1983.
- Binay K. Bhattacharya and Sandeep Sen. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms, 25(1):177-193, October 1997.
- Timothy M. Y. Chan, Jack Snoeyink, and Chee-Keng Yap. Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 282-291, San Francisco, California, 22-24 January 1995.
- M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing, 13(1):31-45, February 1984.
- Martin Farach and S. Muthukrishnan. Optimal parallel randomized renaming. Information Processing Letters, 61(1):7-10, 14 January 1997.
- R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4):132-133, June 1972.
- Torben Hagerup. Fast deterministic processor allocation. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-10, Austin, Texas, 25-27 January 1993.
- Torben Hagerup and Rajeev Raman. Waste makes haste: Tight bounds for loose parallel sorting. In 33rd Annual Symposium on Foundations of Computer Science, pages 628-637, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Sanjiv Kapoor and Prakash V. Ramanan. Lower bounds for maximal and convex layers problems. Algorithmica, 4:447-459, 1989.
- David G. Kirkpatrick and Raimund Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287-299, February 1986.
- H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectors. Journal of the ACM, 22(4):469-476, October 1975.
- Philip D. MacKenzie. Load balancing requires Omega(log* n) expected time. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 94-99, Orlando, Florida, 27-29 January 1992.
- Nimrod Megiddo. Linear-time algorithms for linear programming in R^3 and related problems. SIAM Journal on Computing, 12(4):759-776, November 1983.
- Ian Munro and Philip M. Spira. Sorting and searching in multisets. SIAM Journal on Computing, 5(1):1-8, March 1976.
- J. Michael Steele and Andrew C. Yao. Lower bounds for algebraic decision trees. Journal of Algorithms, 3(1):1-8, March 1982.
- Lutz M. Wegner. Sorting a linked list with equal keys. Information Processing Letters, 15(5):205-208, 10 December 1982.
- R. Wenger. Randomized quickhull. Algorithmica, 17(3):322-329, March 1997.
- Andrew Chi-Chih Yao. A lower bound to finding convex hulls. Journal of the ACM, 28(4):780-787, October 1981.