ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The Quadtree and Related Hierarchical Data Structures.

Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
@article{DBLP:journals/csur/Samet84,
  author    = {Hanan Samet},
  title     = {The Quadtree and Related Hierarchical Data Structures},
  journal   = {ACM Comput. Surv.},
  volume    = {16},
  number    = {2},
  year      = {1984},
  pages     = {187-260},
  ee        = {db/journals/csur/Samet84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A tutorial survey is presented of the quadtree and related hierarchical data structures. They are based on the principle of recursive decomposition. The emphasis is on the representation of data used in applications in image processing, computer graphics, geographic information systems, and robotics. There is a greater emphasis on region data (i.e., two-dimensional shapes) and to a lesser extent on point, curvilinear, and three-dimensional data. A number of operations in which such data structures find use are examined in greater detail.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Online Edition: ACM Digital Library

References

[Abel 1984]
...
[Abel and Smith 1983]
...
[Aho et al. 1974]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ahuja 1983]
...
[Ahuja and Nash 1984]
...
[Anderson 1983]
D. P. Anderson: Techniques for Reducing Pen Plotting Time. ACM Trans. Graph. 2(3): 197-212(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ballard 1981]
Dana H. Ballard: Strip Trees: A Hierarchical Representation for Curves. Commun. ACM 24(5): 310-321(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bell et al. 1983]
...
[Bentley 1975a]
...
[Bentley 1975b]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bentley and Friedman 1979]
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bentley and Stanat 1975]
Jon Louis Bentley, Donald F. Stanat: Analysis of Range Searches in Quad Trees. Inf. Process. Lett. 3(6): 170-173(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Besslich 1982]
...
[Blum 1967]
...
[Brooks and Lozano Perez 1983]
Rodney A. Brooks, Tomás Lozano-Pérez: A Subdivision Algorithm Configuration Space for Findpath With Rotation. IJCAI 1983: 799-806 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Burkhardt 1983]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Burt 1980]
...
[Burt et al. 1981]
...
[Burton 1977]
Warren Burton: Representation of Many-Sided Polygons and Polygonal Lines for Rapid Processing. Commun. ACM 20(3): 166-171(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Burton and Kollias 1983]
...
[Carlson 1982]
...
[Chien and Aggrawal 1984]
...
[Cohen et al. 1980]
...
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Connolly 1984]
...
[Cook 1978]
...
[Creutzburg 1981]
...
[Davis and Roussopoulos 1980]
Larry S. Davis, Nick Roussopoulos: Approximate pattern matching in a pattern database system. Inf. Syst. 5(2): 107-119(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeCoulon and Johnsen 1976]
...
[DeFloriani et al. 1982]
...
[DeMillo et al. 1978]
Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton: Preserving Average Proximity in Arrays. Commun. ACM 21(3): 218-231(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Doctor and Torborg 1981]
...
[Duda and Hart 1973]
...
[Dyer 1980]
...
[Dyer 1981]
...
[Dyer 1982]
...
[Dyer et al. 1980]
Charles R. Dyer, Azriel Rosenfeld, Hanan Samet: Region Representation: Boundary Codes from Quadtrees. Commun. ACM 23(3): 171-179(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Eastman 1970]
...
[Edelsbrunner 1984]
...
[Edelsbrunner and van Leeuwen 1983]
...
[Edelsbrunner e tal. 1985]
Herbert Edelsbrunner, Leonidas J. Guibas, Jorge Stolfi: Optimal Point Location in a Monotone Subdivision. SIAM J. Comput. 15(2): 317-340(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fagin et al. 1979]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Faugeras and Ponce 1983]
Olivier D. Faugeras, Jean Ponce: Prism Trees: A Hierarchical Representation for 3-D Objects. IJCAI 1983: 982-988 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Faugeras et al. 1984]
...
[Faverjon 1984]
...
[Finkel and Bentley 1974]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fredkin 1960]
...
[Freeman 1974]
Herbert Freeman: Computer Processing of Line-Drawing Images. ACM Comput. Surv. 6(1): 57-97(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Friedman et al. 1977]
Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw. 3(3): 209-226(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gargantini 1982a]
Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gargantini 1982b]
...
[Gargantini 1983]
...
[Gaston and Lozano Perez 1984]
...
[Gibson and Lucas 1982]
...
[Gillepsie and Davis 1981]
...
[Gomez and Guzman 1979]
...
[Grosky and Jain 1983]
...
[Harary 1969]
...
[Hertel and Mehlhorn 1983]
Stefan Hertel, Kurt Mehlhorn: Fast Triangulation of Simple Polygons. FCT 1983: 207-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hinrichs and Nievergelt 1983]
Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hoare 1972]
...
[Horowitz and Pavlidis 1976]
Steven L. Horowitz, Theodosios Pavlidis: Picture Segmentation by a Tree Traversal Algorithm. J. ACM 23(2): 368-388(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Huffman 1952]
...
[Hunter 1978]
...
[Hunter and Steiglitz 1979a]
...
[Hunter and Steiglitz 1979b]
...
[Ibrahim 1984]
...
[Ismail and Steele 1980]
...
[Jackins and Tanimoto 1980]
...
[Jackins and Tanimoto 1983]
...
[Jones and Iyengar 1984]
...
[Kawaguchi and Endo 1980]
...
[Kawaguchi et al. 1980]
...
[Kawaguchi et al. 1983]
...
[Kedem 1981]
...
[Kelly 1971]
...
[Kirkpatrick 1983]
David G. Kirkpatrick: Optimal Search in Planar Subdivisions. SIAM J. Comput. 12(1): 28-35(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Klinger 1971]
...
[Klinger and Dyer 1976]
...
[Klinger and Rhodes 1979]
...
[Knott 1971]
Gary D. Knott: Expandable Open Addressing Hash Table Storage and Retrieval. SIGFIDET Workshop 1971: 187-206 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knowlton 1980]
...
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knuth 1975]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lauzon et al. 1984]
...
[Lee and Shacter 1980]
...
[Lee and Wong 1977]
D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Letelier 1983]
...
[Li et al. 1982]
...
[Linn 1973]
...
[Lipton and Tarjan 1977]
Richard J. Lipton, Robert Endre Tarjan: Application of a Planar Separator Theorem. FOCS 1977: 162-170 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Litwin 1980]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lozano-Perez 1981]
...
[Lumia 1983]
...
[Lumia et al. 1983]
...
[Martin 1982]
...
[Matsuyama et al. 1984]
...
[McCluskey 1965]
...
[McKeown and Denlinger 1984]
...
[Meagher 1982]
...
[Merrett 1978]
...
[Merrett and Otoo 1981]
T. H. Merrett, Ekow J. Otoo: Dynamic Multipaging: A Storage Structure for Large Shared Data Banks. JCDKB 1982: 237-255 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Merrill 1973]
R. D. Merrill: Representation of Contours ad Regions for Efficient Computer Search. Commun. ACM 16(2): 69-82(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Milford and Willis 1984]
...
[Minsky and Pepert 1969]
...
[Morton 1966]
...
[Mudur and Koparkar 1984]
...
[Nagy and Wagle 1979]
George Nagy, Sharad Wagle: Geographic Data Processing. ACM Comput. Surv. 11(2): 139-181(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nievergelt and Preparata 1982]
Jürg Nievergelt, Franco P. Preparata: Plane-Sweep Algorithms for Intersecting Geometric Figures. Commun. ACM 25(10): 739-747(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nievergelt et al. 1984]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nilsson 1969]
Nils J. Nilsson: A Mobile Automaton: An Application of Artificial Intelligence Techniques. IJCAI 1969: 509-520 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oliver and Wiseman 1983a]
M. A. Oliver, Neil E. Wiseman: Operations on Quadtree Encoded Images. Comput. J. 26(1): 83-91(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oliver and Wiseman 1983b]
M. A. Oliver, Neil E. Wiseman: Operations on Quadtree Leaves and Related Image Areas. Comput. J. 26(4): 375-380(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Omalayole and Klinger 1980]
Joseph Olu Omolayole, Allen Klinger: A Hierarchical Data Structure Scheme for Storing Pictures. Pictorial Information Systems 1980: 1-38 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Orenstein 1982]
Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Orenstein 1983]
Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Orenstein and Merrett 1984]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ORourke 1981]
...
[ORourkeand Sloan 1984]
...
[Ouksel and Scheuermann 1983]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Overmars 1983]
Mark H. Overmars: The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Overmars and van Leeuwen 1982]
Mark H. Overmars, Jan van Leeuwen: Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Inf. 17: 267-285(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Peters 1984]
...
[Peucker 1976]
...
[Peuquet 1983]
...
[Peuquet 1983]
...
[Pfaltz and Rosenfeld 1967]
...
[Pietikainen et al. 1982]
...
[Raman and Iyengar 1983]
V. K. Raman, S. Sitharama Iyengar: Properties and Applications of Forests of Quadtrees. BIT 23(4): 472-(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ranade 1981]
...
[Ranade and Shneier 1981]
...
[Ranade et al. 1980]
...
[Ranade et al. 1982]
...
[Reddy and Rubin 1978]
...
[Requicha 1980]
Aristides A. G. Requicha: Representations for Rigid Solids: Theory, Methods, and Systems. ACM Comput. Surv. 12(4): 437-464(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rheinboldt and Mesztenzi 1980]
...
[Riseman and Arbib 1977]
...
[Robinson 1981]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rosenfeld 1983]
...
[Rosenfeld 1984]
...
[Rosenfeld and Kak 1982]
...
[Rosenfeld and Pfaltz 1966]
Azriel Rosenfeld, John L. Pfaltz: Sequential Operations in Digital Picture Processing. J. ACM 13(4): 471-494(1966) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rosenfeld et al. 1982]
...
[Rosenfeld et al. 1983]
...
[Roth 1982]
...
[Rutovitz 1968]
...
[Samet 1980a]
Hanan Samet: Region Representation: Quadtrees from Boundary Codes. Commun. ACM 23(3): 163-170(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samet 1980b]
...
[Samet 1980c]
Hanan Samet: Deletion in Two-Dimensional Quad Trees. Commun. ACM 23(12): 703-710(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samet 1981a]
...
[Samet 1981b]
Hanan Samet: Connected Component Labeling Using Quadtrees. J. ACM 28(3): 487-501(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samet 1981c]
...
[Samet 1982a]
...
[Samet 1982b]
...
[Samet 1983]
Hanan Samet: A Quadtree Medial Axis Transform. Commun. ACM 26(9): 680-693(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samet 1984]
...
[Samet 1985a]
...
[Samet 1985b]
...
[Samet 1985c]
Hanan Samet: Data Structures for Quadtree Approximation and Compression. Commun. ACM 28(9): 973-993(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samet and Krishnamurthy 1983]
...
[Samet and Rosenfeld 1980]
...
[Samet and Shaffer 1984]
...
[Samet and Tamminen 1984]
...
[Samet and Tamminen 1985]
...
[Samet Webber 1982]
...
[Samet Webber 1983]
...
[Samet Webber 1984]
...
[Shamos 1978]
...
[Shamos and Hoey 1975]
Michael Ian Shamos, Dan Hoey: Closest-Point Problems. FOCS 1975: 151-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shneier 1981a]
...
[Shneier 1981b]
...
[Shneier 1981c]
...
[Sloan 1981]
...
[Sloan and Tanimoto 1979]
Kenneth R. Sloan Jr., Steven L. Tanimoto: Progressive Refinement of Raster Images. IEEE Trans. Computers 28(11): 871-874(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Srihari 1981]
Sargur N. Srihari: Representation of Three-Dimensional Digital Images. ACM Comput. Surv. 13(4): 399-424(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sutherland et al. 1974]
Ivan E. Sutherland, Robert F. Sproull, Robert A. Schumacker: A Characterization of Ten Hidden-Surface Algorithms. ACM Comput. Surv. 6(1): 1-55(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tamminien 1981]
...
[Tamminen 1982]
...
[Tamminen 1983]
...
[Tamminen 1984a]
Markku Tamminen: Comment on Quad- and Octtrees. Commun. ACM 27(3): 248-249(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tamminen 1984b]
...
[Tamminen and Samet 1984]
...
[Tanimoto 1976]
...
[Tanimoto 1979]
...
[Tanimoto and Klinger 1980]
...
[Tanimoto and Pavlidis 1975]
...
[Tarjan 1975]
Robert Endre Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22(2): 215-225(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Toussaint 1980]
...
[Tropf and Herzog 1981]
...
[Tucker 1984a]
...
[Tucker 1984b]
...
[Uhr 1972]
...
[Unnikrishnan and Venkatesh 1984]
...
[Van Leeuwen and Wood 1981]
Jan van Leeuwen, Derick Wood: The Measure Problem for Rectangular Ranges in d-Space. J. Algorithms 2(3): 282-300(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Van Lierop 1984]
...
[Warnock 1969]
...
[Webber 1984]
...
[Webber 1978]
...
[Willard 1982]
Dan E. Willard: Polygon Retrieval. SIAM J. Comput. 11(1): 149-165(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Woodwark 1982]
John R. Woodwark: The Explicit Quad Tree as a Structure for Computer Graphics. Comput. J. 25(2): 235-238(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wu et al. 1982]
...
[Yamaguchi et al. 1984]
...
[Yau 1984]
...
[Yau and Srihari 1983]
Mann-May Yau, Sargur N. Srihari: A Hierarchical Data Structure for Multidimensional Digital Images. Commun. ACM 26(7): 504-515(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yerry and Shepard 1983]
...

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Wed Dec 16 19:51:41 2009 by Michael Ley (ley@uni-trier.de)