RKRolf Klein
Rolf Klein
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Rolf Klein has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Andrzej Lingas
Department of Computer Science Lund University Lund Sweden
3 shared publications Cecilia Bohler
University of Bonn
2 shared publications- Chih-Hung Liu
National Taiwan University, Taipei, Taiwan
2 shared publications Christian Icking
Fernuniversität Hagen
2 shared publications- Christian Knauer
Freie Universität Berlin
2 shared publications - Christos Levcopoulos
Lund University
2 shared publications
Latest Publications
- 18 December 2018
- Published by Springer Nature in Algorithmica
- Vol. 81 (6) , 2317-2345
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
- 18 December 2018
- Published by Springer Nature in Algorithmica
- Vol. 81 (6) , 2317-2345
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
- Open Access
- 11 April 2018
- Published by MDPI AG in Algorithms
- Vol. 11 (4) , 45
Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in , we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.- 11 April 2018
- Published by MDPI AG in Algorithms
- Vol. 11 (4) , 45
Open AccessApproximation Algorithms for the Geometric Firefighter and Budget Fence Problems
Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in , we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross. - 1 March 2018
- Published by Elsevier in Computational Geometry
- Vol. 68, 134-145
Forest-like abstract Voronoi diagrams in linear time
- 1 March 2018
- Published by Elsevier in Computational Geometry
- Vol. 68, 134-145
Forest-like abstract Voronoi diagrams in linear time
- 1 January 2018
- Published by Elsevier in Computational Geometry
- Vol. 67, 38-41
Reversibility properties of the fire-fighting problem in graphs
- 1 January 2018
- Published by Elsevier in Computational Geometry
- Vol. 67, 38-41
Reversibility properties of the fire-fighting problem in graphs
- 22 April 2016
- Published by Springer Nature
- p. 547-549
Dilation of Geometric Networks
- 22 April 2016
- Published by Springer Nature
- p. 834-837
Geometric Dilation of Geometric Networks
- 22 April 2016
- Published by Springer Nature
- p. 2368-2371
Well Separated Pair Decomposition
- Open Access
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.Open AccessA 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.