2005

Computational Algebra

• Embedding point sets into plane graphs of small dilation
  In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC), Hainan, China, Pages 5-16, 2005.
  A. Ebbers-Baumann, A. Grüne, M. Karpinski, R. Klein, Christian Knauer, A. Lingas
  [bibtex]

• Exact and approximation algorithms for computing the dilation spectrum of paths, trees and cycles
  In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC), Hainan, China, Pages 849-858, 2005.
  R. Klein, Christian Knauer, G. Narasimhan, M. Smid
  [bibtex]

• Configurations with few crossings in topological graphs.
  Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC), Hainan, China, Pages 604-613, 2005.
  Christian Knauer, E. Schramm, A. Spillner, A. Wolff
  [bibtex]

Computational Geometry

• An exclusion region for minimum dilation triangulations
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Eindhoven, Netherlands, 2005.
  Christian Knauer, Wolfgang Mulzer
  [bibtex]

• Spanning trees with few crossings in geometric graphs (Extended Abstract)
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Eindhoven, Netherlands, 2005.
  Christian Knauer, Etienne Schramm, Andreas Spillner, Alexander Wolff
  [bibtex]

• Simple and optimal output-sensitive construction of contour trees using monotone paths
  Computational Geometry, Theory and Applications, Volume 30, Pages 165–195, 2005.
  Yi-Jen Chiang, Tobias Lenz, Xiang Lu, Günter Rote
  [bibtex]

• Computing the Fr\'echet distance between piecewise smooth curves
  Technical Report ECG-TR-241108-01, Pages 13, May 2005.
  Günter Rote
  [bibtex]

• Simple Reconstruction of Non-Simple Curves
  Technical Report B 05-02, Freie Universität Berlin, March 2005.
  Tobias Lenz
  [bibtex]

• Reconstructing Collections of Arbitrary Curves
  In 21st Annual ACM Symposium on Computational Geometry, Pisa, Italy, June 2005.
  Tobias Lenz
  [bibtex]

• Finding the Best Shortcut in a Geometric Network
  In 21st Annual ACM Symposium on Computational Geometry, Pages to appear, Pisa, Italy, June 2005.
  M. Farshi, Panos Giannopoulos, J. Gudmundsson
  [bibtex]

• Shortest Inspection-Path Queries in Simple Polygons
  Technical Report B-05-05, Freie Universität Berlin, April 2005.
  Christian Knauer, Günter Rote
  [bibtex] [pdf]

• Minimum Dilation Triangulations
  Technical Report B-05-06, Freie Universität Berlin, April 2005.
  Christian Knauer, Wolfgang Mulzer
  [bibtex] [ps.gz]

• The Voronoi diagram of curved objects
  Discrete & Computational Geometry, Volume 34, Pages 439-453, 2005.
  Helmut Alt, Otfried Cheong, Antoine Vigneron
  [bibtex]

• Constructing Delaunay Triangulations along Space-Filling Curves
  In Proceedings of the 2nd International Symposium on Voronoi Diagrams in Science and Engineering, Pages 184 – 195, Hanyang University, Seoul, Korea, October 2005.
  Kevin Buchin
  [bibtex]

• Incremental Construction along Space-filling Curves
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Pages 17 – 20, Eindhoven, Netherlands, 2005.
  Kevin Buchin
  [bibtex]

• Semi-Computability of the Fr\'echet Distance between Surfaces
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Pages 45 – 48, Eindhoven, Netherlands, 2005.
  Helmut Alt, Maike Buchin
  [bibtex]

• Flow Complex: General Structure and Algorithm
  In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), Pages 279 – 282, Windsor, Canada, 2005.
  Kevin Buchin, Joachim Giesen
  [bibtex]

• Fr\'echet Distance between Simple Polygons
  In Proceedings 15th Annual Fall Workshop on Computational Geometry, Pages 7–8, 2005.
  Kevin Buchin, Maike Buchin, Carola Wenk
  [bibtex]

• Approximation Algorithms for the Earth Mover's Distance Under Transformations Using Reference Points
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Pages 53 - 56, Eindhoven, Netherlands, 2005.
  Oliver Klein, Remco C. Veltkamp
  [bibtex]

• Approximation Algorithms for Computing the Earth Mover's Distance Under Transformations
  In Proceedings of the 16th Annual Symposium on Algorithms and Computation (ISAAC), Sanya, Hainan, China, 2005.
  Oliver Klein, Remco C. Veltkamp
  [bibtex]

• Approximation Algorithms for the Earth Mover's Distance Under Transformations Using Reference Points
  Technical Report UU-CS-2005-003, Department of Information and Computing Sciences, Universiteit Utrecht, 2005.
  Oliver Klein, Remco C. Veltkamp
  [bibtex]

• Visibility maps of segments and triangles in 3d
  Technical Report UU-CS-2005-049, Institute of Information and Computing Sciences, Universiteit Utrecht, 2005.
  Christian Knauer, M. van Kreveld, Esther Moet
  [bibtex]

• Configurations with few crossings in topological
  Technical Report 2005-24, Fakultät für Informatik, Universität Karlsruhe, 2005.
  Christian Knauer, E. Schramm, A. Spillner, Alexander Wolff
  [bibtex]

• Dilation and Detours in Geometric Networks
  Technical Report B05-16, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 2005.
  J. Gudmundsson, Christian Knauer
  [bibtex]

• New results on Pseudo-triangulations with low vertex degree
  In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05), Pages 130-133, Windsor, 2005.
  André Schulz
  [bibtex]

• A Pointed Delaunay Pseudo-Triangulation of a Simple Polygon
  In Proceedings of the 21st European Workshop on Computational Geometry, Pages 77-80, Eindhoven, 2005.
  Günter Rote, André Schulz
  [bibtex]

Edited Publications

• Theory of Computing Systems
  Volume 38 (2), Springer New York, 2005.
  Editor(s): Helmut Alt
  [bibtex]

Geometric Optimization Problems

• Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard
  In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), Pages 192 – 195, Windsor, Canada, 2005.
  Maike Buchin, Joachim Giesen
  [bibtex]

Geometric Shape and Pattern Matching

• Matching surfaces with characteristic points
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Pages 49–51, Eindhoven, Netherlands, 2005.
  Darko Dimitrov, Christian Knauer, Klaus Kriegel
  [bibtex]

• Matching point sets with respect to the Earth Mover's distance
  In Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Eindhoven, Netherlands, Pages 27-60, 2005.
  Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
  [bibtex]

• Matching point sets with respect to the Earth Mover's distance
  In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Ibiza, Spain, 2005.
  Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
  [bibtex]

• Computing the Hausdorff Distance between Curved Objects
  In Proceedings of the 2nd International Symposium on Voronoi Diagrams in Science and Engineering, Pages 196-204, Hanyang University, Seoul, Korea, October 2005.
  Helmut Alt, Ludmila Scharf
  [bibtex]

Geometry

• Planar minimally rigid graphs and pseudo-triangulations
  Computational Geometry, Theory and Applications, 2005.
  Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley
  [bibtex] [pdf] [pdf]

• Strictly convex drawings of planar graphs
  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, 2005.
  Günter Rote
  [bibtex]