Search Results

Documents authored by Klein, Rolf

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.60
Partially Walking a Polygon

Authors: Franz Aurenhammer, Michael Steinkogler, and Rolf Klein

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.
Cite as

Franz Aurenhammer, Michael Steinkogler, and Rolf Klein. Partially Walking a Polygon. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 60:1-60:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2018.60,
  author =	{Aurenhammer, Franz and Steinkogler, Michael and Klein, Rolf},
  title =	{{Partially Walking a Polygon}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{60:1--60:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.60},
  URN =		{urn:nbn:de:0030-drops-100089},
  doi =		{10.4230/LIPIcs.ISAAC.2018.60},
  annote =	{Keywords: Polygon, guard walk, visibility}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.21
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

Authors: Cecilia Bohler, Rolf Klein, and Chih-Hung Liu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.
Cite as

Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohler_et_al:LIPIcs.SoCG.2016.21,
  author =	{Bohler, Cecilia and Klein, Rolf and Liu, Chih-Hung},
  title =	{{An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.21},
  URN =		{urn:nbn:de:0030-drops-59135},
  doi =		{10.4230/LIPIcs.SoCG.2016.21},
  annote =	{Keywords: Order-k Voronoi Diagrams, Abstract Voronoi Diagrams, Randomized Geometric Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.768
A Fire Fighter’s Problem

Authors: Rolf Klein, Elmar Langetepe, and Christos Levcopoulos

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.
Cite as

Rolf Klein, Elmar Langetepe, and Christos Levcopoulos. A Fire Fighter’s Problem. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 768-780, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.SOCG.2015.768,
  author =	{Klein, Rolf and Langetepe, Elmar and Levcopoulos, Christos},
  title =	{{A Fire Fighter’s Problem}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{768--780},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.768},
  URN =		{urn:nbn:de:0030-drops-51044},
  doi =		{10.4230/LIPIcs.SOCG.2015.768},
  annote =	{Keywords: Motion Planning, Dynamic Environments, Spiralling strategies, Lower and upper bounds}
}
Document
DOI: 10.4230/DagSemProc.09451.1
09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining

Authors: Gautam Das, Joachim Gudmundsson, Rolf Klein, Christian Knauer, and Michiel Smid

Published in: Dagstuhl Seminar Proceedings, Volume 9451, Geometric Networks, Metric Space Embeddings and Spatial Data Mining (2010)

Abstract
From November 1 to 6, 2009, the Dagstuhl Seminar 09451 ``Geometric Networks, Metric Space Embeddings and Spatial Data Mining'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Gautam Das, Joachim Gudmundsson, Rolf Klein, Christian Knauer, and Michiel Smid. 09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining. In Geometric Networks, Metric Space Embeddings and Spatial Data Mining. Dagstuhl Seminar Proceedings, Volume 9451, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:DagSemProc.09451.1,
  author =	{Das, Gautam and Gudmundsson, Joachim and Klein, Rolf and Knauer, Christian and Smid, Michiel},
  title =	{{09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining}},
  booktitle =	{Geometric Networks, Metric Space Embeddings and Spatial Data Mining},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9451},
  editor =	{Gautam Das and Joachim Gudmundsson and Rolf Klein and Christian Knauer and Michiel Smid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09451.1},
  URN =		{urn:nbn:de:0030-drops-24380},
  doi =		{10.4230/DagSemProc.09451.1},
  annote =	{Keywords: Geometric networks, metric space embeddings, spatial data mining, spanners, dilation, distortion}
}
Document
DOI: 10.4230/DagSemProc.09171.1
09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract
From 19.01. to 24.04.2009, the Dagstuhl Seminar 09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.1,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Abstracts Collection  – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1},
  URN =		{urn:nbn:de:0030-drops-21228},
  doi =		{10.4230/DagSemProc.09171.1},
  annote =	{Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms}
}
Document
DOI: 10.4230/DagSemProc.09171.2
09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms

