Fixed-parameter tractability and lower bounds for stabbing problems (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the...
Fixed-parameter tractability and lower bounds for stabbing problems (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the...
The parameterized complexity of some geometric problems in unbounded dimension (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$: i) Given $n$ points in $\Rd$, compute their minimum enclosing cylinder. ii)...
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Gunter Rote, Triangulations Intersect Nicely, Oswin Aichholzer, Oswin Aichholzer, ...
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Volker Kaibel, Gunter Rote, Bericht Nr, Endgultige Fassung Janner
We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d \Gamma 1)! + 2(d \Gamma 1) (which is the best one currently known for small...
Jerrold R. Griggs, Gunter Rote
Abstract. An analogue of the Littlewood-O#ord problem posed by the first author is to find the maximum number of subset sums equal to the same vector over all ways of selecting n vectors in R d in...
Expansive motions and the polytope of pointed pseudo-triangulations (2003)
Gunter Rote, Francisco Santos, Ileana Streinu
We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the...
Triangles of extremal area or perimeter in a finite planar point set. (2001)
Brass, Peter, Rote, Gunter, Swanepoel, Konrad
We show the following two results on a set of n points in the plane, thus answering questions posed by Erdos and Purdy [11]: 1. The maximum number of triangles of maximum area (or of maximum...
Counting triangulations and pseudo-triangulations of wheels (2001)
Dana Randall, Gunter Rote, Francisco Santos, Jack Snoeyink
Motivated by several open questions on triangulations and pseudotriangulations, we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n...
Counting triangulations and pseudo-triangulations of wheels (2001)
Dana Randall, Gunter Rote, Francisco Santos, Jack Snoeyink
Motivated by several open questions on triangulations and pseudotriangulations, we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n...
Straightening polygonal arcs and convexifying polygonal cycles (2000)
Robert Connelly, Erik D. Demaine, Gunter Rote
Consider a planar linkage, consisting of disjoint polygonal arcs and cycles of rigid bars joined at incident endpoints (polygonal chains), with the property that no cycle surrounds another arc or...
The Obnoxious Center Problem on a Tree (1998)
Rainer E. Burkard, Yixun Lin, Gunter Rote
Abstract. The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as...
The Obnoxious Center Problem on a Tree (1998)
Diskrete Optimierung, Rainer E. Burkard, Rainer E. Burkard, Helidon Dollani, Helidon Dollani, Yixun Lin, ...
The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We...
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 '...
Angewandte Mathematik und Informatik Universit at zu K oln (1997)
Report No On, Hazel Everett, Hazel Everett, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...
Matching Convex Shapes with Respect to the Symmetric Difference (1997)
Helmut Alt, Ulrich Fuchs, Ulrich Fuchs, Günter Rote, Gunter Rote, Gerald Weber, ...
This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of moving one convex figure over another, minimizing the area of their symmetric...
On a Visibility Representation of Graphs in 3D (1997)
Prosenjit Bose, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...
Janusz Januszewski, Marek Lassak, Gunter Rote, Gerhard Woeginger
Abstract. We prove that in Euclidean d-space every sequence of cubes with total volume 2 d +3is able to cover on-line the unit cube. The proof is based on an on-line q-adic method of covering the...
Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling (1996)
Günter Rote, Gunter Rote, Guochuan Zhang, Guochuan Zhang, Projektbereich Diskrete Optimierung
We consider a variant of the classical jeep problem. We have n cans of fuel on the edge of a desert and a jeep with an empty tank whose capacity is just one can. The jeep can carry one can in...
The N-line Traveling Salesman Problem (1991)
The special case of the Euclidean Traveling Salesman Problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time...
Approximation of Convex Figures by Pairs of Rectangles (1990)
Otfried Schwarzkopf Ulrich, Ulrich Fuchs, Gunter Rote, Emo Welzl
We consider the problem of approximating a convex figure in the plane by a pair (r; R) of homothetic (that is, similar and parallel) rectangles with r ` C ` R. We show the existence of such a pair...