Location: Bowdoin / Laura I. Toma

Computer Science

Laura I. Toma

Associate Professor of Computer Science; Chair of Computer Science Department

Contact Information

Computer Science

Searles Science Building - 219

Teaching this semester

CSCI 2200. Algorithms

An introductory course on the design and analysis of algorithms. Introduces a number of basic algorithms for a variety of problems such as searching, sorting, selection, and graph problems (e.g., spanning trees and shortest paths). Discusses analysis techniques, such as recurrences and amortization, as well as algorithm design paradigms such as divide-and-conquer, dynamic programming, and greedy algorithms.

CSCI 3225. GIS Algorithms and Data Structures

Geographic information systems (GIS) handle geographical data such as boundaries of countries; course of rivers; height of mountains; and location of cities, roads, railways, and power lines. GIS can help determine the closest public hospital, find areas susceptible to flooding or erosion, track the position of a car on a map, or find the shortest route from one location to another. Because GIS deal with large datasets, making it important to process data efficiently, they provide a rich source of problems in computer science. Topics covered include data representation, triangulation, range searching, point location, map overlay, meshes and quadtrees, terrain simplification, and visualization.

laura toma


  • Ph.D 2003 Duke University
  • MS 2001 Duke University
  • MS 1997 University Politehnica Bucharest, Romania
  • BS 1996 University Politehnica Bucharest, Romania


I am interested in I/O-efficient algorithms and data structures, in particular in I/O-efficient graph algorithms and applications to Geographic Information Systems (GIS).

A significant part of my work has been motivated by scalability issues in Geographic Information Systems (GIS). I am interested in developing new methods and algorithms for representing, modeling, and analyzing massive terrain data in GIS. I am interested in algorithms that are not only of theoretical interest, but perform well in practice and scale to very large inputs, using techniques from I/O-efficient algorithms and cluster computing.


  • r.refine
    A module for simplifying grid terrains and converting grids to TINs (triangular irregular networks) within a specified error threshold. Uses a tiled approach that makes it efficient for very large terrains. With Jonathan Todd '05.
  • Terracost
    Terracost is a versatile and scalable approach for computing least-cost-path surfaces on massive grid-based terrains. It is implemented in the context of the GRASS open source GIS system (as r.terracost) 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 near-linear speedup when preprocessing large terrains for multiple queries. With Thomas Hazel '05.
  • TerraFlow | r.terraflow | TerraFlow Extension for ArcGIS 8.x
    TerraFlow is a package for I/O-efficient computation of flow-related indices on massive grid terrains. It includes primitives for flow routing, flooding and flow accumulation. TerraFlow is the first terrain flow software designed and optimized for massive data. On large terrains TerraFlow significantly outperforms existing systems and is capable of solving problems of a scope and scale impractical with previous systems. Terraflow was originally developed with TPIE and later ported to GRASS as r.terraflow, and to Windows and ArcGIS.

    TerraFlow talks/posters: GRASS'02 | ACMGIS'01 | IALE'01 | IPP'00 | ALENEX'00

Journal Articles

Articles in refereed conference proceedings

  • Terracost: A Versatile and Scalable Approach to Computing Least-Cost-Path Surfaces for Massive Grid-Based Terrains. Thomas Hazel, Laura Toma, Jan Vahrenhold and Rajiv Wickremesinghe. In Proceedings of the 21st Annual ACM Symposium on Applied Computing (SAC 2006), 2006. ACM 2006. © ACM. (to appear)
  • External Data Structures for Shortest Path Queries on Planar Digraphs. Lars Arge and Laura Toma. In X. Deng and D. Du, editors, Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), volume 3827 of Lecture Notes in Computer Science, pages 328-338. Springer, Berlin, December 2005. © Springer-Verlag. [ abstract | pdf ] (to appear)
  • External Memory Algorithms for Diameter and All-Pairs Shortest Paths on Sparse Graphs. Lars Arge, Ulrich Meyer and Laura Toma. In Josep Diaz, Juhani Karhumaki, Arto Lepisto, Donald Sannella, editors: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), volume 3142 of Lecture Notes in Computer Science, pages 146-157. Springer, Berlin, July 2004. © Springer-Verlag. [ abstract | pdf ]
  • Simplified I/O-Efficient Algorithms for Planar DAGs. Lars Arge, Laura Toma. In Torben Hagerup, Jyrki Katajainen, editors, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004), volume 3111 of Lecture Notes in Computer Science, pages 493-503. Springer, Berlin, July 2004. © Springer-Verlag. [ abstract | pdf ]
  • I/O-Efficient Algorithms for Planar Digraphs. Lars Arge, Laura Toma and Norbert Zeh. In Proceedings of the Fifteenth annual ACM Symposium on Parallel Algorithms in Algorithms and Architectures (SPAA 2003), pages 85-93, 2003. ACM 2003. © ACM. [ abstract | pdf ]
  • Flow Computation on Massive Grids. Laura Toma, Rajiv Wickremesinghe, Lars Arge, Jeff Chase, Jeffrey S. Vitter, Patrick Halpin, and Dean Urban. In Walid Aref, editor, Proceedings of the Ninth ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2001), pages 82-87, 2001. ACM 2001. © ACM. [ abstract | pdf ]
  • On External-Memory Planar Depth First Search. Lars Arge, Ulrich Meyer, Laura Toma and Norbert Zeh. In F. Dehne, J.R. Sack, R. Tamassia, editors, Proceedings of the Seventh International Workshop on Algorithms and Data Structures (WADS 2001), volume 2125 of Lecture Notes in Computer Science, pages 471-482. Springer, Berlin, July 2001. © Springer-Verlag. [ abstract | pdf ]
  • On External-Memory MST, SSSP and Multi-way Planar Graph Separation. Lars Arge, Gerth Brodal and Laura Toma. In M.M. Halldorsson, editor, Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory (SWAT 2000), volume 1851 of Lecture Notes in Computer Science, pages 433-447. Springer, Berlin, July 2000. © Springer-Verlag. [ abstract | pdf ]
  • 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 ]

Book Chapters