Anne Driemel

Since October 2009, I am a PhD student in the Multimedia and Geometry group of the Department of Information and Computing Sciences at Utrecht University. My supervisors are Marc van Kreveld (Utrecht University) and Mark de Berg (TU Eindhoven). I did my Master's studies in Computer Science at the Free University of Berlin with a focus on Computational Geometry. There, my Master's thesis Multiscale Curvature Matching for Smooth Polylines was supervised by Helmut Alt.

Research interests

Computational Geometry for Geographic Information Systems and Science (GIS)

I work on the design and analysis of geometric algorithms and data structures with geographic applications and by using realistic input models. The worst-case analysis of the running time and space complexities as a function of the input size is a fundamental method in algorithm design. However, it can turn out to be too pessimistic when the worst case is a contrived geometric configuration. Therefore, it can be revealing to do this analysis also with respect to parameters that describe how ''unrealistic'' the input is. Typically, these parameters constrain shape or distribution in space. Using this technique, one can sometimes explain an observed discrepancy between actual and theoretical running times and reveal inherent properties of realistic input that make the problem computationally easy or hard. More importantly, this give rise to new algorithms that are more efficient by exploiting the observed properties. Using realistic input models, we designed a near-linear time algorithm for approximating the Frechet distance, which had been a longstanding open problem, see below.

Conference and Workshop Publications (peer-reviewed)

• Anne Driemel, Sariel Har-Peled, and Carola Wenk:
  Approximating the Frechet Distance for Realistic Curves in Near Linear Time,
  26th Symposium on Computational Geometry (SoCG), 2010. [arXiv]

• Maike Buchin, Anne Driemel, Marc van Kreveld, and Vera Sacristan:
  An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria,
  18th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS), 2010. [PDF]

• Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk:
  Approximate Map Matching with respect to the Frechet Distance,
  Workshop on Algorithm Engineering and Experiments (ALENEX11), 2011. [PDF]

• Anne Driemel, Herman Haverkort, Maarten Loffler, and Rodrigo Silveira :
  Flow Computations on Imprecise Terrains,
  Algorithms and Data Structures Symposium (WADS), 2011. [arXiv]

• Atlas F. Cook IV, Anne Driemel, Sariel Har-Peled, Jessica Sherette, and Carola Wenk:
  Computing the Frechet Distance Between Folded Polygons,
  Algorithms and Data Structures Symposium (WADS), 2011. [arXiv]

• Anne Driemel and Sariel Har-Peled:
  Jaywalking your Dog - Computing the Frechet Distance with Shortcuts,
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012. [arXiv]

• Anne Driemel, Benjamin Raichel, and Sariel Har-Peled:
  On the Expected Complexity of Voronoi Diagrams on Terrains,
  28th Symposium on Computational Geometry (SoCG), 2012. [arXiv]

Journal Publications (peer-reviewed)

• Maike Buchin, Anne Driemel, Marc van Kreveld, and Vera Sacristan:
  Segmenting trajectories: A framework and algorithms using spatiotemporal criteria ,
  Journal of Spatial Information Science (JOSIS), 3:33-63, 2011.

• Anne Driemel, Sariel Har-Peled, and Carola Wenk:
  Approximating the Frechet Distance for Realistic Curves in Near Linear Time,
  Discrete and Computational Geometry (DCG), Springer, 2012.