Patent
1992-04-02
1994-06-07
Herndon, Heather R.
395141, G06F 1562
Patent
active
053197437
ABSTRACT:
An improved graphical data structure and method for processing geometrical data stored in a two-dimensional area. The invention is especially suited to storing, deleting, and conducting queries of data related to two-dimensional objects, such as the elements of a VLSI chip layout. A two-dimensional area is provided for storing a plurality of two-dimensional objects. The area may be sub-divided into a horizontal plane and a vertical plane, wherein each plane may contain one or more surfaces. Each surface typically contains a plurality of stripes of equal horizontal dimension, and the stripes are each sub-divided into sub-stripes. An object whose minimum bounding box intersects a particular sub-stripe is represented in one of four bucket lists associated with that sub-stripe. In one example of a preferred embodiment, the bucket list is selected depending upon whether the portion of the object that intersects the sub-stripe is the object's lower-left corner, left edge, bottom edge, or another portion of the object. Each bucket list is made up of a bucket list head and a number of buckets. Routines are provided for inserting objects into the graphical data structure, deleting objects from the structure, and conducting regional queries of the structure.
REFERENCES:
patent: 5170353 (1992-12-01), Verstraete
Bently, "Multidimensional Binary Search Trees Used for Associate Searching", Communications of ACM, vol. 18, pp. 509-517, Sep. 1975; place of publication unknown.
Brown, "Multiple Storage Quad Trees: A Simpler Faster Alternative to Bi-Sector List Quad Trees", IEEE Transactions on CAD, vol. CAD-5, No. 3, pp. 419-419, Jul. 1986p place of publication unknown.
Fontayne & Bowman, "The Multiple Storage Radix Hash Tree: An Improved Region Query Data Structure", Digest of Technical Papers, ICCAD-87, pp. 302-305, undated; place of publication unknown.
Kadem, "The Quad-CIF Tree: A Data Structure for Hierarchical On-Line Algorithms", Proceedings of the 19th Design Automation Conference, pp. 352-357, Jun. 1982; place of publication unknown.
Li et al. "Two Layer Quad Trees: A Data Structure for High-Speed Interactive Layout Tools", Digest of Technical Papers, ICCAD-88, pp. 530-533, undated; place of publication unknown.
Ousterhout, "Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools", IEEE Transactions on Computer-Aided Design, vol. CAD-3, No. 1, Jan. 1984, pp. 87-100; place of publication unknown.
Rosenberg, "Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries", IEEE Transactions on CAD, vol. CAD-4, No. 1, pp. 53-67, Jan. 1985; place of publication unknown.
Samet, "Hierarchical Representations of Collections of Small Rectangles", ACM Computing Surveys, vol. 20, No. 4, Dec. 1988; pp. 271-309, place of publication unknown.
Sherer et al., "Smals: A Novel Database for Two-Dimensional Object Location", IEEE Transactions on CAD, vol. 9 No. 1, pp. 57-65, Jan. 1990; place of publication unknown.
Dutta Shiraj R.
Rao Nagaraja R.
Roy Ashutosh K.
Digital Equipment Corporation
Herndon Heather R.
Jankus Almis
LandOfFree
Intelligent and compact bucketing method for region queries in t does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Intelligent and compact bucketing method for region queries in t, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intelligent and compact bucketing method for region queries in t will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-800234