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.
- ACM Int. Worksh. Advances in Geographic Information Systems.
3rd Worksh., Baltimore, Dec. 1995, call for papers.
4th Worksh., Rockville, MD, Nov. 1996,
call for papers.
- The
Agricultural Non-Point Source Pollution Model claims to be using
Voronoi diagrams as a basis for spatial subdivision, but appears to
actually be using quadtrees.
-
Applications of 3d Delaunay triangulation algorithms in geoscientific modeling, R. Lattuada and J. Raper.
Uses 3d DT for shape reconstruction of 3d geographic objects such as aquifers, ocean currents, and weather fronts.
- Applications of computational geometry: virtual reality, 3d graphics, and route planning. Abstract for a talk in which Joe Mitchell describes his ongoing work.
- Automated derivation of high accuracy road centrelines:
Thiessen polygons technique. A. Ladak and R. B. Martinez use
Voronoi diagrams to automatically construct maps of the roads in Qatar
from databases of nearby buildings.
- Cartography
resources on the web, Jeremy Crampton, George Mason U.
-
Case Studies in Biometry. This book by N. Lange and others
mentions Voronoi diagrams as a method for detecting clusters
of disease incidence.
- Centre for Research in Geomatics, U. Laval.
- CMU
Digital Mapping Laboratory.
-
Commun. ACM Theme Section: Geographic Information Systems,
S. Shekhar and M. Egenhofer, eds., call for papers.
- Computational Topology.
Survey paper by Dey, Edelsbrunner, and Guha, presented at the conference
"Computational Geometry -- Ten Years After". Includes descriptions of
applications in image processing, cartography, graphics, solid modeling,
mesh generation, and molecular modeling.
- Data formats for addresses.
James Guthrie discusses the complexities of naming systems in GIS's
and the difficulty of associating names to geographic/geometric entities.
- A
data foundation for the national spatial data infrastructure, US
Natl. Research Council, 1995.
- Dept. Spatial Information Science and Engineering, U. Maine.
- Der
Technik hinter dem Mühlentag (in German).
Kasper Schiess uses Voronoi diagrams to set up web page image maps
of geographical locations
in such a way that clicking on any point in the map leads to a description
of the nearest location.
- The
DoD groundwater modeling system uses
natural neighbor interpolation for groundwater plume characterization.
- Dynamic segmentation and Thiessen polygons: a solution
to the river mile problem.
Hargrove, Winterfield and Levine use Voronoi diagrams to
construct a coordinate system for locations on water or along
other linear structures such as interstate highways.
- External-memory
algorithms with applications in geographic information systems,
L. Arge, Duke.
- Extracting features from remotely sensed images. Mark Dobie and co-workers use minimum spanning trees to find road networks in satellite and aerial imagery.
- William
Franklin of Rensselaer Polytechnic
combines computational geometry and cartography in his research.
- Geophysical
applications of natural neighbors.
A group at ANU Canberra uses Voronoi diagram based interpolation
for a range of geophysical problems.
- GIS and CAD.
John Thomas describes Rochester's experience with the interface
between GIS (for large-scale geographic data) and CAD
(for smaller scale architectural information such
as street layout).
- The
Green Island Formation in Forest Fire Modeling with Voronoi
Diagrams, Roque and Choset, CGC98.
- IGIS '94 (Int. Worksh. Advanced Research in Geographic Information
Systems) table of contents.
- Image tilings.
The PRISME group at INRIA proposes stitching together multiple images of
a scene (e.g. multiple aerial or satellite views of a piece of land)
using a form of Voronoi diagram to choose which image has the best quality
for each piece of scenery.
- Internet
GIS and remote sensing sites, Queen's Univ., Canada.
- Labeling a rectilinear map,
Andy Mirzaian and Binhai Zhu, 5th MSI Worksh. Comp. Geom.
-
Map-Labeling Pages,
Alexander Wolff
- The Paradigm Group
at Carleton U., research into parallel algorithms for geographic
information systems.
- Petroleum reservoir simulation. Santosh Verma of Stanford uses
Voronoi diagrams "to accurately represent horizontal and deviated
wells, local flow geometry, faults, major heterogeneities, etc" in
petroleum reservoir simulation.
- Quasi-conformal maps of the Earth, M. Hurdal.
- Reconstruction of geological data using 3d Voronoi diagrams. From the PRISME project at INRIA.
- Resources for
cartography, GIS, and remote sensing,
U. Wisc. Stevens Point, Dept. of Geography/Geology.
- Settlement
selection for interactive display. How to choose which towns to show
on a map, when the scale is too low to show everything?
M. van Kreveld, R. van Oostrum, and J. Snoeyink describe algorithms
based on incremental maintenance of Voronoi diagrams.
- Spatial
modelling by Delaunay networks. Terje Midtbø explains applications
of Voronoi diagrams to "subjects such as determination of areas covered
by a mobile telephone transmitter, determination of high-water marks in
rivers, determination of noise zones along roads, drawing voltage maps,
and other, more conventional cartographic tasks."
- Topological Data Structures for Surfaces: An Introduction for Geographical Information Science.
Book of GIS papers edited by S. Rana.
- Transforming
contour maps into digital elevation models, Michael Gousie, Wheaton
College.
- TRIM
Watershed Atlas. This project uses medial axes
to approximate the drainage patterns of watersheds.
Warning: 472kb PDF file. See especially appendix D on page 45
of the PDF, describing the algorithms used by this project.
- U.S. BLM archive of
GIS utility software and data.
- Voronoi diagram
of McDonalds outlets in San Francisco.
Demo of a commercial GIS tool.
- Voronoi methods in geomatics.
Abstract of a talk by Chris Gold at Carleton U.
See also
Gold's
many papers on Voronoi-diagram based methods in geographic
information systems.
- R. Waupotitsch has implemented various
optimal
triangulation algorithms as part of the
GRASS
geographic resources analysis support system.
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.
