Multidimensional divide-and-conquer

ABSTRACT

Most results in the field of algorithm design are single algorithms that solve single problems. In this paper we discuss multidimensional divide-and-conquer, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems. We use this paradigm to give best-known solutions to such problems as the ECDF, maxima, range searching, closest pair, and all nearest neighbor problems. The contributions of the paper are on two levels. On the first level are the particular algorithms and data structures given by applying the paradigm. On the second level is the more novel contribution of this paper: a detailed study of an algorithmic paradigm that is specific enough to be described precisely yet general enough to solve a wide variety of problems.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: Jon Louis Bentley, Divide and conquer algorithms for closest point problems in multidimensional space., 1976
• 4: Bentley, J.L. Decomposable searching problems. Inform. Proc. Letters 8, 5 (June 1979), 244-251.
• 5: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 6: J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
• 7: Bentley, J.L., and Maurer, H.A. Efficient worst-case data structures for range searching. To appear in Acta lnformatica (1980).
• 8: Jon Louis Bentley , Michael Ian Shamos, Divide-and-conquer in multidimensional space, Proceedings of the eighth annual ACM symposium on Theory of computing, p.220-230, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803652]
• 9: Bentley, J.L., and Shamos, M.I. A problem in multivariate statistics: Algorithm, data structure, and applications. In Proc. 15th Allerton Conf. Communication, Control, and Comptng., Sept. 1977, pp. 193-201.
• 10: Blum, M., et al. Time bounds for selection. J. Comptr. Syst. Sci. 7, 4 (Aug. 1972), 448--461.
• 11: Dobkin, D., and Lipton, R.J. Multidimensional search problems. SIAM J. Comptng. 5, 2 (June 1976), 181-186.
• 12: Michael L. Fredman, A near optimal data structure for a type of range query problem, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.62-66, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804398]
• 13: Michael L. Fredman , Bruce Weide, On the complexity of computing the measure of ∪[a_i,b_i], Communications of the ACM, v.21 n.7, p.540-544, July 1978 [doi>10.1145/359545.359553]
• 14: Friedman, J.H. A recursive partitioning decision rule for nonparametric classification. 1EEE Trans. Comptrs. C-26, 4 (April 1977), 404--408.
• 15: Friedman, J. H. A nested partitioning algorithm for numerical multiple integration. Rep. SLAC-PUB-2006, Stanford Linear Accelerator Ctr., 1978.
• 16: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 17: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 18: D. T. Lee , C. K. Wong, Quintary trees: a file structure for multidimensional datbase sytems, ACM Transactions on Database Systems (TODS), v.5 n.3, p.339-353, Sept. 1980 [doi>10.1145/320613.320618]
• 19: Lipton, R., and Tarjan, R.E. Applications of a planar separator theorem. In Proc. 18th Symp. Foundations of Comptr. Sci., Oct. 1977, pp. 162-170.
• 20: Lueker, G. A data structure for orthogonal range queries. In Proc. 19th Symp. Foundations of Comptr. Sci., Oct. 1978, pp. 28-34.
• 21: Monier, L. Combinatorial solutions of multidimensional divideand-conquer recurrences. To appear in the J. of Algorithms.
• 22: Murray, J.A. Lieutenant, Police Department--The Complete Study Guide for Scoring High (4th ed.). Arco, New York, 1966, p. 184, question 3.
• 23: Reddy, D.R., and Rubin, S. Representation of three-dimensional objects. Carnegie-Mellon Comptr. Sci. Rep. CMU-CS-78-113, Carnegie-Mellon Univ., Pittsburgh, Pa., 1978.
• 24: Saxe, J.B. On the number of range queries in k-space. Discrete Appl. Math. 1, 3 (Nov. 1979), 217-225.
• 25: Michael Ian Shamos, Computational geometry., 1978
• 26: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 27: Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977 [doi>10.1145/356707.356711]
• 28: Willard, D.E. New data structures for orthogonal queries. Harvard Aiken Comptr. Lab. Rep., Cambridge, Mass., 1978.
• 29: Yao, F.F. On f'mding the maximal elements in a set of planar vectors. Rep. UIUCDCS-R-74-667, Comptr. Sci. Dept., Univ. of Illinois, Urbana, July 1974.

INDEX TERMS

Keywords:
algorithmic paradigms, analysis of algorithms, closest-point problem, computational geometry, data structures, empirical cumulative distribution functions, maxima problems, multidimensional searching problems, range searching