| The main objectives in computational geometry are algorithm design for geometric problems, and analyzing how efficiently geometric problems can be solved. The efficiency analysis is mathematical and based on the worst possible input, because then the efficiency bound holds for all possible inputs. In practice, however, geometric algorithms often perform much better than this type of analysis predicts, because worst-case input is often hypothetical. Therefore, so-called realistic input models were introduced in computational geometry: assumptions about geometric properties of the input that reflect properties of the data in real-world settings. The realistic input models proposed in the literature usually concern the shape of individual objects, or their spatial distribution. These models work well for geometric data-structure design and in applications like robotics, but they do not seem well-suited to explain the efficiency of geometric problems defined on certain GIS data representations, in particular, polyhedral terrains and trajectories. Polyhedral terrains represent e.g. elevation, depth to ground-water, or annual precipitation, and trajectories represent e.g. human, animal or vehicle motion, or hurricane paths. The goal of our project is to perform a fundamental study of realistic input models for these two types of geographic data, in order to obtain provably more efficient algorithmic results: we want to develop new realistic input models for such data, experimentally verify the validity of the models on real-world data, and develop and mathematically analyze algorithms for a number of important algorithmic GIS problems under these realistic assumptions. |
