A review of quadtree-based strategies for interfacing coverage data with digital elevation models in grid form

References

• ABEL , D. J. , 1983 , Towards a relational database for geographic information systems . Workshop on Databases in the Natural Sciences , Collected papers from the workshop held in Brisbane, Australia, on 7–9 September 1983 , edited by D.J. Abel, R. Hnatiuk, A. W. Moore and J. L. Smith ( Brisbane , Australia CSIRO Cunningham Laboratory ), pp. 199 – 208 .
   Google Scholar
• ABEL , D. J. , 1984 , A B+ -tree structure for large quadtrees . Computer Vision, Graphics, and Image Processing , 27 , 19 .
   Google Scholar
• ABEL , D. J. , and SMITH , J. L. , 1983 , A data structure algorithm based on a linear key for a rectangle retrieval problem . Computer Vision, Graphics and Image Processing , 24 , 1 .
   Google Scholar
• ABEL , D. J. , and SMITH , J. L. , 1984 a , A data structure and query algorithm for a database of areal entities . Australian Computer Journal , 16 , 147 .
   Google Scholar
• ABEL , D. J. , and SMITH , J. L. , 1984 b , A simple approach to the nearest-neighbour problem . Australian Computer Journal , 16 , 140 .
   Google Scholar
• ALLAM , M. M. , 1978 , DTM's application in topographic mapping . Proceedings of the Digital Terrain Models (DTM) Symposium of the ASP/ACSM held in St Louis, Missouri, on 9–11 May 1978 ( Falls Church , Virginia American Society for Photogrammetry/American Congress on Surveying and Mapping ), pp. 1 – 15 .
   Google Scholar
• AYALA , D. , BRUNET , P. , JUAN , R. , and NAVAZO , I. , 1985 , Object representation by means of nonminimal division quadtrees and octrees . ACM Transactions on Graphics , 4 , 41 .
   Web of Science ®Google Scholar
• CEBRIAN , J. A. , MOWER , J. E. , and MARK , D. M. , 1985 , Analysis and display of digital elevation models within a quadtree-based geographic information system . Proceedings of the Seventh International Symposium on Computer-Assisted Cartography (Auto-Carto 7) held in Washington, D.C. on 11–14 March 1985 ( Falls Church , Virginia American Society of Photogrammetry and Remote Sensing, American Congress on Surveying and Mapping ), pp. 55 – 64 .
   Google Scholar
• CHEN , Z. -T. , and TOBLER , W. , 1986 , Quadtree representatives of digital terrain . Proceedings, Auto Carto London , Vol. 1 , edited by M. Blakemore ( London Auto Carto ) ( available from the Royal Institution of Chartered Surveyors ), pp. 475 – 484 .
   Google Scholar
• COMEAU , M. A. , 1981 , A coordinate reference system for spatial data processing . Canada Land Data Systems , Technical Bulletin No. 3 , Lands Directorate, Environment Canada , Ottawa , Canada .
   Google Scholar
• COOK , B. G. , 1979 , The structural and algorithmic basis of a geographic data base . Proceedings of the International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems held in Dedham, Massachusetts , Vol. 4 , edited by G. Dutton ( Cambridge , Massachusetts Harvard University Laboratory for Computer Graphics and Spatial Analysis ), pp. 1 – 30 .
   Google Scholar
• DYER , C. R. , 1982 , The space efficiency of quadtrees . Computer Graphics and Image Processing , 19 , 335 .
   Google Scholar
• ELASSAL , A. A. , and CARUSO , V. M. , 1983 , Digital elevation models . U.S. Geological Survey Circular 895-B , U.S. Geological Survey , Reston , Virginia , U.S.A.
   Google Scholar
• FOWLER , R. J. , and LITTLE , J. J. , 1979 , Automatic extraction of irregular network digital terrain models . Proceedings of SIGGRAPH '79 , pp. 199 – 207 .
   Google Scholar
• GARGANTINI , I. , 1982 a , An effective way to represent quadtrees . Communications of the ACM , 25 , 905 .
   Web of Science ®Google Scholar
• GARGANTINI , I. , 1982 b , Linear octtrees for fast processing of three dimensional objects . Computer Graphics and Image Processing , 20 , 365 .
   Google Scholar
