Hierarchical representations of collections of small rectangles

ABSTRACT

A tutorial survey is presented of hierarchical data structures for representing collections of small rectangles. Rectangles are often used as an approximation of shapes for which they serve as the minimum rectilinear enclosing object. They arise in applications in cartography as well as very large-scale integration (VLSI) design rule checking. The different data structures are discussed in terms of how they support the execution of queries involving proximity relations. The focus is on intersection and subset queries. Several types of representations are described. Some are designed for use with the plane-sweep paradigm, which works well for static collections of rectangles. Others are oriented toward dynamic collections. In this case, one representation reduces each rectangle to a point in a higher multidimensional space and treats the problem as one involving point data. The other representation is area based—that is, it depends on the physical extent of each rectangle.

REFERENCES

• 1: ABEL, D. J. 1985. Some elemental operations on linear quadtrees for geographic information systems. Comput. J. 28, i (February), 73-77.
• 2: ABEL, D. J., AND SMITH, J. L. 1983. A data structure and algorithm based on a linear key for a rectangle retrieval problem. Comput. Vision Graph. Image Process. 24, 1 (Oct.), 1-13.
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: 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]
• 5: BENTLEY, J. L. 1977. Algorithms for Klee's rectangle problems. Computer Science Department, Carnegie-Mellon University, Pittsburgh.
• 6: BENTLEY, J. L. 1979. Decomposable searching problems. Inf. Process. Lett. 8, 5 (June), 244-251.
• 7: BENTLEY, J. L., AND MAURER, H. A. 1980. Efficient worst-case data structures for range searching. Acta Inf. 13, 2, 155-168.
• 8: BENTLEY, J. L., AND OTTMANN, T. A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28, 9 (Sept.), 643-647.
• 9: BENTLEY, J. L., AND WOOD, D. 1980. An optimal worst-case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. 29, 7 (July), 571-577.
• 10: BUCHER, W., AND EOELSBRUNNER, H. 1983. On expected and worst-case segment trees. In Advances in Computing Research, vol. 1, Computational Geometry, F. P. Preparata, Ed. JAI Press, Greenwich, Conn., pp. 109-125.
• 11: CHAZELLE, B., AND GUIBAS, L. J. 1986a. Fractional cascading: I. A data structuring technique. Algorithmica 1, 2, 133-162.
• 12: CHAZELLE, B., AND GUIBAS, L. J. 1986b. Fractional cascading: II. Applications. Algorithmica 1, 2, 163-191.
• 13: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 14: EDELSBRUNNER, H. 1980a. Dynamic rectangle intersection searching. Institute for Information Processing Rept. 47, Technical University of Graz, Graz, Austria.
• 15: EDELSBRUNNER, H. 1980b. Dynamic data structures for orthogonal intersection queries. Institute for Information Processing. Rept. 59, Technical University of Graz, Graz, Austria.
• 16: EDELSBRUNNER, I-I. 1982. Intersection problems in computational geometry. Institute for Information Processing Rept. 93, Technical Univ. of Graz, Graz, Austria.
• 17: EDELSBRUNNER, H. 1983a. A new approach to rectangle intersections: Part I. Int. J. Comp. Math. 13, 3-4, 209-219.
• 18: EDELSBRUNNER, H. 1983b. A new approach to rectangle intersections: Part II. Int. J. Comput. Math. 13, 3-4, 221-229.
• 19: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 20: Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
• 21: FINKEL, R. A., AND BENTLEY, J. L. 1974. Quad trees: A data structure for retrieval on composite keys. Acta Inf. 4, 1, 1-9.
• 22: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 23: GUIBAS, L. J., AND SEOGEWICK, R. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual IEEE Symposium on the Foundations of Computer Science (Ann Arbor, Mich., Oct.). IEEE, New York, pp. 8-21.
• 24: Oliver Gunther , Eugene Wong, Efficient structures for geometric data management, 1987
• 25: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 26: HARARY, F. 1969. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 27: HINRICHS, K. 1985a. The grid file system: Implementation and case studies of applications. Ph.D. dissertation, Institut fur Informatik, ETH, Zurich, Switzerland.
• 28: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 29: HINRICHS, K., AND NIEVERGELT, J. 1983. The grid file: A data structure designed to support proximity queries on spatial objects. In Proceedings of the WG'83 (International Workshop on Graphtheoretic Concepts in Computer Science), M. Nagl and J. Perl, Eds. (Trauner Verlag, Linz, Austria), pp. 100-113.
• 30: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 31: HUNTER, G. M., AND STEIGLITZ, K. 1979. Operations on images using quad trees. IEEE Trans. Pattern Anal. Mach. Intell. 1, 2 (Apr.), 145-153.
• 32: Gershon Kedem, The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proceedings of the 19th conference on Design automation, p.352-357, January 1982
• 33: KLEE, V. 1977. Can the measure of U {a,, bi} be computed in less than O(n log n) steps? Am. Math. Monthly 84, 4 (Apr.), 284-285.
• 34: KLINGER, A. 1971. Patterns and search statistics. In Optimizing Methods in Statistics, J. S. Rustagi, Ed. Academic Press, Orlando, Fla., pp. 303-337.
• 35: 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
• 36: LAUTHER, U. 1978. Four-dimensional binary search trees as a means to speed up associative searches in design rule verification of integrated circuits. J. Design Automat. Fault-Tolerant Comput. 2, 3 (July), 241-247.
• 37: LEE, D. T. 1983. Maximum clique problem of rectangle graphs. In Advances in Computing Research. Vol. 1, Computational Geometry. F. P. Preparata, Ed. JAI Press, Greenwich, Conn., pp. 91-107.
• 38: LEE, D. T., AND PREPARATA, F. P. 1982. An improved algorithm for the rectangle enclosure problem. J. Algorithms 3, 3 (Sept.), 218-224.
• 39: MATSUYAMA, T., HAO, L. V., AND NAGAO, M. 1984. A file organization for geographic information systems based on spatial proximity. Cornput. Vision Graph. Image Process. 26, 3 (June), 303-318.
• 40: MCCREIGHT, E. M. 1980. Efficient algorithms for enumerating intersecting intervals and rectangles. Report CSL-80-9, Xerox Palo Alto Research Center, Palo Alto, Calif. (June).
• 41: MCCREIGHT, E. M. 1985. Priority search trees. SIAM J. Comput. 14, 2 (May), 257-276.
• 42: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 43: ORENSTEIN, J. A. 1982. Multidimensional tries used for associative searching. Inf. Process. Lett. 14, 4 (June), 150-157.
• 44: OVERMARS, M. H. 1988. Geometric data structures for computer graphics: An overview. In Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, Ed. Springer-Verlag, Berlin, pp. 21-49.
• 45: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 46: Mireille Regnier, Analysis of grid file algorithms, BIT, v.25 n.2, p.335-358, 1985 [doi>10.1007/BF01934379]
• 47: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 48: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 49: ROSENBERG, J. B. 1985. Geographical data structures compared: A study of data structures supporting region queries. IEEE Trans. Comput. Aided Design 4, i (Jan.), 53-67.
• 50: Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
• 51: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• 52: SAMET, H. 1980. Region representation: Quadtrees from binary arrays. Comput. Graph. Image Process. 13, i (May), 88-93.
• 53: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 54: SAMET, H. 1989a. Fundamentals of Spatial Data Structures. Addison-Wesley, Reading, Mass.
• 55: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 56: SAMET, H., AND TAMMINEN, M. 1985. Computing geometric properties of images represented by linear quadtrees. IEEE Trans. Pattern Anat. Mach. InteU. 7, 2 (Mar.), 229-240.
• 57: Hanan Samet , Markku Tamminen, Efficient Component Labeling of Images of Arbitrary Dimension Represented by Linear Bintrees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.579-586, July 1988 [doi>10.1109/34.3918]
• 58: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 59: SELLIS, T., ROUSSOPOULOS, N., AND FALOUTSOS, C. 1987. The R*-tree: A dynamic index for multidimensional objects. Computer Science TR-1795, Univ. of Maryland, College Park, Md.
• 60: Clifford Alan Shaffer, Application of alternative quadtree representations (vlsi, data structures), 1986
• 61: SHAMOS, M. I., AND HOEY, D. 1976. Geometric intersection problems. In Proceedings of the 17th Annual IEEE Symposium on the Foundations of Computer Science (Houston, October). IEEE, New York, pp. 208-215.
• 62: SHNEIER, M. 1981. Calculations of geometric properties using quadtrees, Comp. Graph. Image Process. 16, 3 (July), 296-302.
• 63: SIX, H. W., AND WOOD, D. 1980. The rectangle intersection problem revisited. BIT 20, 4, 426- 433.
• 64: SIX, H. W., AND WOOD, D. 1982. Counting and reporting intersections of d-ranges. IEEE Trans. Comput. 31, 3 (March), 181-187.
• 65: STONEBRAKER, M., SELLIS, T., AND HANSON, E. 1986. An analysis of rule indexing implementations in data base systems. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S.C., Apr.), pp. 353- 364.
• 66: TARJAN, R. E. 1983. Updating a balanced search tree in 0(1) rotations. Inf. Process. Lett. 16, 5 (June), 253-257.
• 67: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 68: VAISHNAVI, V., AND WOOD, D. 1980. Data structures for the rectangle containment and enclosure problems. Comp. Graph. Image Process. 13, 4 (Aug.), pp. 372-384.
• 69: VAISHNAVI, V., AND WOOD, D. 1982. Rectilinear line segment intersection, layered segment trees and dynamization. J. Algorithms 3, 2 (June), pp. 160- 176.
• 70: VAN LEEUWEN, J. AND WOOD, D. 1981. The measure problem for rectangular ranges in d-space. J. Algorithms 2, 3 (Sept.), 282-300.
• 71: VOELCKER, H. B., AND REQUICHA, A. A. G. 1977. Geometric modeling of mechanical parts and processes. IEEE Comp. 10, 12 (Dec.), 48-57.
• 72: WEIDE, B. W. 1978. Statistical methods in algorithm design and analysis. Res. Rep. CMU-CS-78-142, Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pa.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.5 FILES
      Subjects: Organization/structure

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Routing and layout

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Theory