Rolf Klein

About

Rolf Klein is a distinguished computer scientist whose research sits at the intersection of computational geometry, robotics, and online algorithms. He is best known for his foundational contributions to mobile robot exploration and navigation under uncertainty, particularly the challenge of traversing unknown environments with provable efficiency guarantees. Klein's most celebrated work addresses the **polygon exploration problem**, where he developed an online strategy enabling a vision-equipped robot to explore an unknown simple polygon with a tour no more than 26.5 times the length of the optimal offline watchman route — a landmark result that garnered 117 citations. His earlier work on navigating unknown streets with bounded detour (68 citations) established key theoretical frameworks for competitive robot strategies, a theme he developed extensively throughout his career. His 1988 work on Voronoi diagrams generalized to arbitrary metrics (46 citations) demonstrates his broader contributions to computational geometry. His 2010 survey on online searching and exploration algorithms (41 citations) has become an important reference for researchers entering the field. Across his body of work, Klein has consistently championed **competitive analysis** as a rigorous framework for evaluating autonomous systems operating with incomplete information, shaping how generations of researchers approach robot navigation, sensor-based planning, and algorithmic decision-making under uncertainty.

Research Focus

Key Achievements

Top Papers

1. 1
   The Polygon Exploration Problem

   117 citations · 2001
2. 2
   Walking an unknown street with bounded detour

   68 citations · 1992
3. 3
   Voronoi diagrams based on general metrics in the plane

   46 citations · 1988
4. 4
   Online algorithms for searching and exploration in the plane

   41 citations · 2010
5. 5
   Exploring Simple Grid Polygons

   38 citations · 2005
6. 6
   Online searching with an autonomous robot

   29 citations · 2005
7. 7
   Sensor Based Intelligent Robots

   29 citations · 2002
8. 8
   A competitive strategy for learning a polygon

   29 citations · 1997
9. 9
   COMPETITIVE STRATEGIES FOR AUTONOMOUS SYSTEMS

   26 citations · 1995
10. 10
    Walking an unknown street with bounded detour

    20 citations · 2002

Key Collaborators

Contact & Links