An application of m-ary trees to the design of data structures for geometric searching problems
Talamo, M. ; Gambosi, G.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989), p. 165-176 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1989-01-01
@article{ITA_1989__23_2_165_0,
     author = {Talamo, M. and Gambosi, G.},
     title = {An application of $m$-ary trees to the design of data structures for geometric searching problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {23},
     year = {1989},
     pages = {165-176},
     mrnumber = {1001724},
     zbl = {0681.68083},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1989__23_2_165_0}
}

Talamo, M.; Gambosi, G. An application of $m$-ary trees to the design of data structures for geometric searching problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) pp. 165-176. http://gdmltest.u-ga.fr/item/ITA_1989__23_2_165_0/

[1] J. L. Bentley, Multidimensional Divide and Conquer, Communications of A.C.M., vol. 23, 1980, pp. 214-229. | MR 567150 | Zbl 0434.68049

[2] J. L. Bentley, Multidimensional Binary Search Trees Used for Associative Searching, Communications of A.C.M., vol. 18, 1975, pp. 509-517. | Zbl 0306.68061

[3] J. L. Bentley, Multidimensional Binary Search Trees in Database Applications, I.E.E.E. Trans. on Software Engineering, vol. 5, 1979, pp. 333-340. | Zbl 0411.68055

[4] J. L. Bentley, Decomposable Searching Problems, Information Processing Letters, vol. 8, 1979, pp. 244-251. | MR 534072 | Zbl 0404.68067

[5] J. L. Bentley and J. H. Friedman, Data Structures for Range Searching, Computing Surveys, vol. 11, 1979, pp. 397-409.

[6] J. L. Bentley and H. A. Maurer, Efficient Worst-case Data Structures for Range Searching, Acta Informatica, vol. 13, 1980, pp. 155-168. | MR 564462 | Zbl 0423.68029

[7] J. L. Bentley and J. B. Saxe, Decomposable Searching Problems # 1: Static to Dynamic Transformations, Journal of Algorithms, vol. 1, 1980, pp. 301-358. | MR 604869 | Zbl 0461.68065

[8] J. L. Bentley and M. I. Shamos, A Problem in Multivariate Statistics: Algorithm, Data Structure and Applications, Proc. 15th Annual Allerton Conf. on Communication, Control and Computing, 1977, pp. 193-201.

[9] J. L. Bentley and D. Wood, An Optimal Worst-case Algorithm for Reporting Intersection of Rectangles, I.E.E.E. Trans. on Computers, vol. 29, 1980, pp. 571-577. | MR 581619

[10] B. M. Chazelle, Filtering Search: a New Approach to Query Answering, Proc. 24th I.E.E.E. Symp. on Foundations of Computer Science, 1983, pp. 122-132.

[11] B. M. Chazelle and H. Edelsbrunner, Linear Space Data Structures for two Types of Range Search, Tech. Report 202, Inst. of Computer Science, University of Graz, 1985.

[12] R. A. Finkel and J. L. Bentley, Quad Trees: a Data Structure for Retrieval of Composite Keys, Acta Informatica, vol. 4, 1974, pp. 1-9. | Zbl 0278.68030

[13] M. F. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal ACM 28, 1981, pp. 696-706. | MR 677081 | Zbl 0468.68049

[14] M. F. Fredman, Lower Bounds on the Complexity of Some Optimal Data Structures, SIAM Journal on Computing 10, 1981, pp. 1-10. | MR 605599 | Zbl 0454.68006

[15] H. N. Gabow, J. L. Bentley and R. E. Tarjan, Scaling and Related Techniques for Geometry Problems, Proc. 16th Symp. on Theory of Computing, 1984, pp. 135-143.

[16] D. T. Lee and C. K. Wong, Worst Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees, Acta Informatica, vol. 9, 1977, pp. 23-29. | MR 464676 | Zbl 0349.68016

[17] D. T. Lee and C. K. Wong, Finding Intersection of Rectangles by Range Search, Journal of Algorithms, vol. 2, 1981, pp. 337-347. | MR 640518

[18] D. T. Lee and C. K. Wong, Quintary Trees: a File Structure for Multidimensional Database Systems, A.C.M. Trans. on Database Systems, vol. 5, 1980, pp. 339-353. | Zbl 0441.68122

[19] J. Van Leeuwen and D. Wood, Dynamization of Decomposable Searching Problems, Information Processing Letters, vol. 10, 1980, pp. 51-56. | MR 564499

[20] G. S Lueker and D. E. Willard, A Data Structure for Dynamic Range Queries, Information Processing Letters, vol. 15, 1982, pp. 209-213. | MR 684253 | Zbl 0511.68080

[21] J. Nievergelt, H. Hinterberger and K. Sevcik, The Grid File: an Adaptable, Symmetric Multikey Data Structure, A.C.M. Trans. on Database Systems, vol. 9, 1984, pp. 38-71.

[22] M. H. Overmars, The Design of Dynamic Data Structures, Lectures Notes on Computer Science, Vol. 156, Springer Verlag, New York. | MR 710832 | Zbl 0545.68009

[23] M. H. Overmars, The Equivalence of Rectangle Containment, Rectangle Enclosure and ECDF Searching, Tech. Report RUU-CS-81-1, Dept. of Computer Science, University of Utrecht, 1981.

[24] J. T. Robinson, The K-D-B Tree: a Search Structure for Large Multidimensional Dynamic Indexes, Proc. of the SIGMOD Conference, 1981, pp. 10-18.

[25] J. Vuillemin, A Unifying Look at Data Structures, Communications of A.C.M., Vol. 23, 1980, pp. 229-239. | MR 567151 | Zbl 0434.68047

[26] D. E. Willard, New Data Structures for Orthogonal Range Queries, S.I.A.M. Journal on Computing, Vol. 14, 1985, pp. 232-253. | MR 774942 | Zbl 0564.68071

[27] D. E. Willard, Lower Bounds for Dynamic Range Queries That Permit Subtraction (to appear).

[28] D. E. Willard and G. S. Lueker, Adding Range Restriction Capability to Dynamic Data Structures, Journal A.C.M., Vol. 32, 1985, pp. 597-617. | MR 796204 | Zbl 0629.68097