Prof. Dr. Rolf Klein

OfficeUniversity of Bonn
Institute of
Computer Science, Dept. I
Room E.61
Friedrich-Ebert-Allee 144
D-53113 Bonn
Phone+49 (228) 73 - 4134
Fax +49 (228) 73 - 4321
Office HoursBy appointment

Curriculum Vitae

born September 5, 1953, in Münster, Germany
marriage December 27, 1984, in Nottuln, Germany
one daughter, born January 1, 1997, in Munich, Germany

1978Diploma in Mathematics und Mathematical Logic, University of Münster, Germany
1982Doctorate in Mathematics, University of Erlangen-Nürnberg, Germany
1986/87Visiting Assistant Professor, Data Structuring Group, Department of Computer Science, University of Waterloo, Canada
1989Habilitation in Computer Science, University of Freiburg, Germany
1989Associate Professor of Computer Science, Department of Mathematics, University of Essen, Germany
1991Professor of Computer Science, University of Hagen, Germany
2000-todayProfessor of Computer Science, Faculty of Natural Sciences, University of Bonn, Germany

Research Interests

Computational Geometry, Discrete Geometry, On-Line Algorithms, Algorithms and Data Structures


Editorial Boards

  • Computational Geometry: Theory and Applications (CGTA)
  • Journal of Spatial Information Science (JOSIS)

Research Publications Co-Edited

  • Special Issue SoCG'13, Discrete & Computational Geometry 52(2)
  • Special Issue SoCG'13, Computational Geometry: Theory and Applications
  • Special Issue EuroCG'03, Computational Geometry: Theory and Applications 30(2)
  • Volumes 2238 and 2598 of Lecture Notes in Computer Science

Research Publications Co-Authored

  • 1 textbook, 2 research monographs
  • 14 book chapters
  • 116 refereed journal and conference papers; two best paper awards
  • 167 conference and colloquium talks

Recent Publications

  • A fire fighter's problem, with E. Langetepe and C. Levcopoulos,
    31st Symposium on Computational Geometry (SoCG'15)
  • Most finite point sets in the plane have dilation $>1$, with M. Kutz and R. Penninger,
    Discrete & Computational Geometry 53, pp. 80-106, 2015
  • A new upper bound for the VC-dimension of visibility regions, with A. Gilbers,
    Computational Geometry: Theory and Applications 46(8), pp. 61-74, 2014
  • Abstract Voronoi diagrams with disconnected regions, with C. Bohler,
    to appear in International Journal of Computational Geometry and Applications, 2015,
    special issue on ISAAC'13
  • Abstract Voronoi diagrams, to appear in Encyclopedia of Algorithms, 2015
  • Voronoi diagrams and Delaunay triangulations, to appear in Encyclopedia of Algorithms, 2015
  • Approximation Algorithms for the Geometric Fire fighter and Budget Fence Problems, with C. Levcopoulos and A. Lingas,
    Latin American Theoretical Informatics Symposium (LATIN'14), LNCS 8392, pp. 261-272
  • Forest-Like Abstract Voronoi Diagrams in Linear Time, with C. Bohler and C.H. Liu,
    26th Canadian Conference on Computational Geometry (CCCG'14)
  • Optimally solving a transportation problem, with D. Geiß, R. Penninger, and G. Rote,
    Computational Geometry: Theory and Applications 47(1), pp. 1009-1016, 2013, also in COCOON'12
  • On the complexity of higher order abstract Voronoi diagrams, with C. Bohler, P. Cheilaris, C.H. Liu, E. Papadopoulou, and M. Zavershynskyi,
    40th International Colloquium on Automata, Languages and Programming (ICALP'13), pp. 208-219
  • Voronoi Diagrams and Delaunay Triangulations, with F. Aurenhammer and D.T. Lee, 337 pages,
    World Scientific Publ. Co., 2013.

Ph.D. Students

Research Visits

University of Alicante; Free University of Berlin; Bellairs Research Institute, Barbados; University of Catalunya, Barcelona; Hong Kong University of Science and Technology; Lund University; Carleton University, Ottawa; Universidad de Cantabria, Santander; Max-Planck Institute, Saarbrücken; Fudan University, Shanghai; National Chung Hsing University, Taichung; Academia Sinica, Taipei; Amirkabir University, Teheran; Utrecht University; University of Waterloo.

Professional Service

Academic Positions

2004-2005, 2008-2009Director of the Institute of Computer Science, University of Bonn
1998-2000Member of Senate, University of Hagen
1994-1995Dean of the Department of Computer Science, University of Hagen

Committees Chaired

2013 Program committee 28th ACM Symposium on Computational Geometry (co-chair)
2000-2001Karl V. Karlstrom Outstanding Educator Awards Committee, Association for Computing Machinery
1993-2007Special Interest Group on Computational Geometry, Gesellschaft für Informatik
1991-todaySeveral recruiting and Ph. D. committees

Committees Served On

1996-2004 Advisory Board of the Hermann-Minkowski Minerva Center, Tel Aviv University, Israel
1999-2000 Karl V. Karlstrom Outstanding Educator Awards Committee, Association for Computing Machinery, U.S.A.
2004-2012 Postdoc Selection Board, German Academic Exchange Service (DAAD)
1991-today Program committees of 32 international conferences; recently FCT'15, WADS'15, EuroCG'15, ISVD'13, WADS'13, ACM SoCG'13
Organizing committees of 11 international research seminars at Schloß Dagstuhl, Germany
26 Ph.D. committees at Universities of Barcelona, Bonn, Eindhoven, Freiburg, Hagen, Lugano, Lulea, Lund, Munich, Saarbrücken, Utrecht, Würzburg

Reviewing Duties

  • U.S. National Science Foundation (NSF)
  • Natural Sciences and Engineering Research Council of Canada (NSERC)
  • Israel Science Foundation
  • German-Israeli Foundation for Scientific Research and Development
  • German Research Foundation (DFG)
  • Alexander-von-Humboldt Foundation (AvH)
  • German Academic Exchange Service (DAAD)
  • Max-Planck Society
  • Numerous scientific journals and conferences

Society Membership

Association for Computing Machinery (ACM), Gesellschaft für Informatik (GI), Deutscher Hochschulverband

Projects Funded

  • Abstrakte Voronoi-Diagramme, funded by DFG (Kl 655/ 2-1, 2-2), 1991-1995.
  • Kompetitive Bahnplanung, funded by DFG (Kl 655/ 8-1, 8-2, 8-3), 1995-2001.
  • Distanzprobleme und Voronoi-Diagramme für verallgemeinerte Metriken, funded by DAAD under Acciones Integradas, 1995.
  • Entwurf und Implementierung eines interaktiven Systems zur Spezifikation und Compilierung von Dokumentendesign with A. Brüggemann-Klein and Th. Ottmann, funded by DFG (BR 1309/2-1), 1995-1997.
  • Virtuelle Universität, with G. Schlageter, H.-W. Six and C. Unger, funded by MWF NRW, 1996-1998.
  • Eine Dokumenttypdefinition für das Deutsche Steuerrecht, with Griebsch & Rochol Druck GmbH, Hamm, 1997-1998.
  • Standortplanung und verallgemeinerte Voronoi-Diagramme, funded by DAAD under Acciones Integradas 2000/2001.
  • Exploration and Search in Geometric Environments, funded by DAAD in Projektbezogenes Personenaustauschprogramm with Hong Kong, 2003/2004.
  • Dilation Geometrischer Netzwerke, funded by DFG (Kl 655/ 14-1, 14-2, 14-3), 2003-2006.
  • Spatial Decompositions and Graphs, EuroGIGA, funded by DFG (Kl 655/17-1), 2011-2013.
en/staff/rolfklein.txt · Zuletzt geändert: 2015/03/28 23:40 von demir