• HUNTER , G. M. , 1978 , Efficient computation and data structures for graphics . Ph.D. dissertation , Department of Electrical Engineering and Computer Science, Princeton University .
   Google Scholar
• HUNTER , G. M. , and STEIGLITZ , K. , 1979 , Operations on images using quadtrees . I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence , 1 , 145 .
   PubMed Web of Science ®Google Scholar
• KAVOURAS , M. , 1985 , Design of a geometry-system to handle 3-D mining information . Presented at the Sixth International Congress on Mining Surveying held in Harrogate, England in September 1985 .
   Google Scholar
• KAVOURAS , M. , and MASRY , S. E. , 1987 , An information system for geosciences design considerations . Proceedings of the Eighth International Symposium on Computer-Assisted Cartography (Auto-Carto 8) held in Baltimore, Maryland on 29 March–3 April 1987 ( Falls Church , Virginia American Society of Photogrammetry and Remote Sensing/American Congress on Surveying and Mapping ), pp. 336 – 345 .
   Google Scholar
• KAWAGUCHI , E. , ENDO , T. , and MATSUNAGA , J. -I. , 1983 , Depth-first picture expression viewed from digital picture processing . I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence , 5 , 373 .
   PubMed Web of Science ®Google Scholar
• KLINGER , A. , 1971 , Patterns and search statistics . In Optimizing Methods in Statistics , edited by J. S. Rustagi ( New York Academic Press ).
   Google Scholar
• KLINGER , A. , and DYER , C. R. , 1976 , Experiments on picture representation using regular decomposition . Computer Graphics and Image Processing , 5 , 69 .
   Google Scholar
• LABONTE , A. E. , 1977 , Two dimensional image coding by Micro Adaptive Picture Sequencing (MAPS) . Proceedings of the International Optical Computing Conference, SPIE, held in San Diego, California on 25–26 August 1977 , Vol. 119 ( San Diego SPIE ), pp. 99 – 106 .
   Google Scholar
• LAUZON , J. P. , 1983 , Two-dimensional run-encoding for spatially referenced data . MA project , Department of Geography, State University of New York at Buffalo , Buffalo , New York , U.S.A.
   Google Scholar
• LAUZON , J. P. , MARK , D. M. , KIKUCHI , L. , and GUEVARA , J. A. , 1985 , Two-dimensional run-encoding for quadtree representation . Computer Vision, Graphics, and Image Processing , 30 , 56 .
   Google Scholar
• LEIFER , L. A. , and MARK , D. M. , 1987 , Recursive approximation of topographic data using quadtrees and orthogonal polynomials . Proceedings of the Eighth International Symposium on Computer-Assisted Cartography (Auto-Carto 8) held in Baltimore, Maryland, on 29 March–3 April 1987 ( Falls Church , Virginia American Society of Photogrammetry and Remote Sensing/American Congress on Surveying and Mapping ), pp. 650 – 659 .
   Google Scholar
• LITTLE , J. J. , 1979 , Strategies for interfacing geographic information systems . Proceedings of the International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems held in Dedham, Massachusetts , Vol. 4 , edited by G. Dutton ( Cambridge , Massachusetts Harvard University Laboratory for Computer Graphics and Spatial Analysis ), pp. 1 – 11 .
   Google Scholar
• MAKAROVIC , B. , 1973 , Progressive sampling for digital terrain models . ITC Journal , 3 , 397 .
   Google Scholar
• MAKAROVIC , B. , 1979 , Digital terrain models—A constituent of geo-information systems . Proceedings of the International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems held in Dedham, Massachusetts , Vol. 5 , edited by G. Dutton ( Cambridge , Massachusetts Harvard University Laboratory for Computer Graphics and Spatial Analysis ), pp. 1 – 19 .
   Google Scholar
• MARK , D. M. , 1979 , Phenomenon-based data-structuring and digital terrain modelling . Geo-Processing , 1 , 27 .
   Google Scholar
• MARK , D. M. , 1986 a , Construction of quadtrees and octtrees from raster data A new algorithm based on run-encoding . The Australian Computer Journal , 18 , 115 .
   Google Scholar
• MARK , D. M. , 1986 b , The use of quadtrees in geographic information systems and spatial data handling . Proceedings of Auto-Carto London , Vol. 1 , edited by M. Blakemore ( London AutoCarto ) ( available from the Royal Institution of Chartered Surveyors ), pp. 517 – 526 .
   Google Scholar
