Andrew Danner

Welcome

I'm an assistant professor in computer science at Swarthmore College. I am interested in researching ways to process very large geometric data sets that often arise in geographic information systems (GIS). I am originally from Southwestern Pennsylvania, so I say "pop", not "soda".

Current Courses

CS 41 Algorithms
CS 41 Lab
CS 21 Introduction to Computer Science
CS 21 Lab

Previous Courses

Courses marked with +L include a separate lab section

CS 21 Introduction to Computer Science | F12+L | F09+L | S09 | F08 | F07 | S07
CS 35 Data Structures and Algorithms | S11+L | F10+L | S10+L | S08 | F07
CS 40 Computer Graphics | S13+L | S11+L | S09
CS 41 Algorithms | F12+L | F08 | F06
CS 46 Theory of Computation | S10+L | S07
CS 97 Senior Conference | S08 | F06

Research Summary

My current research interests are in I/O-efficient algorithms (also called out-of-core or external-memory algorithms). On data sets larger than the amount of available internal memory of a computer, the transfer of data between slow hard disks and faster internal memory, not CPU speed, limits computing performance. Working in a theoretical model that mimics this behavior, I am interested in finding efficient ways to solve problems in computational geometry on large data sets. I also look at possible applications in geographic information systems (GIS). The STREAM project page summarizes some recent contributions by my research group to hi-resolution elevation data analysis and modeling. While my emphasis is on theory, I prefer to develop solutions that are practical enough to implement and be applied. One example of a practical project that I work on is TPIE—a templated, portable I/O environment written in C++ that makes it easier for people to develop I/O-efficient applications. I also contribute to the open source GIS community through the GRASS project.

Publications

R. Carlson and A. Danner. Bridge detection in grid terrains and improved drainage enforcement. In Proc. ACM Symposium on Advances in Geographic Information Systems, pages 250—260, 2010. [bib | pdf ]

A. Danner, T. Mølhave, K. Yi, P. K. Agarwal, L. Arge, and H. Mitasova. TerraStream: From Elevation Data to Watershed Hierarchies. In Proc. ACM Symposium on Advances in Geographic Information Systems, pages 212—219, 2007. [bib | pdf ]

P. K. Agarwal, L. Arge, and A. Danner. From point cloud to grid DEM: A scalable approach. In Andreas Riedl, Wolfgang Kainz, and Gregory Elmes, editors, Progress in Spatial Data Handling. 12th International Symposium on Spatial Data Handling, pages 771—788. Springer-Verlag, 2006. [ bib | pdf ]

L. Arge, A. Danner, H. Haverkort, and N. Zeh. I/O-efficient hierarchical watershed decomposition of grid terrain models. In Andreas Riedl, Wolfgang Kainz, and Gregory Elmes, editors, Progress in Spatial Data Handling. 12th International Symposium on Spatial Data Handling, pages 825—844. Springer-Verlag, 2006. [ bib | pdf ]

A. Danner. I/O Efficient Algorithms and Applications in Geographic Information Systems PhD thesis, Department of Computer Science, Duke University, 2006. [bib | pdf | pdf2 | color_pdf | color_pdf2 ]

L. Arge, A. Danner, H. Haverkort, and N. Zeh. Computing Pfafstetter labellings I/O-efficiently. In Münster University, Dept. of Computer Science, technical report 02/05-I, 2005. [ bib | pdf ]

L. Arge, A. Danner, and S. Teh. I/O-efficient point location using persistent B-trees. The ACM Journal of Experimental Algorithmics, 8, 2003. [ bib | pdf ]

P. K. Agarwal, L. Arge, A. Danner, and B. Holland-Minkley. Cache-oblivious data structures for orthogonal range searching. In Proc. ACM Symposium on Computational Geometry, pages 237—245, 2003. [ bib | pdf ]

L. Arge, A. Danner, and S. Teh. I/O-efficient point location using persistent B-trees. In Proc. Workshop on Algorithm Engineering and Experimentation, 2003. [ bib | pdf ]

Education

Ph.D. Duke University computer science (2006)
committee: Pankaj Agarwal, Lars Arge, Helena Mitasova, and Herbert Edelsbrunner

B.S. Gettysburg College physics and mathematics (1999)