Authors: Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier

Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Abstract
Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved algorithm can be obtained by considering a finer partition of the input space. As this idea has been independently rediscovered in many areas, the workshop gathered participants from different fields in order to explore the impact and the limits of this technique, in the hope to spring new collaboration and to seed the unification of the technique.
Cite as

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.2,
  author =	{Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf},
  title =	{{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9171},
  editor =	{J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2},
  URN =		{urn:nbn:de:0030-drops-21207},
  doi =		{10.4230/DagSemProc.09171.2},
  annote =	{Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms}
}
Document
DOI: 10.4230/DagSemProc.06481.1
06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings

Authors: Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff

Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

Abstract
The Dagstuhl Seminar 06481 ``Geometric Networks and Metric Space Embeddings'' was held from November~26 to December~1, 2006 in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. In this paper we describe the seminar topics, we have compiled a list of open questions that were posed during the seminar, there is a list of all talks and there are abstracts of the presentations given during the seminar. Links to extended abstracts or full papers are provided where available.
Cite as

Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff. 06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.06481.1,
  author =	{Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander},
  title =	{{06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.1},
  URN =		{urn:nbn:de:0030-drops-10291},
  doi =		{10.4230/DagSemProc.06481.1},
  annote =	{Keywords: Geometric networks, metric space embeddings, phylogenetic networks, spanners, dilation, distortion}
}
Document
DOI: 10.4230/DagSemProc.06421.1
06421 Abstracts Collection – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Abstracts Collection – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.1,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Abstracts Collection – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.1},
  URN =		{urn:nbn:de:0030-drops-8890},
  doi =		{10.4230/DagSemProc.06421.1},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.2
06421 Executive Summary – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. People in Online Algorithms have developed strategies that can deal with the inherent lack of information an autonomous robot encounters, as it sets out to perform a task in an unknown environment. Computational Geometers have obtained many results on the efficient planning of collision-free motions, and on visibility problems. Scientists and engineers in Robotics have perfected real robots to an astounding degree. Economic household robots and artificial pets are now available; more complex robots are able to carry out difficult search-and-rescue and exploration missions. The goal of this seminar is to bring together researchers from robotics, computational geometry, and online algorithms, in order to exchange problems and ideas, and to jointly work towards solutions. The following questions seem crucial. Given the advanced level of technical development, what are the strategic planning problems researchers in robotics need to solve in the next decade? How can real environments and robots be modeled, so that planning problems become tractable by algorithmic methods, and solutions are still significant for applications? In particular, what can be assumed about perception and motion accuracy? We are planning for plenary sessions where members of all groups can present their problems and recent work. In addition, there will be plenty of time for discussions.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Executive Summary – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.2,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Executive Summary – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.2},
  URN =		{urn:nbn:de:0030-drops-8720},
  doi =		{10.4230/DagSemProc.06421.2},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.5
Competitive Online Searching for a Ray in the Plane

Authors: Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal. First, we give a search strategy for a special case of the ray search---the window shopper problem---, where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$.
Cite as

Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive Online Searching for a Ray in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{eubeler_et_al:DagSemProc.06421.5,
  author =	{Eubeler, Andrea and Fleischer, Rudolf and Kamphans, Tom and Klein, Rolf and Langetepe, Elmar and Trippen, Gerhard},
  title =	{{Competitive Online Searching for a Ray in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.5},
  URN =		{urn:nbn:de:0030-drops-8687},
  doi =		{10.4230/DagSemProc.06421.5},
  annote =	{Keywords: Online motion planning, competitive analysis, ray search}
}
Document
DOI: 10.4230/DagSemProc.05031.27
Searching with an Autonomous Robot

Authors: Sándor Fekete, Rolf Klein, and Andreas Nüchter

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video.
Cite as

Sándor Fekete, Rolf Klein, and Andreas Nüchter. Searching with an Autonomous Robot. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05031.27,
  author =	{Fekete, S\'{a}ndor and Klein, Rolf and N\"{u}chter, Andreas},
  title =	{{Searching with an Autonomous Robot}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.27},
  URN =		{urn:nbn:de:0030-drops-1919},
  doi =		{10.4230/DagSemProc.05031.27},
  annote =	{Keywords: Searching , visibility problems , watchman problems , online searching , competitive strategies , autonomous mobile robots three-dimensional laser scanning , Kurt3D}
}
Document
DOI: 10.4230/DagSemRep.406
Robot Navigation (Dagstuhl Seminar 03501)

Authors: Rudolf Fleischer and Rolf Klein

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rudolf Fleischer and Rolf Klein. Robot Navigation (Dagstuhl Seminar 03501). Dagstuhl Seminar Report 406, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{fleischer_et_al:DagSemRep.406,
  author =	{Fleischer, Rudolf and Klein, Rolf},
  title =	{{Robot Navigation (Dagstuhl Seminar 03501)}},
  pages =	{1--4},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{406},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.406},
  URN =		{urn:nbn:de:0030-drops-152863},
  doi =		{10.4230/DagSemRep.406},
}
Document
DOI: 10.4230/DagSemRep.371
Multimedia Retrieval (Dagstuhl Seminar 03112)

