Honors 2005: Jon and Tom
Below is a list of the projects that I have worked on with Bowdoin students which resulted in publications and presentations.

We consider the problem of building a
quadtree subdivision for a set of edges in the place. Our
approach is to first build a quadtree on the vertices
corresponding to the endpoints of the edges, and then compute
the intersections between the edges and the cells in the
subdivision. We introduce the Kquadtree: for any
k>=1, a kquadtree is a linear compressed quadtree that
has O(n/k) cells with O(k) points each. We
show how to build a kquadtree cacheefficienctly. As an
application, we consider one of the basic problems in spatial
data structures, map overlay, and implement it via
kquadtrees. We report experimental results.
Papers and presentations:


We describe an algorithm to compute the
viewshed with linear interpolation and without using any
approximation. The algorithm is based on computing and merging
horizons, and in practice it is faster than our previous
viewshed algorithms, while being more accurate. We prove that
the complexity of horizons on a grid of n points is O(n),
improving on the general O(n \alpha (n)) bound on triangulated
terrains.
Papers and presentations:


We describe the design and
engineering of three new algorithms for computing viewsheds on
massive grid terrains. The first two algorithms sweep the
terrain by rotating a ray around the viewpoint, while
maintaining the terrain profile along the ray. The third
algorithm sweeps the terrain centrifugally, growing a
starshaped region around the viewpoint, while maintaining the
approximate visible horizon of the terrain within the swept
region. On a terrain of n grid points, these
algorithms run in O(sort(n)) I/O's in the I/Omodel if
Agarwal and Vitter. This algorithm runs in O(n) time and
O(scan(n)) I/O's and is cacheoblivious.
Papers and presentations:


Given a terrain T and a point v, the
viewshed of v is the set of points in T that are visible from
v. We consider the problem of computing the viewshed of a
point on a very large grid terrain in external memory. We
describe an algorithm for this problem in the cacheaware and
cacheoblivious models, together with an implementation and an
experimental evaluation. Our algorithm is based on Van
Kreveld's O(n lg n) algorithm for this problem in internal
memory and uses O(sort(n)) I/Os, where sort(n) is the
complexity of sorting n items of data in the I/Omodel of
Agarwal and Vitter.
r.viewshed: We ported the algorithm to GRASS, where it was adopted as one of their core modules and extended to use linear interpolation by their developer group. Papers and presentations:

Terracost is a module for computing leastcostpath surfaces on massive grid terrains and is motivated by cost analysis in GIS. In algorithmic terms, it corresponds to the problem of computing multisource shortest paths (MSSP). Compared to singlesource SP, MSSP has poorer spatial locality as the number of sources increase. Specifically when the grids do not fit in memory, the standard inmemory algorithm starts to thrash. Our algorithm is I/Oefficient and scales to terrains that are much larger than main memory. It is based on a technique to compute shortest paths in planar graphs: the idea is to partition the graph in subgraphs such that they have small boundaries and replace each subgraph by a complete graph on its boundary vertices. The resulting graph is not larger than the initial one; preserves shortest paths; and, it can be accessed I/Oefficiently. This technique can be used for planar graphs in general as a tool to speed up shortestpath computation. We implemented this idea for grids in a module called r.terracost; it is implemented for GRASS and, using our cluster management tool, in a distributed environment. Terracost outperforms standard solutions as dataset size increases relative to available memory and our distributed solver obtains nearlinear speedup when preprocessing large terrains for multiple source queries. Papers and presentations:
A tarball of the code is available here: r.terracost1.1 (works with GRASS 6.x)  r.terracost1.0 (works with GRASS 5.3). 
While most data in GIS is represented in grid form, TINs (triangular irregular networks) have the potential of being more space efficient than grids, especially for very large terrains. In this project we took a first step at simplifying a grid terrain into a TIN within a specified error threshold using an approach that scales to terrains that are arbitrarily larger than main memory. Our module, r.refine can work standalone or as an addon in GRASS open source GIS. Papers and presentations:
