Source author record

Rolf Klein

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.MG Robotics

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The limit of $L_p$ Voronoi diagrams as $p \rightarrow 0$ is the bounding-box-area Voronoi diagram

We consider the Voronoi diagram of points in the real plane when the distance between two points $a$ and $b$ is given by $L_p(a-b)$ where $L_p((x,y)) = (|x|^p+|y|^p)^{1/p}.$ We prove that the Voronoi diagram has a limit as $p$ converges to zero from above or from below: it is the diagram that corresponds to the distance function $L_*((x,y)) = |xy|$ . In this diagram, the bisector of two points in general position consists of a line and two branches of a hyperbola that split the plane into three faces per point. We propose to name $L_*$ as defined above the "geometric $L_0$ distance".

preprint2016arXiv

A Fire Fighter's Problem

Suppose that a circular fire spreads in the plane at unit speed. A single 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 contribute two results. First, we analyze the natural curve $\mbox{FF}_v$ that develops when the fighter keeps building, at speed $v$ , a barrier along the boundary of the expanding fire. We prove that the behavior of this spiralling curve is governed by a complex function $(e^{w Z} - s \, Z)^{-1}$ , where $w$ and $s$ are real functions of $v$ . For $v>v_c=2.6144 \ldots$ all zeroes are complex conjugate pairs. If $ϕ$ denotes the complex argument of the conjugate pair nearest to the origin then, by residue calculus, the fire fighter needs $Θ( 1/ϕ)$ rounds before the fire is contained. As $v$ decreases towards $v_c$ these two zeroes merge into a real one, so that argument $ϕ$ goes to~0. Thus, curve $\mbox{FF}_v$ does not contain the fire if the fighter moves at speed $v=v_c$ . (That speed $v>v_c$ is sufficient for containing the fire has been proposed before by Bressan et al. [7], who constructed a sequence of logarithmic spiral segments that stay strictly away from the fire.) Second, we show that any curve that visits the four coordinate half-axes in cyclic order, and in inreasing distances from the origin, needs speed $v>1.618\ldots$ , the golden ratio, in order to contain the fire. Keywords: Motion Planning, Dynamic Environments, Spiralling strategies, Lower and upper bounds

preprint2015arXiv

A local strategy for cleaning expanding cellular domains by simple robots

We present a strategy SEP for finite state machines tasked with cleaning a cellular environment in which a contamination spreads. Initially, the contaminated area is of height $h$ and width $w$ . It may be bounded by four monotonic chains, and contain rectangular holes. The robot does not know the initial contamination, sensing only the eight cells in its neighborhood. It moves from cell to cell, $d$ times faster than the contamination spreads, and is able to clean its current cell. A speed of $d<\sqrt{2}(h+w)$ is in general not sufficient to contain the contamination. Our strategy SEP succeeds if $d \geq 3(h+w)$ holds. It ensures that the contaminated cells stay connected. Greedy strategies violating this principle need speed at least $d \geq 4(h+w)$ ; all bounds are up to small additive constants.

preprint2012arXiv

A New Upper Bound for the VC-Dimension of Visibility Regions

In this paper we are proving the following fact. Let P be an arbitrary simple polygon, and let S be an arbitrary set of 15 points inside P. Then there exists a subset T of S that is not "visually discernible", that is, T is not equal to the intersection of S with the visibility region vis(v) of any point v in P. In other words, the VC-dimension d of visibility regions in a simple polygon cannot exceed 14. Since Valtr proved in 1998 that d \in [6,23] holds, no progress has been made on this bound. By epsilon-net theorems our reduction immediately implies a smaller upper bound to the number of guards needed to cover P.

preprint2010arXiv

Exploring Grid Polygons Online

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 adjacent cells exist and which are boundary edges. The robot starts from a specified cell adjacent to the room's outer wall; it visits each cell, and returns to the start. Our interest is in a short exploration tour; that is, in keeping the number of multiple cell visits small. For abitrary environments containing no obstacles we provide a strategy producing tours of length S <= C + 1/2 E - 3, and for environments containing obstacles we provide a strategy, that is bound by S <= C + 1/2 E + 3H + WCW - 2, where C denotes the number of cells-the area-, E denotes the number of boundary edges-the perimeter-, and H is the number of obstacles, and WCW is a measure for the sinuosity of the given environment.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Rolf Klein

Research overview

Is this your work?

5 publications

The limit of $L_p$ Voronoi diagrams as $p \rightarrow 0$ is the bounding-box-area Voronoi diagram

A Fire Fighter's Problem

A local strategy for cleaning expanding cellular domains by simple robots

A New Upper Bound for the VC-Dimension of Visibility Regions

Exploring Grid Polygons Online

See the researcher in context

Building this map preview

Rolf Klein

Research overview

Is this your work?

5 publications

The limit of LpL_pLp​ Voronoi diagrams as p→0p \rightarrow 0p→0 is the bounding-box-area Voronoi diagram

A Fire Fighter's Problem

A local strategy for cleaning expanding cellular domains by simple robots

A New Upper Bound for the VC-Dimension of Visibility Regions

Exploring Grid Polygons Online

See the researcher in context

Building this map preview

The limit of $L_p$ Voronoi diagrams as $p \rightarrow 0$ is the bounding-box-area Voronoi diagram