Scalable Algorithms for Realistic Terrain Processing in GIS

Bowdoin College, Brunswick ME

Investigators

Abstract

The research goal of this project is to develop scalable algorithms for a number of fundamental problems in terrain processing and implement these algorithms into open-source modules used by the GIS (Geographic Information Systems) community. The research will address three problems on terrains: the computation of visibility, overlay, and simplification. These problems come up in some of the most basic terrain processing applications, and have received a lot of attention both in theory and in practice. However, solutions that are both optimally I/O-efficient and practically scalable are not known. The central theme of the research is to develop algorithms that are simple and optimal and also perform well in practice and scale to very large inputs by exploiting the geometry of realistic terrains. So far, theoretical research into scalable algorithms has focused on algorithms that are I/O-efficient for any worst-case input. However, worst-case inputs are often artificial constructions that occur rarely in real-life. The research will use the notion of realistic input developed in computational geometry, thus combining the theory of I/O-efficient algorithms with realistic input models as a new approach to obtain optimal, practical and realistic I/O-efficient algorithms.