• MARK , D. M. , 1987 , Recursive algorithm for determination of proximal (Thiessen) polygons in any metric space . Geographical Analysis , 19 , 264 .
   Web of Science ®Google Scholar
• MARK , D. M. , and ABEL , D. J. , 1985 , Linear quadtrees from vector representations of polygons . I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence , 7 , 344 .
   PubMed Web of Science ®Google Scholar
• MARK , D. M. , and CEBRIAN , J. A. , 1986 , Octtrees A useful data-structure for the processing of topographic and sub-surface data . Proceedings of the 46th Annual Meeting of the ACSM held in Washington, D.C., on 16–21 March 1986 ( Falls Church American Congress on Surveying and Mapping ), pp. 103 – 104 .
   Google Scholar
• MARK , D. M. , and LAUZON , J. P. , 1984 , Linear quadtrees for geographic information systems . Proceedings of the International Symposium on Spatial Data Handling held in Zurich, Switzerland in August 1984 , Vol. 2 , edited by D. F. Marble, K. E. Brassel, D. J. Peuquet and H. Kishimoto ( Zurich Department of Geography, University of Zurich-Irebel ), pp. 412 – 430 .
   Google Scholar
• MARK , D. M. , and LAUZON , J. P. , 1985 a , Approaches for quadtree-based geographic information systems at continental or global scales . Proceedings of the Seventh International Symposium on Computer-Assisted Cartography (Auto-Carto 7) held in Washington, D.C., on 11–14 March 1985 ( Falls Church , Virginia American Society of Photogrammetry and Remote Sensing/American Congress on Surveying and Mapping ), pp. 355 – 364 .
   Google Scholar
• MARK , D. M. , and LAUZON , J. P. , 1985 b , The space efficiency of quadtrees An empirical examination including the effects of two-dimensional run-encoding . Geo-Processing , 2 , 367 .
   Google Scholar
• MARTIN , J. J. , 1982 , Organization of geographical data with quad trees and least squares approximation . Proceedings of the I.E.E.E. Conference on Pattern Recognition and Image Processing held in Las Vegas, Nevada in 1982 ( New York I.E.E.E. ), pp. 458 – 463 .
   Google Scholar
• MATSUYAMA , T. , HAO , L. V. , and NAGAO , M. , 1984 , File organization for geographic information systems based on spatial proximity . Computer Vision, Graphics and Image Processing , 26 , 303 .
   Google Scholar
• MORTON , G. , 1966 , A computer oriented geodetic data base, and a new technique in file sequencing . Unpublished report , IBM Canada Limited .
   Google Scholar
• NOMA , A. A. , and SPENCER , N. S. , 1978 , Development of a DMATC digital terrain data base system . Proceedings of the Digital Terrain Models (DTM) Symposium of the ASP/ACSM held in St Louis, Missouri, on 9–11 May 1978 ( Falls Church American Society for Photogrammetry of the American Congress on Surveying and Mapping ) pp. 493 – 505 .
   Google Scholar
• OLIVER , M. A. , and WISEMAN , N. E. , 1983 , Operations on quadtree-encoded images . The Computer Journal , 26 , 83 .
   Web of Science ®Google Scholar
• PEUCKER , T. K. , and CHRISMAN , N. , 1975 , Cartographic data structures . The American Cartographer , 2 , 55 .
   Google Scholar
• PEUCKER , T. K. , FOWLER , R. F. , LITTLE , J. J. , and MARK , D. M. , 1978 , The triangulated irregular network . Proceedings of the Digital Terrain Models (DTM) Symposium of the ASP/ACSM held in St Louis, Missouri, on 9–11 May 1978 ( Falls Church American Society for Photogrammetry/American Congress on Surveying and Mapping ), pp. 516 – 540 .
   Google Scholar
• PEUQUET , D. , 1982 , Comparative data structures raster versus vector . In Computer Assisted Cartography and Geographic Information Processing Hope and Realism , edited by D. H. Douglas and A. R. Boyle ( Ottawa Canadian Cartographic Association ), pp. 73 – 80 .
   Google Scholar
