Anne Driemel
Contact Information
Department of Information and Computing Sciences
Utrecht University
PO Box 80.089
3508TB Utrecht
The Netherlands
Email : a.driemel@uu.nl
Telephone : +31 (30) 253 6759
Fax: +31 (30) 251 3791
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.
Since 10 December I am the proud mother of Emma.
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.