“A consistent hierarchical representation for vector data” by Nelson and Samet

A consistent hierarchical data structure for the representation of vector data is presented. It makes use of a concept termed a line segment fragment to prevent data degradation under splitting or clipping of vector primitives. This means that the insertion and subsequent deletion (and vice versa) of a vector leaves the data unchanged. Vectors are represented exactly and not as digital approximations. The data is dynamically organized by use of simple probabilistic splitting and merging rules. The use of the structure for implementing a geographic information system is described. Algorithms for constructing and manipulating the structure are provided. Results of empirical tests comparing the structure to other representations in the literature are given.

1. {Ayal85}- D. Ayala, P. Brunet, R. Juan, and I. Navazo, Object representation by means of nonminimal division quadtres and octrees, ACM Transactions on Graphics 4, 1(January 1985): 41-59.
2. {Bent75} – J.L. Bentley, A survey of techniques for fixed radius near neighbor searching, SI,AC Report No. 186, Stanford Linear Accelerator Center, Stanford University, Stanford, CA, August 1975.
3. {Carl85}- I. Carlbom, I. Chakravurty, and D. Vanderschel, A hierarchical data structure for representing the spatial decomposition of 3-D objects, IEEE Computer Graphics and Applicalions 5, 4(April 1985), 24-31.
4. {Come79}- D. Comer, The Ubiquitous B-tree, ACM Computing Surveys 11, 2(June 1979), 121-137.
5. {Fink74} – B.A. Finkel and J.L. Bentley, Quad trees: a data structure for retrievM on composite keys, Acta Information 4, 1(1974), 1-9.
6. {Fuji85} – K. Fujimura and T.L. Kunii, A hierarchical space indexing method, Proceedings of Computer Graphics ’85, Tokyo, 1985, T1-4, 1-14.
7. {Garg82}- I. Gurguntini, An effective way to represent quadtrees, Communications of the ACIUI 25, 12(December 1982), 905-910.
8. {Hunt79} – G.M. Hunter and K. Steiglilz, Operations on images using quad trees, IEEE Transactions on Pattern Analysis and Machine Tntelligence 1, 2(April 1979), 145-153.
9. {Klin71}- A. Klinger, Patterns and Search Statistics, in Optimizing Methods in Statistics, J.S. Rustagi, Ed., Academic Press, New York, 1971, 303-337.
10. {Rose83} – A. Rosenfeld, H. Samet, C. Shaffer, and R.E. Webber, Application of hierarchical data structures to geographical information systems phase II, Computer Science TR 1327, University of Maryland, College Park, MD, September 1983.
11. {Same84a}- H. Samet and R.E. Webber, On encoding boundaries with quadtrees, IEEE Transactions on Pattern Analysis and Machine Intelligence 6,’3(May 1984), 365-369.
12. {Same84b} – H. Sz.met, The quadtree and related hierarchical data structures, ACM Camputiug Survegs 16, 2(June 1984), 187-260.
13. {Same85a} H. Samet and M. Tamminen, Efficient component, labeling of images of arbit, rary dimension, Computer Science TR-1480, University of Maryland, College Park, MD, February 1985.
14. {Same85b} H. Sumet., C.A. Shuffer, and R.E. Webber, The segment quadtree: a linear quadtree-based representation for linear features, Proceedings of Computer Vision and Pattern Recognition 85, San Francisco, June 1985, 385-389.
15. {Same85c} – H. Samet and R.E. Webber, Storing a collection of polygons using quadtrees, ACM Transactions on Graphics 4, 3(July 1085), 182-222.
16. {Same85d}- H. Samet, A. Rosenfcld, C.A. Shaffer, B.C. Nelson, Y-G. Huang, and K. Fujimura, Appiication of hierrchical data structures to geographic information systems: phase IV, Computer Science TR-1578, University of Maryland, CoIlege Park, MD, December 1985.
17. {Shne81}- M. Shneier, Calculations of geometric properties using quadtrees, Computer Graphics and Image Processing 16, 3(July 1981), 296-302.
18. {Tamm83} – M. Tamminen, Performance analysis of cell based geometric file organizations, Computer Vision, Graphics, and Image Processing 24, 2(November 1983), 168-181.