Geometric algorithms for geographic information systems

Abstract

A geographic information system (GIS) is a software package for storing geographic data and performing complex operations on the data. Examples are the reporting of all land parcels that will be flooded when a certain river rises above some level, or analyzing the costs, benefits, and risks involved with the development of industrial activities at some place. A substantial part of all activities performed by a GIS involves computing with the geometry of the data, such as location, shape, proximity, and spatial distribution. The amount of data stored in a GIS is usually very large, and it calls for efficient methods to store, manipulate, analyze, and display such amounts of data. This makes the field of GIS an interesting source of problems to work on for computational geometers. In chapters 2-5 of this thesis we give new geometric algorithms to solve four selected GIS problems.These chapters are preceded by an introduction that provides the necessary background, overview, and definitions to appreciate the following chapters. The four problems that we study in chapters 2-5 are the following:

Subdivision traversal: we give a new method to traverse planar subdivisions without using mark bits or a stack. Contour trees and seed sets: we give a new algorithm for generating a contour tree for d-dimensional meshes, and use it to determine a seed set of minimum size that can be used for isosurface generation. This is the first algorithm that guarantees a seed set of minimum size. Its running time is quadratic in the input size, which is not fast enough for many practical situations. Therefore, we also give a faster algorithm that gives small (although not minimal) seed sets. Settlement selection: we give a number of new models for the settlement selection problem. When settlements, such as cities, have to be displayed on a map, displaying all of them may clutter the map, depending on the map scale. Choices have to be made which settlements are selected, and which ones are omitted. Compared to existing selection methods, our methods have a number of favorable properties. Facility location: we give the first algorithm for computing the furthest-site Voronoi diagram on a polyhedral terrain, and show that its running time is near-optimal. We use the furthest-site Voronoi diagram to solve the facility location problem: the determination of the point on the terrain that minimizes the maximal distance to a given set of sites on the terrain.