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...
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...
Rheinische Friedrich-Wilhelms-Universität Bonn (2008)
Informatik Hauptseminar Ws, Dr. Elmar Langetepe, Ansgar Grüne, Sören Kühl, Das Leasing-problem
ein Überblick über das Leasing Problem gegeben. Dieses wurde von R. El-Yaniv, R. Kaniel
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,...
Improved Lower Bound on the Geometric Dilation of Point Sets (2008)
Adrian Dumitrescu Ansgar, Adrian Dumitrescu, Ansgar Grüne, 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 length of a shortest path connecting p and q in G divided by their...
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...
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...
Improved lower bound on the geometric dilation of point sets (2005)
Adrian Dumitrescu, Ansgar Grüne, 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 length of a shortest path connecting p and q in G divided by their...
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...
On the Density of Iterated Line Segment Intersections (2005)
Ansgar Grüne, Sanaz Kamali Sarvestani
Given S1 , a finite set of points in the plane, we define a sequence of point sets S i as follows: With S i already determined, let L i be the set of all the line segments connecting pairs of points...
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...
On the Density of Iterated Line Segment Intersections (2005)
Ansgar Grüne, Sanaz Kamali Sarvestani
Given S1, a finite set of points in the plane, we define a sequence of point sets Si as follows: With Si already determined, let Li be the set of all the line segments connecting pairs of points of...
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...
On the Density of Iterated Line Segment Intersections (2005)
Ansgar Grüne, Sanaz Kamali Sarvestani
Given S1, a finite set of points in the plane, we define a sequence of point sets Si as follows: With Si already determined, let Li be the set of all the line segments connecting pairs of points 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...
On the geometric dilation of curves and point sets (2004)
Adrian Dumitrescu, Ansgar Grüne, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points u and v (on edges or vertices) of G is the ratio between the shortest path in G between u and v and their...
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...