Intelligent and compact bucketing method for region queries in two-dimensional space
作者： Ashutosh K. Roy , Nagaraja R. Rao , Shiraj R. Dutta
DOI:
关键词:
摘要: An improved graphical data structure and method for processing geometrical stored in a two-dimensional area. The invention is especially suited to storing, deleting, conducting queries of related objects, such as the elements VLSI chip layout. A area provided storing plurality objects. may be sub-divided into horizontal plane vertical plane, wherein each contain one or more surfaces. Each surface typically contains stripes equal dimension, are sub-stripes. object whose minimum bounding box intersects particular sub-stripe represented four bucket lists associated with that sub-stripe. In example preferred embodiment, list selected depending upon whether portion object's lower-left corner, left edge, bottom another object. made up head number buckets. Routines inserting objects structure, deleting from regional structure.
google.co.uk 参考文章(8)
J.B. Rosenberg, Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 4, pp. 53- 67 ,(1985) , 10.1109/TCAD.1985.1270098
R.L. Brown, Multiple Storage Quad Trees: A Simpler Faster Alternative to Bisector List Quad Trees IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 5, pp. 413- 419 ,(1986) , 10.1109/TCAD.1986.1270210
A.D. Sherer, B.S. Stanojevich, R.J. Bowman, SMALS: a novel database for two-dimensional object location IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 9, pp. 57- 65 ,(1990) , 10.1109/43.45857
Li Wanhao, S. Legendre, K. Gardiner, Two-layer quad trees: a data structure for high-speed interactive layout tools international conference on computer aided design. pp. 530- 533 ,(1988) , 10.1109/ICCAD.1988.122564
Rick Achiel Verstraete, Bucket-oriented route planning method, and navigation system comprising a route planner for carrying out such a method ,(1991)
J.K. Ousterhout, Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 3, pp. 87- 100 ,(1984) , 10.1109/TCAD.1984.1270061
Hanan Samet, Hierarchical representations of collections of small rectangles ACM Computing Surveys. ,vol. 20, pp. 271- 309 ,(1988) , 10.1145/50020.50021
Gershon Kedem, The Quad-CIF Tree: A Data Structure for Hierarchical On-Line Algorithms design automation conference. pp. 352- 357 ,(1982) , 10.5555/800263.809229