An application of m -ary trees to the design of data structures for geometric searching problems

M. Talamo; G. Gambosi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1989)

  • Volume: 23, Issue: 2, page 165-176
  • ISSN: 0988-3754

How to cite

top

Talamo, M., and 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 23.2 (1989): 165-176. <http://eudml.org/doc/92329>.

@article{Talamo1989,
author = {Talamo, M., Gambosi, G.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {computational geometry; ECDF searching problem; data structures},
language = {eng},
number = {2},
pages = {165-176},
publisher = {EDP-Sciences},
title = {An application of $m$-ary trees to the design of data structures for geometric searching problems},
url = {http://eudml.org/doc/92329},
volume = {23},
year = {1989},
}

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
PB - EDP-Sciences
VL - 23
IS - 2
SP - 165
EP - 176
LA - eng
KW - computational geometry; ECDF searching problem; data structures
UR - http://eudml.org/doc/92329
ER -

References

top
  1. [1] J. L. BENTLEY, Multidimensional Divide and Conquer, Communications of A.C.M., vol. 23, 1980, pp. 214-229. Zbl0434.68049MR567150
  2. [2] J. L. BENTLEY, Multidimensional Binary Search Trees Used for Associative Searching, Communications of A.C.M., vol. 18, 1975, pp. 509-517. Zbl0306.68061
  3. [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. Zbl0411.68055
  4. [4] J. L. BENTLEY, Decomposable Searching Problems, Information Processing Letters, vol. 8, 1979, pp. 244-251. Zbl0404.68067MR534072
  5. [5] J. L. BENTLEY and J. H. FRIEDMAN, Data Structures for Range Searching, Computing Surveys, vol. 11, 1979, pp. 397-409. 
  6. [6] J. L. BENTLEY and H. A. MAURER, Efficient Worst-case Data Structures for Range Searching, Acta Informatica, vol. 13, 1980, pp. 155-168. Zbl0423.68029MR564462
  7. [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. Zbl0461.68065MR604869
  8. [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. [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. MR581619
  10. [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. [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. Zbl0624.68054
  12. [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. Zbl0278.68030
  13. [13] M. F. FREDMAN, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal ACM 28, 1981, pp. 696-706. Zbl0468.68049MR677081
  14. [14] M. F. FREDMAN, Lower Bounds on the Complexity of Some Optimal Data Structures, SIAM Journal on Computing 10, 1981, pp. 1-10. Zbl0454.68006MR605599
  15. [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. [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. Zbl0349.68016MR464676
  17. [17] D. T. LEE and C. K. WONG, Finding Intersection of Rectangles by Range Search, Journal of Algorithms, vol. 2, 1981, pp. 337-347. MR640518
  18. [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. Zbl0441.68122
  19. [19] J. VAN LEEUWEN and D. WOOD, Dynamization of Decomposable Searching Problems, Information Processing Letters, vol. 10, 1980, pp. 51-56. MR564499
  20. [20] G. S LUEKER and D. E. WILLARD, A Data Structure for Dynamic Range Queries, Information Processing Letters, vol. 15, 1982, pp. 209-213. Zbl0511.68080MR684253
  21. [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. [22] M. H. OVERMARS, The Design of Dynamic Data Structures, Lectures Notes on Computer Science, Vol. 156, Springer Verlag, New York. Zbl0545.68009MR710832
  23. [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. [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. [25] J. VUILLEMIN, A Unifying Look at Data Structures, Communications of A.C.M., Vol. 23, 1980, pp. 229-239. Zbl0434.68047MR567151
  26. [26] D. E. WILLARD, New Data Structures for Orthogonal Range Queries, S.I.A.M. Journal on Computing, Vol. 14, 1985, pp. 232-253. Zbl0564.68071MR774942
  27. [27] D. E. WILLARD, Lower Bounds for Dynamic Range Queries That Permit Subtraction (to appear). Zbl0596.68066
  28. [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. Zbl0629.68097MR796204

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.