Voronoi Methods in GIS

Chris Gold

EU Marie-Curie Chair in GIS
University of Glamorgan
Tuesday 10th April 2007; 2pm-6pm

Workshop Fee: None.
Supported by the EU Marie-Curie.

Workshop Abstract

In GIS data is often classified as of either "field" or "object" types. Field data implies spatial continuity whereas objects are unconnected entities, such as houses. Field data again may be classified as having discrete or continuous attributes - for example land use classification vs. temperature. Traditionally tessellations are used for discrete attribute fields, and not for objects. Point observations of fields may be interpolated over the whole space and either be classified and treated as discrete, or else modelled as surfaces - as in triangulated terrain models. While usually considered in 2D geographic space, the same principles apply in 3D.

A second use for tessellations is as co-ordinate indexing schemes - sometimes hierarchical, sometimes not. The spatial partitions are used as pigeon-holes to store pointers to objects having 2D or 3D coordinates.

However, recent re-examination of tessellations suggests that they are valuable for object-type data as well - if they are based on an adaptive tessellation such as the Voronoi diagram, rather than a spatial partitioning like the quad-tree. The most obvious example is Sibson (natural neighbour) interpolation, where inserting a Voronoi cell steals areas of the neighbouring cells, which are used for weighted averages. Following from this is the idea that cell adjacency relationships describe the relative positions of the generator objects (a local coordinate system). Thus the static, dynamic or kinetic Voronoi diagram may be used for navigation, map construction and updating, as well as simulating fluid flow, etc. It should be remembered that one of the original, and ongoing, concerns of GIS is the valid construction of connected graphs (polygons, rivers etc.) from approximate co-ordinate data.

Finally, while the Voronoi and Delaunay duality is well known, there are many applications where both of these structures are needed simultaneously - for example in crust and skeleton construction and catchment area modelling. Data structures in 2D or 3D that preserve these relationships, and associated attributes, are becoming more interesting.