Geometry in Action

Cartography and Geographic Information Systems

A geographic information system (GIS) is simply a database of information about natural and man-made geographic features such as roads, buildings, mountains... These systems can be used for making maps, but also for analyzing data e.g. for facility location. There has been some communication between the geometry and GIS communities (e.g. geographer Michael Goodchild gave an invited lecture on "Computational Geography" at the 11th ACM Symp. Comp. Geom.) but more could be done to bring them together. Geographic problems already visible in the geometry community include interpolation of surfaces from scattered data, overlaying planar subdivisions, hierarchical representations of terrain information, boundary simplification, lossy compression of elevation data (e.g. by using a piecewise linear approximation with few facets), and map labelling. Other interesting geometric issues include handling of approximate and inconsistent data, matching similar features from different databases, compression of large geographic databases, cooperation between raster and vector representations, visibility analysis, and generation of cartograms (maps with area distorted to represent other information such as population).

A particularly important geometric data structure in geographic analysis is the Voronoi diagram, which has been used for to identify regions of influence of clans and other population centers, model plant and animal competition, piece together satellite photographs, estimate ore reserves, perform marketing analysis, and estimate rainfall.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.