Searching with an autonomous robot, in (2009)
Sándor P. Fekete, Rolf Klein, Andreas Nüchter
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...
09171 Executive Summary -- Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Barbay, Jérémy, Klein, Rolf, López-Ortiz, Alejandro, Niedermeier, Rolf
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...
09171 Abstracts Collection -- Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Barbay, Jérémy, Klein, Rolf, López-Ortiz, Alejandro, Niedermeier, Rolf
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...
How Many Lions Are Needed to Clear a Grid? (2009)
Florian Berger, Alexander Gilbers, Ansgar Grüne, Rolf Klein
We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction...
SIMPLIFIED ABSTRACT VORONOI DIAGRAMS (2008)
Abstract. We present a simplified system of axioms for Abstract Voronoi Diagrams that should pave the way for new applications in theory and practice. 1. History In the Eighties, many different kinds...
Geometric Dilation of Closed Planar Curves: New (2008)
Lower Bounds, Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein
Given two points on a closed planar curve, C, we can divide the length of a shortest connecting path in C by their Euclidean distance. The supremum of these ratios, taken over all pairs of points on...
Java Applets for the Dynamic Visualization of Voronoi Diagrams (2008)
Christian Icking, Rolf Klein, Peter Köllner, Lihong Ma
We discuss the design of Java applets that visualize how the Voronoi diagram of n points continuously changes as individual points are moved across the plane, or as the underlying distance function...
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Abstract. Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this...
How Many Lions Can One Man Avoid? (2008)
Florian Berger, Ansgar Grüne, Rolf Klein
Abstract. A pride of lions are prowling among the vertices and edges of an n × n grid. If their paths are known in advance, is it possible to design a safe path for a man that avoids all lions,...
Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...
The detour and spanning ratio of a graph � embedded in �� � measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Consider a plane graph G, drawn with straight lines. For every pair a, b of vertices of G, we compare the shortestpath distance between a and b in G (with Euclidean edge lengths) to their actual...
Competitive Online Searching for a Ray in the Plane ⋆ Abstract (2008)
Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the...
Competitive Online Searching for a Ray in the Plane (2008)
Andrea Eubeler Rudolf, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the flashlight, and...
Doktors Der Naturwissenschaften, Lihong Ma, Erster Gutachter, Prof Dr, ...
genehmigte
A Competitive Strategy for Learning a Polygon (Short Version) (2007)
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
this paper, we present the first strategy for general simple polygons and we prove a competitive factor of 133.
Searching a goal on m rays within a fixed distance (extended abstract) (2007)
Christian Icking, Rolf Klein, Elmar Langetepe
The problem of searching a goal on m rays is well known. If the goal is in unknown position then the target can be found by choosing a path not longer than � �m−1 m 1+2m m−1 times the...
Given a simple polygon in the plane with two distinguished vertices, s and g,isit possible for two guards to simultaneously walk along the two boundary chains from s to g in such a way that they are...
The polygon exploration problem (2007)
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
Abstract. We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest...
Java Applets for the Dynamic Visualization of Voronoi Diagrams (2007)
Christian Icking, Rolf Klein, Peter Köllner, Lihong Ma
This paper is dedicated to Thomas Ottmann on the occasion of his 60th birthday. We discuss the design of several Java applets that visualize how the Voronoi diagram of n points continuously changes...
Reliability of the Bad Sobernheim Stress Questionnaire (BSSQbrace) (2007)
Botens-Helmus, Christine, Klein, Rolf, Stephan, Carola, Weiss, Hans-Rudolf
No abstract available.
Computing Geometric Minimum-Dilation Graphs is NP-Hard (2007)
Consider a geometric graph G, drawn with straight lines in the plane. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to...
Florian Berger, Ansgar Grüne, Rolf Klein, One Man Avoid
A pride of lions are prowling among the vertices and edges of an n × n grid. If their paths are known in advance, is it possible to design a safe path for a man that avoids all lions, assuming that...
Computing Geometric Minimum-Dilation Graphs Is NP-Hard (2007)
Consider a geometric graph $G$, drawn with straight lines in the plane. For every pair $a$,$b$ of vertices of $G$, we compare the shortest-path distance between $a$ and $b$ in $G$ (with Euclidean...
Competitive Online Searching for a Ray in the Plane (2007)
Eubeler, Andrea, Fleischer, Rudolf, Kamphans, Tom, Klein, Rolf, Langetepe, Elmar, Trippen, Gerhard
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...
06421 Executive Summary -- Robot Navigation (2007)
Fekete, Sándor, Fleischer, Rudolf, Klein, Rolf, Lopez-Ortiz, Alejandro
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...
06421 Abstracts Collection -- Robot Navigation (2007)
Fekete, Sándor, Fleischer, Rudolf, Klein, Rolf, Lopez-Ortiz, Alejandro
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...
06481 Abstracts Collection -- Geometric Networks and Metric Space Embeddings (2007)
Gudmundsson, Joachim, Klein, Rolf, Narasimhan, Giri, Smid, Michiel, Wolff, Alexander
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...
The Geometric Dilation of Finite Point Sets (2006)
Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein
Let G be an embedded planar graph whose edges may be curves. For two arbitrary points of G, we can compare the length of the shortest path in G connecting them against their Euclidean distance. The...
Geometric Dilation of Closed Planar Curves: New Lower Bounds (2006)
Lower Bounds, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein
Given two points on a closed planar curve, C, we can divide the length of a shortest connecting path in C by their Euclidean distance. The supremum of these ratios, taken over all pairs of points on...
Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, A. Ebbers-baumann, ...
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...
Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer
Communicated by Li Zhang Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on...
Computing geometric minimum-dilation graphs is NP-hard (2006)
Abstract. Consider a geometric graph G, drawn with straight lines in the plane. For every pair a, b of vertices of G, we compare the shortestpath distance between a and b in G (with Euclidean edge...
Voronoi Diagram and Related Problems (2006)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
team was supported by DAAD grant 314-AI-e-dr.
Geometric Networks and Metric Space Embeddings (2006)
Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, Alexander Wolff, Tu Eindhoven, ...
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...
Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual...
Competitive online searching for a ray in the plane (2005)
Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the flashlight, and...
Maximizing a Voronoi Region: The Convex Case (2005)
Frank Dehne, Rolf Klein, Raimund Seidel
Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors...
Consider a plane graph G, drawn with straight lines. For every pair a, b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual...
Exploring Grid Polygons Online (2005)
Christian Icking, Tom Kamphans, Rolf Klein, Elmar Langetepe
We investigate the exploration problem of a short-sighted mobile robot moving in an unknown cellular room. To explore a cell, the robot must enter it. Once inside, the robot knows which of the 4...
Exploring Simple Grid Polygons (2005)
Christian Icking, Tom Kamphans, Rolf Klein, Elmar Langetepe
We investigate the online exploration problem of a shortsighted mobile robot moving in an unknown cellular room without obstacles.
On Geometric Dilation and Halving Chords (2005)
Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Let G be an embedded planar graph whose edges may be curves. The detour between two points, p and q (on edges or vertices) of G, is the ratio between the shortest path in G between p and q and their...
Embedding Point Sets into Plane Graphs of Small Dilation (2005)
Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S?EvenforasetS as simple as five points evenly placed on the circle, this question seems...
On the Geometric Dilation of Closed Curves, Graphs and Point Sets (2005)
Adrian Dumitrescu, Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points p and q (on edges or vertices) of G is the ratio between the length of a shortest path connecting p and q in G...
On geometric dilation and halving chords (2005)
Adrian Dumitrescu, Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Abstract. Let G be an embedded planar graph whose edges may be curves. The detour between two points, p and q (on edges or vertices) of G, is the ratio between the shortest path in G between p and q...
Embedding point sets into plane graphs of small dilation (2005)
Annette Ebbers-baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this paper we...
Searching with an Autonomous Robot (2005)
Fekete, Sándor, Klein, Rolf, Nüchter, Andreas
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...
On the geometric dilation of closed curves, graphs, and point sets (2004)
Dumitrescu, Adrian, Ebbers-Baumann, Annette, Grüne, Ansgar, Klein, Rolf, Rote, Günter
The detour between two points u and v (on edges or vertices) of an embedded planar graph whose edges are curves is the ratio between the shortest path in in the graph between u and v and their...
Competitive Online Approximation of the Optimal Search Ratio (2004)
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen
How e#ciently can we search an unknown environment for a goal in unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for general...
Competitive Online Approximation of the Optimal Search Ratio (2004)
Rudolf Fleischer Tom, Tom Kamphans, Rolf Klein, Elmar Langetepe
How e#ciently can we search an unknown environment for a goal in unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for...
Online searching with an autonomous robot (2004)
Sándor P. Fekete, Rolf Klein, Andreas Nüchter
Summary. 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...
On the Geometric Dilation of Finite Point Sets (2003)
Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein
Let G be an embedded planar graph whose edges may be curves. For two arbitrary points of G, we can compare the length of the shortest path in G connecting them against their Euclidean distance.
Computing the Detour of Polygons (2003)
Ansgar Gr Une, Ansgar Grüne, Rolf Klein, Elmar Langetepe
Let P be a simple polygon in with n vertices. The detour of P between two points, p, q P , is the length of a shortest path contained in P and connecting p to q, divided by the distance of these...
On the competitive complexity of navigation tasks (2002)
Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe
Abstract. A strategy S solving a navigation task T is called competitive with ratio r if the cost of solving any instance t of T does not exceed r times the cost of solving t optimally. The...
The weighted farthest color Voronoi diagram on trees and graphs (2002)
Ferran Hurtado, Rolf Klein, Elmar Langetepe, Vera Sacristan
Let n point sites be situated on the vertices or edges of a geometric graph G over e edges. Each site can be assigned a multiplicative weight and a color. We discuss the complexity, and provide...
Computing the Detour of Polygonal Curves (2002)
Pankaj K. Agarwal, Pankaj K. Agarwal, Rolf Klein, Rolf Klein, Christian Knauer, Christian Knauer, ...
Let P be a simple polygonal chain in E with n edges. The detour of P between two points, x and y, is the ratio between the length of P between x any y and their Euclidean distance.
Maximizing a Vo24 Regio The Co vex Case Frank Dehne (2002)
Klein And Rdo, Frank Dehne, Rolf Klein, Raimund Seidel
Given a set S o s po7 ts in the plane, wheredo we place a new poK t, p, ino77) to maximize the areao itsregio in the Vo9730 diagramo S and p? We study the case where the Vo80(8 neighbo9 o p are in co...
The weighted farthest color Voronoi diagram on trees and graphs (Extended Abstract) (2002)
Ferran Hurtado, Vera Sacristan, Rolf Klein, Elmar Langetepe
Ferran Hurtado, Vera Sacrist an Dept. de Matem atica Aplicada II Univ. Polit ecnica de Catalunya, Barcelona, Spain Rolf Klein, Elmar Langetepe Institut f ur Informatik I Universit at Bonn, Germany...
Ferran Hurtado, Rolf Klein, Elmar Langetepe
The weighted farthest color Voronoi diagram on trees and graphs
The weighted farthest color Voronoi diagram on trees and graphs (2002)
Ferran Hurtado, Rolf Klein, Elmar Langetepe, Vera Sacristan
Let n point sites be situated on the vertices or edges of a geometric graph G over e edges. Each site can be assigned a multiplicative weight and a color. We discuss the complexity, and provide...
The farthest color Voronoi diagram and related problems (2001)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
Suppose there are k types of facilities, e. g. schools, post offices, supermarkets, modeled by n colored points in the plane, each type by its own color. One basic goal in choosing a residence...
Smallest color-spanning objects (2001)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
Motivated by questions in location planning, we show for a set of colored points in the plane how to compute the smallest (by perimeter or area) axis-parallel rectangle, the narrowest strip, and...
The farthest color Voronoi diagram and related problems (2001)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
Suppose there are k types of facilities, e. g. schools, post o#ces, supermarkets, modeled by n colored points in the plane, each type by its own color. One basic goal in choosing a residence location...
Smallest color-spanning objects (2001)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
Motivated by questions in location planning, we show for a set of colored point sites in the plane how to compute the smallest (by perimeter or area) axis-parallel rectangle, the narrowest strip, and...
Smallest color-spanning objects (2001)
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, ...
Abstract. Motivated by questions in location planning, we show for a set of colored point sites in the plane how to compute the smallest— by perimeter or area—axis-parallel rectangle and the...
Exploring an unknown cellular environment (2000)
Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Praktische Informatik Vi
We investigate the exploration problem of a short-sighted mobile robot moving about in an unknown cellular room. In order to explore a cell, the robot must enter it. Once inside, the robot knows...
Self-approaching curves (1999)
Christian Icking, Rolf Klein, Elmar Langetepe
We present a new class of curves which are self-approaching in the following sense. For any three consecutive points a, b, c on the curve the point b is closer to c than a to c. This is a...
On bisectors for different distance functions (1999)
Christian Icking, Rolf Klein, Lihong Ma
Let γC and γD be two convex distance functions in the plane with convex unit balls C and D. Giventwopoints,p and q, we investigate the bisector, B(p, q), of p and q, where distance from p is...
An optimal competitive strategy for walking in streets (1999)
Christian Icking, Rolf Klein, Elmar Langetepe
We present an optimal strategy for searching for a goal in a street which achieves the competitive factor of √ 2, thus matching the best lower bound known before. This finally settles an...
Anne Brüggemann-klein, Rolf Klein, Britta Landgraf
Traditional searching and browsing functions for bibliographic databases do no longer
On bisectors for convex distance functions in 3-space (1999)
Christian Icking, Rolf Klein, Ngoc-minh Lê, Lihong Ma, Francisco Santos
We investigate the structure of the bisector of point sites under arbitrary convex distance functions in three dimensions. Our results show that it is advantageous for analyzing bisectors to consider...
On Bisectors for Different Distance Functions (1999)
Christian Icking, Rolf Klein, Lihong Ma, Stefan Nickel, Ansgar Weißler
Let γC and γD be two convex distance functions in the plane with convex unit balls C and D. Given two points, p and q, we investigate the bisector, B(p, q), of p and q, where...
On Bisectors for Convex Distance Functions in 3-Space (1999)
Christian Icking, Rolf Klein, Ngoc-minh Lê, Lihong Ma, Francisco Santos
We investigate the structure of the bisector of point sites under arbitrary convex distance functions in three dimensions. Our results show that it is advantageous for analyzing bisectors to consider...
Generalized self-approaching curves (1998)
Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, Günter Rote, ...
Abstract. We consider all planar oriented curves that have the following property depending on a fixed angle ϕ. ForeachpointB on the curve, the rest of the curve lies inside a wedge of angle ϕ with...
The polygon exploration problem I: A competitive strategy (1998)
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman...
Generalized Self-Approaching Curves (1998)
Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Christian Icking, Christian Icking, ...
We consider all planar oriented curves that have the following property depending on a fixed angle '. For each point B on the curve, the rest of the curve lies inside a wedge of angle '...
Generalized Self-Approaching Curves (1998)
Spezialforschungsbereich F, Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Günter Rote, ...
We consider all planar oriented curves that have the following property depending on a #xed angle '. For each point B on the curve, the rest of the curve lies inside a wedge of angle ' with...
On the Pagination of Complex Documents (1998)
Anne Brüggemann-klein, Rolf Klein, Stefan Wohlfeil
The pagination problem of complex documents is in placing text and floating objects on pages in such a way that each object appears close to, but not before, its text reference. Current electronic...
The Polygon Exploration Problem II: The Angle Hull (1998)
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
Let D be a connected region inside a simple polygon, P . We define the angle hull of D, to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of...
Rolf Klein, Raimund Seidel, Seth Teller, Rolf Klein (hagen, Raimund Seidel (saarbrucken
This report contains the abstracts of all the 29 talks, in the order as they were given at the meeting, as well as abstracts of the problems presented at the open problem session. Compiled by Rolf...
An Efficient Competitive Strategy for Learning a Polygon (1996)
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
We provide a competitive strategy for a mobile robot with vision, that has to explore an unknown simple polygon starting from and returning to a given point xo on the boundary. Our strategy creates a...
Competitive Strategies for Autonomous Systems (1995)
A strategy for working with incomplete information is called competitive if it solves each problem instance at a cost not exceeding the cost of an optimal solution (with full information available),...
Fast Skeleton Construction (1995)
For a polygon P , the skeleton of P is a partition of P into regions assigned to the edges of P: A point p inside P belongs to the region of an edge e if and only if e is the closest edge of P: We...
Competitive strategies for autonomous systems (1995)
A strategy for working with incomplete information is called competitive if it solves each problem instance at a cost not exceeding the cost of an optimal solution (with full information available),...
Pagination Reconsidered (1995)
Anne Brüggemann-klein, Rolf Klein, Stefan Wohlfeil
We present a new algorithm for pagination that minimizes the number of page turns that are necessary while reading a formatted document. This approach keeps the total number of pages small and places...
Searching for the Kernel of a Polygon: A Competitive Strategy Using Self-Approaching Curves (1995)
Christian Icking, Rolf Klein, Elmar Langetepe
We present a competitive strategy for walking into the kernel of an initially unknown star-shaped polygon. From an arbitrary start point, s, within the polygon, our strategy finds a path to the...
A Linear-Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon (1994)
For a polygon P , the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P: A point p inside P belongs to the region of a vertex v if and only if v is the...
An Optimal Competitive Strategy for Looking Around a Corner (1994)
Christian Icking, Rolf Klein, Lihong Ma
We consider a problem of motion planning under uncertainty. A robot can navigate freely in the plane and, using a built-in vision system, can determine distances and angles. Initially, the robot...
A Linear-Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon (1993)
Rolf Klein, Praktische Informatik Vi
For a polygon P , the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. Apointpinside P belongs to the region of a vertex v if and only if v is the closest...
"The Big Sweep": On the Power of the Wavefront Approach to Voronoi Diagrams (1992)
We show that the wavefront approach to Voronoi diagrams (a deterministic line sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the...
Wrapping Ellipses around a Convex Skeleton (1992)
Rolf Klein, Lihong Ma, Praktische Informatik Vi, Elberfelder Str
Let F and G denote two closed convex curves in the (X,Z)-plane and in the (Y,Z)-plane, correspondingly, that are symmetric about the Z-axis and cross at two points. Let S denote the solid that...
Randomized incremental construction of abstract Voronoi diagrams (1992)
Klein, Rolf, Mehlhorn, Kurt, Meiser, Stefan, Buchmann, J., Ganzinger, Harald, Paul, Wolfgang J.
Über Hilbertsche Körper. (1982)
Aus: Journal für die reine und angewandte Mathematik. Bd. 337. 1982, S. 171 - 194
Münster, Rechts- u. staatswiss. F., Diss. v. 20. Juni 1953 (Nicht f. d. Aust.).
Franz Aurenhammer, Rolf Klein, Praktische Informatik Vi
Voronoi diagrams can also be thought of as lower envelopes, in the sense mentioned at the beginning of this subsection. Namely, for each point x not situated on a bisecting curve, the relation p x q...