History of DGGS Development



There are early records of using grid patterns to organize measurements of land parcels, astronomical observations, and cartographic information. Most charting and map projections rely on transforming a grid, on a globe, to a plane. Artillery surveys provide accurate targeting on grid quadrants. Requirements for digitally organizing national maps produced innovation in map tiling and spatial data indexing systems that now drive spatial databases and web maps. At a global level, computational grids developed for fluid flow models supported climate, weather, and ocean current predictions. However, none of these approaches to earth gridding evolved directly into the information-centric Digital Earth reference of a DGGS.
 
Harvard’s Lab for Computer Graphics and Spatial Analysis (LCGSA) was a fertile birthplace of ideas related to digital thematic mapping, spatial analysis and, what is now called, geographic information systems (GIS). Early work at LCGSA set some of the groundwork for using discrete models to characterize geospatial information. From 1967 to 1972, under the direction of William Warntz, LCGSA produced a series of papers on geography and the properties of surfaces that would lay a foundation for digital mapping, including several notable papers examining the properties of mixed hexagon tessellations to represent central places and networks. In 1967, Carl Steinitz, then an associate professor at Harvard’s Graduate School of Design, applied LCGSA-developed computer mapping software, Synteny Mapping and Analysis Program (SYMAP), to an aggregation of various vector maps to facilitate an urban planning study of the Delmarva Peninsula. Steinitz found, while integrating the various vector-based data sources, that gridding the data was more efficient. A new raster-based module of SYMAP, coined GRID, resulted. GRID went on to become IMGRID – the basis of work by another Harvard student, Dana Tomlin, the originator of Map Algebra, whose raster-based analysis software would be integrated into Earth Resources Data Analysis System (ERDAS) Imagine and the US Army Corps of Engineers’ Map Analysis Package (MAP) in Geographic Resources Analysis Support System (GRASS).
 
In 1986, Waldo Tobler and Zi-tan Chen identified an opportunity to create a global grid, the primary purpose of which was information storage. Tobler – of Tobler’s first law of geography: “Everything is related to everything else, but near things are more related than distant things” – argued that, since geographic information systems are primarily for planning, analysis, and inventorying of geographic phenomena, it follows that “coverage must be uniform and that every element of area must have an equal probability of entering the system. This suggests that the world should be partitioned into chunks of equal size” (Tobler and Chen 1986). Tobler suggested an approach with a cube as a base polyhedron and dividing it into rectilinear quadtrees to create successive subdivisions with unlimited resolution. Tobler’s paper referenced Geoffrey Dutton, a software researcher working at LCGSA, at Harvard Graduate School of Design, who had done similar work, first using squares, then triangles. 

Geoffrey Dutton came to Harvard for a master’s degree in urban planning in 1966 and worked as a research assistant at LCGSA until 1989. Dutton focused much of his attention on raster-based data structures and three-dimensional (3-D) terrain visualization. Using a time series of 2.5-D gridded surfaces, he created the first animated holographic map. In 1984, Dutton published his work on assembling and managing global terrain data on a triangular global grid. His global geodesic elevation model (GEM) started with a cuboctahedron connected into a rhombic dodecahedron and recursively divided the initial 12 triangular faces into refinements of nine partially nested equilateral triangles. Elevations were assigned to the faces of each successive triangle. Dutton’s paper did more than lay out the mathematics for a global grid, it emphasized why he felt such an effort was necessary: “we live on one planet, a world which may be regarded as an organic entity. The wholeness of the Earth – self-evident to many non-western cultures – largely escapes the western culture of science, even the so-called earth sciences. This peculiar myopia is reflected both by our disciplinary specialization and by territorial concerns.” Dutton believed assembling relevant data in a holistic, globally useful framework could act as a unifying model: “[it is] only through using technology that we have any hope of comprehending the nature of the problems we have wrought for the planet” (Dutton 1984). 

A few years later, Dutton modified the GEM model to a simpler structure called quaternary triangular mesh (QTM). QTM was based on an octahedron embedded in the earth with a vertex at each pole and four vertices at the equator. 

In 1975, Denis White, who had been a computer scientist at the Massachusetts Institute of Technology, joined LCGSA at Harvard to co-design and develop the vector-based GIS, Odyssey. During that time, White learned of Michael Woldenberg’s work on mixed hexagonal hierarchies and collaborated with Geoffrey Dutton. White was familiar with Dutton’s vision for a global data structure when he left Harvard to work at the US Environmental Protection Agency’s (EPA) ecological research lab in Corvallis, Oregon. 

A cluster of research offices in Corvallis, Oregon, which included the University of Oregon, US-EPA, and US Department of Agriculture- Forestry Service, fermented and fostered the next concerted development to formalize global grids into a system. The basic idea was driven by a need to develop an integrated approach to monitoring aquatic and terrestrial resources in the United States, the objective of the EPA’s new Environmental Monitoring and Assessment Program (EMAP). The concept of using an area frame as the basis for a survey design was proposed by Scott Overton, a statistical ecologist at the University of Oregon. Statistically valid sampling was a very important criterion for EPA. White, working with Overton, proposed that EMAP use a global system of hexagonal cells. They shared their plans with Jon Kimerling, a professor of geography at Oregon State University who had extensive experience with map projections. Kimerling suggested a global grid that started with a truncated icosahedron (White, Kimerling, and Overton 1992).
 
