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) no. 2, pp. 165-176.
@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},
     pages = {165--176},
     publisher = {EDP-Sciences},
     volume = {23},
     number = {2},
     year = {1989},
     mrnumber = {1001724},
     zbl = {0681.68083},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1989__23_2_165_0/}
}
TY  - JOUR
AU  - Talamo, M.
AU  - Gambosi, G.
TI  - An application of $m$-ary trees to the design of data structures for geometric searching problems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1989
SP  - 165
EP  - 176
VL  - 23
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1989__23_2_165_0/
LA  - en
ID  - ITA_1989__23_2_165_0
ER  - 
%0 Journal Article
%A Talamo, M.
%A Gambosi, G.
%T An application of $m$-ary trees to the design of data structures for geometric searching problems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1989
%P 165-176
%V 23
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1989__23_2_165_0/
%G en
%F 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) no. 2, pp. 165-176. http://archive.numdam.org/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 | Zbl

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

[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

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

[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 | Zbl

[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 | Zbl

[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

[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

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

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

[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 | Zbl

[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

[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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl