The DOI matches its Crossref record; 67 of the 67 references it cites were found in a registry or an index.
The Quadtree and Related Hierarchical Data Structures
Abstract
A tutorial survey is presented of the quadtree and related hierarchical data structures. They are based on the principle of recursive decomposition. The emphasis is on the representation of data used in applications in image processing, computer graphics, geographic information systems, and robotics. There is a greater emphasis on region data (i.e., two-dimensional shapes) and to a lesser extent on point, curvilinear, and threedimensional data. A number of operations in which such data structures find use are examined in greater detail.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Harary, F. (1969) · Cited by 10,739
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
A Method for the Construction of Minimum-Redundancy Codes
Huffman, D. (1952) · Proceedings of the IRE · doi:10.1109/jrproc.1952.273898 · Cited by 6,334
Proceedings of the 19th International Joint Conference on Artificial Intelligence
Pujol, J. M., Delgado, J., Ramon Sangüesa, A., & Flache, A. (2005) · International Joint Conference on Artificial Intelligence · Cited by 5,771
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,720
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
Cited by
Overview of the High Efficiency Video Coding (HEVC) Standard
Sullivan, G. J., Ohm, J.-R., Han, W.-J., & Wiegand, T. (2012) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2012.2221191 · Cited by 8,263
Local grayvalue invariants for image retrieval
Schmid, C., & Mohr, R. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.589215 · Cited by 1,432
Adaptive spatial binning of integral-field spectroscopic data using Voronoi tessellations
Cappellari, M., & Copin, Y. (2003) · Monthly Notices of the Royal Astronomical Society · doi:10.1046/j.1365-8711.2003.06541.x · Cited by 1,309
Query evaluation techniques for large databases
Graefe, G. (1993) · ACM Computing Surveys · doi:10.1145/152610.152611 · Cited by 1,262
Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
The anatomy of a context-aware application
Harter, A., Hopper, A., Steggles, P., Ward, A., & Webster, P. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313476 · Cited by 1,107
Image coding using vector quantization: a review
Nasrabadi, N. M., & King, R. A. (1988) · IEEE Transactions on Communications · doi:10.1109/26.3776 · Cited by 958
Real-time, continuous level of detail rendering of height fields
Lindstrom, P., Koller, D., Ribarsky, W., Hodges, L. F., Faust, N., & Turner, G. A. (1996) · Proceedings of the 23rd annual conference on Computer graphics and interactive techniques · doi:10.1145/237170.237217 · Cited by 741
Outline for a theory of intelligence
Albus, J. S. (1991) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.97471 · Cited by 722
The Anatomy of a Context-Aware Application
Harter, A., Hopper, A., Steggles, P., Ward, A., & Webster, P. (2002) · Wireless Networks · doi:10.1023/a:1013767926256 · Cited by 681
Octrees for faster isosurface generation
Wilhelms, J., & Van Gelder, A. (1992) · ACM Transactions on Graphics · doi:10.1145/130881.130882 · Cited by 569
Photorealistic scene reconstruction by voxel coloring
Seitz, S. M., & Dyer, C. R. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609462 · Cited by 543
A general approach to connected-component labeling for arbitrary image representations
Dillencourt, M. B., Samet, H., & Tamminen, M. (1992) · Journal of the ACM · doi:10.1145/128749.128750 · Cited by 512
Self-citationFundamentals of Content-Based Image Retrieval
Long, F., Zhang, H., & Feng, D. D. (2003) · Signals and Communication Technology · doi:10.1007/978-3-662-05300-3_1 · Cited by 511
A Mark 1 Geographical Analysis Machine for the automated analysis of point data sets
OPENSHAW, S., CHARLTON, M., WYMER, C., & CRAFT, A. (1987) · International journal of geographical information systems · doi:10.1080/02693798708927821 · Cited by 508
SR-Tesseler: a method to segment and quantify localization-based super-resolution microscopy data
Levet, F., Hosy, E., Kechkar, A., Butler, C., Beghin, A., Choquet, D., & Sibarita, J.-B. (2015) · Nature Methods · doi:10.1038/nmeth.3579 · Cited by 502
Photorealistic Scene Reconstruction by Voxel Coloring
Seitz, S. M., & Dyer, C. R. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008176507526 · Cited by 492
Image Processing and Data Analysis, The Multiscale Approach
Seymour, L., Starck, J. L., Murtagh, F., & Bijaoui, A. (1999) · Journal of the American Statistical Association · doi:10.2307/2669962 · Cited by 467
Multiresolution path planning for mobile robots
Kambhampati, S., & Davis, L. (1986) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1986.1087051 · Cited by 442
Linear-time connected-component labeling based on sequential local operations
Suzuki, K., Horiba, I., & Sugie, N. (2003) · Computer Vision and Image Understanding · doi:10.1016/s1077-3142(02)00030-9 · Cited by 414
Lelewer, D. A., & Hirschberg, D. S. (1987) · ACM Computing Surveys · doi:10.1145/45072.45074 · Cited by 377
Symmetry as a continuous feature
Zabrodsky, H., Peleg, S., & Avnir, D. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.476508 · Cited by 369
Geographic Data Mining and Knowledge Discovery
(2009) · CRC Press eBooks · doi:10.1201/9781420073980 · Cited by 353
Efficient component labeling of images of arbitrary dimension represented by linear bintrees
Samet, H., & Tamminen, M. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.3918 · Cited by 350
Self-citationSocial Media data: Challenges, opportunities and limitations in urban studies
Martí, P., Serrano-Estrada, L., & Nolasco-Cirugeda, A. (2019) · Computers, Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2018.11.001 · Cited by 325
Spatial crowdsourcing: a survey
Tong, Y., Zhou, Z., Zeng, Y., Chen, L., & Shahabi, C. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00568-7 · Cited by 305
Recent advances in the construction of polygonal finite element interpolants
Sukumar, N., & Malsch, E. A. (2006) · Archives of Computational Methods in Engineering · doi:10.1007/bf02905933 · Cited by 293
Generating octree models of 3D objects from their silhouettes in a sequence of images
Potmesil, M. (1987) · Computer Vision, Graphics, and Image Processing · doi:10.1016/0734-189x(87)90053-3 · Cited by 257
Feigl, K. L., Le Mével, H., Tabrez Ali, S., Córdova, L., Andersen, N. L., DeMets, C., & Singer, B. S. (2014) · Geophysical Journal International · doi:10.1093/gji/ggt438 · Cited by 90
Heberle, H., Carazzolle, M. F., Telles, G. P., Meirelles, G. V., & Minghim, R. (2017) · BMC Bioinformatics · doi:10.1186/s12859-017-1787-5 · Cited by 21
“This verification is done after each iteration of the D3 force placement and queries a quad-tree data structure [35].”
Method
Metadata
- Authors
- Samet, H.
- Venue
- ACM Computing Surveys
- Published
- 1984-06
- Volume
- 16
- Issue
- 2
- Pages
- 187-260
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2050576295
- Cited by
- 2,205
- References
- 67
- FWCI
- 48.27
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.