By June 1989 the three convened a meeting in Corvallis to discuss the geometry of sampling designs for EMAP and included Tobler, Dutton, Hrvoje Lukatela, a Canadian scientist who had developed a global model using Voronoi areas, and Tony Olsen, a statistician at the Pacific Northwest Laboratory. Design criteria for a DGGS began its formalization. Michael Goodchild, of the National Center for Geographic Information and Analysis (NCGIA) and University of California, Santa Barbara, had met Dutton when he presented QTM at an NCGIA specialist meeting on spatial accuracy at Montecito in 1988. Goodchild could not attend the Corvallis meeting, sending instead a paper authored with his student Yang Shiren that suggested modification to Dutton’s QTM labeling. Dutton would later collaborate with Shiren to show, as is often the case with DGGS indexing methods, that their respective models were isomorphic, permitting mappings between the two numbering systems. The choices of three regular tilings for a global grid – quadrilateral, triangular, and hexagonal cells – were represented at the 1989 Corvallis meeting with the challenges for a further decade of global grid research established.

In March 2000, the pioneers of DGGS convened at the 1st International Conference on DGGS in Santa Barbara. Notable additions to the main group included Tony Olsen, Kevin Sahr, and Dan Carr.  Tony Olsen came to the EPA in 1990 to lead the statistical design of EMAP. Dan Carr, a statistician from George Mason University, had developed innovative data binning techniques using hexagons and contributed to the cartography of hexagonally partitioned data. White and Olsen worked closely on implementations of the original EMAP grid system, but after several years the disadvantages of the truncated icosahedron hexagonal grid encouraged further research and development. The importance of an equal area cell had become apparent, so Kimerling turned to John P. Snyder, the clever, self-taught geodesist and author of the definitive text on map projections, for a method of projecting equal area cells from the face of a polyhedron to a sphere (Snyder 1992). Subsequent work at the EPA and Oregon State then focused on the icosahedron as the preferred solid model upon which to develop global grids. 

Funding was made available to add a computer scientist to compile and test the ideas that were being generated for a truly global equal-area statistically valid sampling grid. Kevin Sahr had completed his master’s degree in computer science from the University of Colorado in 1995. Sahr was an admirer of Buckminster Fuller, his Dymaxion technology, and his global vision of “Spaceship Earth.” Kevin had picked up on the military use of hexagonal tessellations while serving in the Reserve Officers’ Training Corps in Army intelligence and was a keen champion of a hexagon earth. Sahr coined the term “discrete global grid” and would become a passionate advocate and technical expert on DGGS. “The term ‘discrete global grid’ was proposed by Sahr to identify the types of global partitioning systems based on continuous coverages of polygons. It was first used in print in a draft technical report from the OSU Geosciences Department Terra Cognita Laboratory, where the EPA funded projects on biodiversity and global grids were located. Kevin wrote the report, dated 30 May 1996, entitled ‘Terra Cognita Technical Report 96001: Discrete Global Grid.’ In September 1996, Sahr and others wrote a description of 14 desirable properties of discrete global grid that were proposed by Michael Goodchild in the 1994 meeting in Santa Barbara” (White 2014). 

In 1988, the US National Science Foundation established the National Center for Geographic Information and Analysis to conduct basic research to advance geographical information systems. Many technical impediments existed. The geographer Michael Goodchild, serving as one of the NCGIA’s founding co-directors, produced a prolific series of papers, reports, and vision documents that earned him the reputation as the pre-eminent thought leader within geographical information science. In 1994, Goodchild had constructed a list of criteria describing a global grid.
 
The EPA research team at Corvallis had advanced significantly by the 1st International Conference on DGGS in 2000. At Oregon State University, Kimerling had received the Milton Harris award in 1996 for his exceptional achievement in basic research on developing global grids. A number of research areas had been explored and the preferred solution was identified as the ISEA3H grid (Sahr and White 1998). Dutton had advanced QTM and completed a doctoral degree at the University of Zürich with a dissertation thesis on the subject (Dutton 1999). Goodchild’s research into DGGS systems followed Dutton’s QTM approach; however, his interest aimed at a more generalized and lofty utility than Dutton’s original objective of global terrain modeling. Goodchild could envision an Internet subsystem for organizing and aligning all geospatial information which was sufficiently simple that a child could use it to explore the earth. His vision was articulated in a 1998 speech, "The Digital Earth", written with substantial input from Goodchild, that was to be delivered by Vice-President Al Gore (Gore 1998). For Goodchild, The Digital Earth provided the actionable requirements needed to respond to Al Gore’s vision of a digital replica of earth proposed in his 1992 book Earth in the Balance (Gore 1992). Goodchild articulated the connection between DGGS and Digital Earth at the 1st International Conference on DGGS: “[Digital Earth] can clearly benefit from developments in discrete global grid, which can provide the georeferencing, the indexing, and the discretization needed for geospatial data sets. They have properties, in particular hierarchical structure, uniqueness, explicit representation of spatial resolution, and consistency, that make them superior to any single alternative” (Goodchild 2000). 

Keith Clarke, a geographer at the University of California, Santa Barbara, prepared and presented at the conference a comparison of criteria for assessing a DGGS (see Table 1). 

Table 1: Criteria for DGGS characteristics have been proposed by both Goodchild and Kimerling, (Keith Clarke 2000).


DGGS Criteria in Goodchild (Goodchild, 1994)

G1.      Each area contains one point

G2.      Areas are equal in size

G3.      Areas exhaustively cover the domain

G4.      Areas are equal in shape

G5.      Points form a hierarchy preserving some (undefined) property for m < n points

G6.      Areas form a hierarchy preserving some (undefined) property for m < n areas

G7.      The domain is the globe (sphere, spheroid)

G8.      Edges of areas are straight on some projection

G9.      Areas have the same number of edges

G10.   Areas are compact

G11.   Points are maximally central within areas

G12.   Points are equidistant

G13.   Edges are areas of equal length

G14.   Addresses of points and areas are regular and reflect other properties

DGGS Criteria in Kimerling. (Kimerling, Sahr, White, & Song, 1999)  Goodchild's Numbers given in parentheses

K1.      Areal cells constitute a complete tiling of the globe, exhaustively covering the globe without overlapping. (G3,G7)

K2.      Areal cells have equal areas. This minimizes the confounding effects of area variation in analysis, and provides equal probabilities for sampling designs. (G2)

K3.      Areal cells have the same topology (same number of edges and vertices). (G9, G14)

K4.      Areal cells have the same shape. Ideally a regular spherical polygon with edges that are great circles. (G4)

K5.      Areal cells are compact. (G10)

K6.      Edges of cells are straight in a projection. (G8)

K7.      The midpoint of an arc connecting two adjacent cells coincides with the midpoint of the edge between the two cells.

K8.      The points and areal cells of the various resolution grids which constitute the grid system form a hierarchy which displays a high degree of regularity. (G5,G6)

K9.      A single areal cell contains only one grid reference point.(G1)

K10.   Grid reference points are maximally central within areal cells. (G11)

K11.   Grid reference points are equidistant from their neighbors. (G12)

K12.   Grid reference points and areal cells display regularities and other properties which allow them to be addressed in an efficient manner.

K13.   The grid system has a simple relationship to latitude and longitude.

K14.   The grid system contains grids of any arbitrary defined spatial resolution. (G5,G6)

 References

Clarke, K. C., 2000, "Criteria and Measures for the Comparison of Global Geocoding Systems", International Conference on Discrete Global Grids. Santa Barbara: University of California, Santa Barbara. http://escholarship.org/uc/item/9492q6sm (accessed April 27, 2016).

Dutton, G. 1984. “Geodesic Modelling of Planetary Relief.” Cartographica, 21(2–3): 188–207.

Dutton, G. 1999. A Hierarchical Coordinate System for Geoprocessing and Cartography. Lecture Notes in Earth Sciences 79. Berlin: Springer-Verlag.

Goodchild, M.F. 2000. “Discrete Global Grids for Digital Earth.” International Conference on Discrete Global Grids, Santa Barbara, CA. http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10.1.1.83.9660 (accessed April 27, 2016).

Gore, A. 1992. Earth in the Balance: Ecology and the Human Spirit. New York: Houghton Mifflin.

Gore, A. 1998. “The Digital Earth: Understanding our Planet in the 21st Century.” Australian Surveyor, 43(2): 89–91.

Kimerling, A.J., K. Sahr, D. White, and L. Song. 1999. “Comparing Geometrical Properties of Global Grids.” Cartography and Geographic Information Systems, 26(4): 271–288.

Mahdavi-Amiri, A., F. Samavati, and P. Peterson. 2015. “Categorization and Conversions for Indexing Methods of Discrete Global Grid Systems.” ISPRS International Journal of Geo-Information, 4(1): 320–336.

Sahr, K., and D. White. 1998. “Discrete Global Grid Systems.” In Computing Science and Statistics, Vol. 30, Proceedings of the 30th Symposium on the Interface, Computing Science and Statistics, edited by S. Weisberg, 269–278. Fairfax Station, VA: Interface Foundation.

Sahr, K., D. White, and A. Kimerling. 2003. “Geodesic Discrete Global Grid Systems.” Cartography and Geographic Information Science, 30(2): 121–134.

Snyder, J.P. 1992. “An Equal-Area Map Projection For Polyhedral Globes.” Cartographica: The International Journal for Geographic Information and Geovisualization, 29(10: 10–21.

Tobler, W., and Z.-t. Chen. 1986. “A Quadtree for Global Information Storage.” Geographical Analysis, 18(4): 360–371.

White, D. 2014, April 20. A personal history of discrete global grids (interviewer P. Peterson).

White, D., J. Kimerling, and W.S. Overton. 1992. “Cartographic and Geometric Components of a Global Sampling Design for Environmental Monitoring.” Cartography and Geographic Information Systems, 19(1): 5–22.



Comments