Region representation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Region representation: quadtrees from boundary codes

Full text

Pdf (714 KB)

Source

Communications of the ACM archive
Volume 23 , Issue 3 (March 1980) table of contents

Pages: 163 - 170

Year of Publication: 1980

ISSN:0001-0782

Author

Hanan Samet

Univ. of Maryland, College Park

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 46, Citation Count: 17

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358826.358836 What is a DOI?

ABSTRACT

An algorithm is presented for constructing a quadtree for a region given its boundary in the form of a chain code. Analysis of the algorithm reveals that its execution time is proportional to the product of the perimeter and the log of the diameter of the region.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Charles R. Dyer , Azriel Rosenfeld , Hanan Samet, Region representation: boundary codes from quadtrees, Communications of the ACM, v.23 n.3, p.171-179, March 1980 [doi>10.1145/358826.358838]
	2	Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
	3	Hunter, G.M., and Steiglitz, K. Operations on images using quadtrees. IEEE Trans. on Pattern Analysis and Machine Intell. 1 (1979), 145-153.
	4	Hunter, G.M., and Steiglitz, K. Linear transformation of pictures represented by quadtrees. Comptr. Graphics and Image Processing 10 (1979), 289-296.
	5	Klinger, A., and Rhodes, M.L. Organization and access of image data by areas. IEEE Trans. on Pattern Analysis and Machine lntell. 1 (1979), 50-60.
	6	Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
	7	Samet, H. An algorithm for converting rasters to quadtrees. To appear in 1EEE Trans. on Pattern Analysis and Machine lntell. (1980).

CITED BY 17

	Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984
	Hanan Samet, Connected Component Labeling Using Quadtrees, Journal of the ACM (JACM), v.28 n.3, p.487-501, July 1981
	Peter R. Atherton, A method of interactive visualization of CAD surface models on a color video display, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.279-287, August 1981
	Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982
	Charles R. Dyer , Azriel Rosenfeld , Hanan Samet, Region representation: boundary codes from quadtrees, Communications of the ACM, v.23 n.3, p.171-179, March 1980
	D. A. Beckley , M. W. Evens , V. K. Raman, Multikey retrieval from K-d trees and QUAD-trees, ACM SIGMOD Record, v.14 n.4, p.291-301, May 1985
	Hanan Samet, Data structures for quadtree approximation and compression, Communications of the ACM, v.28 n.9, p.973-993, Sept. 1985
	David S. Scott , S. Sitharama Iyengar, TID—a translation invariant data structure for storing images, Communications of the ACM, v.29 n.5, p.418-429, May 1986
	Hanan Samet, A quadtree medial axis transform, Communications of the ACM, v.26 n.9, p.680-693, Sept. 1983
	Pere Brunet , Isabel Navazo, Solid representation and operation using extended octrees, ACM Transactions on Graphics (TOG), v.9 n.2, p.170-197, April 1990
	Markku Tamminen , Hanan Samet, Efficient octree conversion by connectivity labeling, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.43-51, July 1984
	Dana H. Ballard, Strip trees: a hierarchical representation for curves, Communications of the ACM, v.24 n.5, p.310-321, May 1981
	Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics. Part I., IEEE Computer Graphics and Applications, v.8 n.3, p.48-68, May 1988
	Gultekin Özsoyoglu , Z. Meral Özsoyoglu , Kumar V. Vadaparty, A scientific database system for polymers and materials engineering needs, Proceedings of the 7th international conference on Scientific and Statistical Database Management, p.138-148, September 28-30, 1994, Charlottesville, Virginia
	Claude Puech , Hussein Yahia, Quadtrees, octrees, hyperoctrees: a unified analytical approach to tree data structures used in graphics, geometric modeling and image processing, Proceedings of the first annual symposium on Computational geometry, p.272-280, June 05-07, 1985, Baltimore, Maryland, United States
	Nikos I. Katevas , Spyros G. Tzafestas , Christos G. Pnevmatikatos, The Approximate Cell Decomposition with Local Node Refinement Global Path Planning Method: Path Nodes Refinement and Curve Parametric Interpolation, Journal of Intelligent and Robotic Systems, v.22 n.3-4, p.289-314, July-August 1998
	Arash Abadpour , Shohreh Kasaei, Color PCA eigenimages and their application to compression and watermarking, Image and Vision Computing, v.26 n.7, p.878-890, July, 2008

INDEX TERMS

Keywords:
borders, chain codes, data structures, quadtrees, regions

Collaborative Colleagues:

Hanan Samet: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player