Authors: Michael Clause, Rolf Klein, and Ian H. Witten

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Michael Clause, Rolf Klein, and Ian H. Witten. Multimedia Retrieval (Dagstuhl Seminar 03112). Dagstuhl Seminar Report 371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{clause_et_al:DagSemRep.371,
  author =	{Clause, Michael and Klein, Rolf and Witten, Ian H.},
  title =	{{Multimedia Retrieval (Dagstuhl Seminar 03112)}},
  pages =	{1--4},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{371},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.371},
  URN =		{urn:nbn:de:0030-drops-152517},
  doi =		{10.4230/DagSemRep.371},
}
Document
DOI: 10.4230/DagSemRep.302
Computational Geometry (Dagstuhl Seminar 01121)

Authors: Rolf Klein and Günter Rote

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rolf Klein and Günter Rote. Computational Geometry (Dagstuhl Seminar 01121). Dagstuhl Seminar Report 302, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{klein_et_al:DagSemRep.302,
  author =	{Klein, Rolf and Rote, G\"{u}nter},
  title =	{{Computational Geometry (Dagstuhl Seminar 01121)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{302},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.302},
  URN =		{urn:nbn:de:0030-drops-151866},
  doi =		{10.4230/DagSemRep.302},
}
Document
DOI: 10.4230/DagSemRep.289
Modelling of Sensor-Based Intelligent Robot Systems (Dagstuhl Seminar 00421)

Authors: Horst Bunke, Henrik Iskov Christensen, Gregory Hager, and Rolf Klein

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Horst Bunke, Henrik Iskov Christensen, Gregory Hager, and Rolf Klein. Modelling of Sensor-Based Intelligent Robot Systems (Dagstuhl Seminar 00421). Dagstuhl Seminar Report 289, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{bunke_et_al:DagSemRep.289,
  author =	{Bunke, Horst and Christensen, Henrik Iskov and Hager, Gregory and Klein, Rolf},
  title =	{{Modelling of Sensor-Based Intelligent Robot Systems (Dagstuhl Seminar 00421)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{289},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.289},
  URN =		{urn:nbn:de:0030-drops-151732},
  doi =		{10.4230/DagSemRep.289},
}
Document
DOI: 10.4230/DagSemRep.233
Computational Geometry (Dagstuhl Seminar 99102)

Authors: Michael Goodrich, Rolf Klein, and Raimund Seidel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Michael Goodrich, Rolf Klein, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 99102). Dagstuhl Seminar Report 233, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{goodrich_et_al:DagSemRep.233,
  author =	{Goodrich, Michael and Klein, Rolf and Seidel, Raimund},
  title =	{{Computational Geometry (Dagstuhl Seminar 99102)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{233},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.233},
  URN =		{urn:nbn:de:0030-drops-151191},
  doi =		{10.4230/DagSemRep.233},
}
Document
DOI: 10.4230/DagSemRep.168
Computational Geometry (Dagstuhl Seminar 9707)

Authors: Rolf Klein, Raimund Seidel, and Seth Teller

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rolf Klein, Raimund Seidel, and Seth Teller. Computational Geometry (Dagstuhl Seminar 9707). Dagstuhl Seminar Report 168, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{klein_et_al:DagSemRep.168,
  author =	{Klein, Rolf and Seidel, Raimund and Teller, Seth},
  title =	{{Computational Geometry (Dagstuhl Seminar 9707)}},
  pages =	{1--34},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{168},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.168},
  URN =		{urn:nbn:de:0030-drops-150558},
  doi =		{10.4230/DagSemRep.168},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact