Computer Science

Colloquium Details

A Preliminary Comparison of Proposed Topologies for Geodesic Discrete Global Grid Systems

Abstract

A number of the most challenging computer science applications today, including global climate modeling, environmental monitoring and assessment, transportation planning, and military simulation, share a common spatial substrate, the surface of the earth. Advances in computing hardware, geographic information systems (GIS) software, and in collection-related technologies such as satellites and GPS receivers have facilitated the availability of global spatial data sets of increasingly fine granularity. The difficulties associated with global scale analysis, simulation, and visualization have led researchers in a number of fields to propose alternatives to traditional geospatial data structures and spatial indexes.

Multi-resolution regular partitions of the platonic solids have been proposed as an alternative to traditional floating point coordinates for encoding geospatial location. Proposed topologies have included grids based on triangles, hexagons, and diamonds. In this paper we will give a formal model for this new class of spatial data structures, which we have dubbed "Geodesic Discrete Global Grid Systems." We then describe the implementation of that model to create a software testbed for evaluating the performance of these systems, and discuss preliminary results of performance comparisons.