• PEUQUET , D. J. , 1984 , Data structures for a knowledge-based geographic information system . Proceedings of the International Symposium on Spatial Data Handling held in Zurich, Switzerland in August 1984 , Vol. 2 , edited by D. F. Marble, K. E. Brassel, D. J. Peuquet and H. Kishimoto ( Zurich Department of Geography, University of Zurich-Irchel ), pp. 372 – 391 .
   Google Scholar
• ROSENFELD , A. , and SAMET , H. , 1979 , Tree structures for region representation . Proceedings of the International Symposium on Computer-Assisted Cartography (Auto-Carto 4) held in Reston, Virginia, on 4–8 November 1979 , Vol. 1 ( Falls Church , Virginia American Congress on Surveying and Mapping ), pp. 108 – 118 .
   Google Scholar
• ROSENFELD , A. , SAMET , H. , SHAFFER , C. , and WEBBER , R. E. , 1982 , 1982 , Application of hierarchical data structures to geographical information systems . Technical report Computer Science Center TR-1197 , University of Maryland , College Park , Maryland , U.S.A.
   Google Scholar
• SAMET , H. , 1982 , Hierarchical data structures for representing geographical information . In The Design and Implementation of Computer-based Geographic Information Systems, Proceedings of a Joint U.S./Australia Workshop held in Honolulu, Hawaii, in 1982 , edited by D. Peuquet and J. O'Callaghan ( Williamsvilie , New York IGU Commission on Geographical Data Sensing and Processing ), pp. 36 – 50 .
   Google Scholar
• SAMET , H. , 1984 , The quadtree and related hierarchical data structures . Computing Surveys , 16 , 187 .
   Web of Science ®Google Scholar
• SAMET , H , ROSENFELD , A. , SHAFFER , C. A. , and WEBBER , R. E. , 1984 , Use of hierarchical data structures in geographic information systems . Proceedings of the International Symposium on Spatial Data Handling held in Zurich, Switzerland in August 1984 , Vol. 2 , edited by D. F. Marble, K. E. Brassel, D. J. Peuquet and H. Kishomoto ( Zurich Department of Geography, University of Zurich-Irchel ), pp. 392 – 411 .
   Google Scholar
• SAMET , H. , SCHAFFER , C. A. , NELSON , R. C , HUANG , Y. -G. , FUJIMURA , K. , and ROSENFELD , A. , 1986 , Recent developments in quadtree-based geographic information systems . Proceedings of the Second International Symposium on Spatial Data Handling held in Seattle, Washington in July 1986 ( Williamsville , New York IGU Commission on Geographical Data Sensing and Processing ), pp. 15 – 32 .
   Google Scholar
• SAMET , H. , and TAMMINEN , M. , 1985 , Computing geometric properties of images represented by linear quadtrees . I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence , 7 , 229 .
   PubMed Web of Science ®Google Scholar
• SAMET , H. , and WEBER , R. E. , 1985 , Storing a collection of polygons using quadtrees . ACM Transactions on Graphics , 4 , 182 .
   Web of Science ®Google Scholar
• SMITH , T. R. , MENON , S. , STAR , J. L. , and ESTES , J. E. , 1987 , Requirements and principles for the implementation and construction of large-scale geographic information systems . International Journal of Geographical Information Systems , 1 , 13 .
   Google Scholar
• SWANN , R. , THOMPSON , J. , and DAYKIN , S. E. , 1978 , Application of low cost dense digital terrain models . Proceedings of the Digital Terrain Models (DIM) Symposium of the ASP-ACSM held in St Louis, Missouri, on 9–11 May 1978 ( Falls Church American Society for Photogrammetry/American Congress on Surveying and Mapping ), pp. 141 – 155 .
   Google Scholar
• TOMLINSON , R. F. , CALKINS , H. W. , and MARBLE , D. F. , 1976 , Computer Handling of Geographical Data An Examination of Selected Geographic Information Systems ( Paris UNESCO Press ).
   Google Scholar
• TROPF , H. , and HERZOG , J. , 1981 , Multidimensional range search in dynamically balanced trees . Angewandte Informatik , 2 , 71 .
   Google Scholar
• WEBER , W. , 1979 , Three types of map data structures, their ANDs and NOTs, and a possible OR . Proceedings of the International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems held in Dedham, Massachusetts , Vol. 4 , edited by G. Dutton ( Cambridge , Massachusetts Harvard University Laboratory for Computer Graphics and Spatial Analysis ), pp. 1 – 17 .
   Google Scholar