My research is focused onthe theory and practice of cache-efficient algorithms for large data, and in particular applications that involve large, high-resolution data in Geographic Information Systems (GIS). We explore algorithms for fundamental problems on terrains such as visibility, flooding, sea level rise and least-cost-path surfaces. Our goal is to come up with approaches that are resource-efficient (CPU, IO, cache, parallel), are backed by algorithms that we can theoretically prove efficient, and at the same time work well in practice. Ultimately our goal is to transfer these algorithms into free and open-source software.
On External-Memory MST, SSSP and Multi-way Planar Graph Separation. Lars Arge, Gerth Brodal and Laura Toma. In Journal of Algorithms, 53(2):186-206, November 2004.
Flow Computation on Massive Grid Terrains. Lars Arge, Jeff Chase, Patrick Halpin, Laura Toma, Dean Urban, Jeffrey S. Vitter, and Rajiv Wickremesinghe. In GeoInformatica, International Journal on Advances of Computer Science for Geographic Information Systems, 7(4):283-313, December 2003.
I/O-Efficient Algorithms for Problems on Grid-based Terrains. Lars Arge, Laura Toma and Jeffrey S. Vitter. In Proceedings of the Second Workshop on Algorithm Engineering and Experimentation (ALENEX 2000). [ abstract | pdf ]