Problems with handling spatial data — the voronoi approach

Abstract

Experience with the handling of spatial data on a computer led to the identification of a variety of “awkward” problems, including interpolation, error estimation and dynamic polygon building and editing. Many of the problems encountered could be classified as “spatial adjacency” issues. The Voronoi diagram of points and line segments in the Euclidean plane is shown to give a functional definition of spatial adjacency. The basic operations for incremental construction and maintenance of this Voronoi diagram and its dual are described, and a variety of applications are outlined.