Günter Rote  List of Scientific Papers
with abstracts where available; more recent papers first.
The publication data may not always be up to date,
and some papers that are listed below as manuscripts or to appear
may already have appeared.
Check the
publication list
by following the links from the paper titles
for the most complete and uptodate information, including
the online original versions by the publishers, and a link to a BibTeX entry which you can copy directly.
→ Next
Previous ← → Next
Günter Rote:
To appear in:
Proceedings of the 2nd Symposium on Simplicity
in Algorithms
(SOSA2019), San Diego, January 2019, Editors: Jeremy Fineman and
Michael Mitzenmacher,
OpenAccess Series in
Informatics (OASIcs), Schloss DagstuhlLeibnizZentrum für
Informatik, 2019,
pp. 1:1–1:18
doi:10.4230/OASIcs.SOSA.2019.1
→BibTeX
Abstract
For a given sequence of n numbers, we want to find a monotonically increasing
sequence of the same length that best approximates it in the sense of
minimizing the weighted sum of absolute values of the differences. A
conceptually easy dynamic programming approach leads to an algorithm with
running time O(n log n).
While other algorithms with the
same running time are known, our algorithm is very simple. The only auxiliary
data structure that it requires is a priority queue. The approach extends to
other error measures.
Previous ← → Next
Günter Rote:
to appear in:
Proceedings of the 30th Annual ACMSIAM Symposium on
Discrete Algorithms (SODA19), San Diego, January 2019, Editor: Timothy Chan.
→BibTeX
Abstract
A tree with n vertices has at most
95^{n/13}
minimal dominating sets. The growth constant
λ=95^{1/13} ≈ 1.4194908 is best possible. It is obtained
in a semiautomatic way as a kind of "dominant eigenvalue" of a bilinear
operation on sixtuples that is derived from the dynamicprogramming recursion
for computing the number of minimal dominating sets of a tree. We also
derive an outputsensitive algorithm for listing all minimal dominating sets
with linear setup time and linear delay between successive solutions.
Previous ← → Next
Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and
Günter Rote:
to appear in:
Proceedings of the 30th Annual ACMSIAM Symposium
on Discrete Algorithms (SODA19), San Diego, January 2019. arXiv:1811.03432 [math.CO].
→BibTeX
Abstract
We show that if a planar graph G has a plane straightline drawing
in which a subset S of its vertices are collinear, then for any
set X of points
in the plane with X = S, there is
a plane straightline drawing of G in which the vertices in
S are mapped to the points in X. This solves an open
problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show
that every collinear set is free.
This result has applications in graph drawing, including untangling, column
planarity, universal point subsets, and partial simultaneous drawings.
Previous ← → Next
Pankaj Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote,
Micha Sharir, and Allen Xiao:
To appear in: "Algorithms and Computation—29th Annual International
Symposium on Algorithms and Computation. Jiaoxi, Yilan, Taiwan, December 2018".
Proceedings of ISAAC'18.
→BibTeX
Abstract
Our goal is to compare two planar point sets by finding subsets of a given
size such that a minimumweight matching between them has the smallest weight.
This can be done by a translation of one set that minimizes the weight of
the matching. We give efficient algorithms
 for finding approximately
optimal matchings, when the cost of a matching is the L_{p}norm of
the tuple of the Euclidean distances between the pairs of matched points, for
any p≥1, including p=infinity, and
 for constructing
smallsize approximate minimization (or matching) diagrams: partitions of the
translation space into regions, together with an approximate optimal matching
for each region.
Previous ← → Next
Günter Rote:
In: Oberwolfach Reports, Vol. 14, European Mathematical Society 
Publishing House, 2017, pp. 1180–1182.
doi:10.4171/OWR/2017/19
→BibTeX
Abstract
We consider the problem of sandwiching a polytope Δ
with a given number k of vertices between two nested polytopes
P and Q in d dimensions. The polytope
P is not necessarily fulldimensional.
Besides the question of (a) computing Δ, we study
the following question: (b) Assuming that the given polytopes P
and Q are rational polytopes (polytopes with rational vertex
coordinates), does it suffice to look for Δ among the
rational polytopes?
This problem has several applications: (1) When Q is a dilation of
P (or an offset of P), Δ can
serve as a thrifty approximation of P. (2) The polytope nesting
problem can model the nonnegative rank of a matrix, and thereby the extension
complexity of polytopes, as well as other problems in statistics and
communication complexity. It was in this context that question (b) was
first asked.
Previous ← → Next
Stefan Felsner and Günter Rote:
In: Abstracts of the 34th European Workshop on Computational Geometry
(EuroCG 2018), Berlin, March 2018, pp. 72:1–72:6.
→BibTeX
Abstract
The KoebeAndreevThurston Circle Packing Theorem states that every triangulated
planar graph has a circlecontact representation. The theorem has been
generalized in various ways. The arguably most prominent generalization assures
the existence of a primaldual circle representation for every 3connected
planar graph. The aim of this note is to give a streamlined proof of this
result.
Previous ← → Next
JeanPhilippe Labbé, Günter Rote, and Günter M. Ziegler:
Preprint, August 2017, 29 pages, arXiv:1708.02891 [math.MG].
Abstract
Monsky's theorem from 1970 states that a square cannot be dissected into an
odd number of triangles of the same area, but it does not give a lower
bound for the area differences that must occur.
We extend Monsky's theorem to constrained framed maps; based on this we
can apply a gap theorem from semialgebraic geometry to a polynomial area
difference measure and thus get a lower bound for the area differences that
decreases doublyexponentially with the number of triangles. On the other hand,
we obtain the first superpolynomial upper bounds for this problem, derived
from an explicit construction that uses the Thue–Morse sequence.
Previous ← → Next
Boris Klemz and Günter Rote:
Manuscript, November 2017, 14 pages, arXiv:1711.04496 [cs.DS].
Abstract
A bipartite graph G=(U,V,E) is convex if the vertices in
V can be linearly ordered such that for each
vertex u in U,
the neighbors of u are consecutive in the ordering of V.
An induced matching H of G is a matching such
that no edge of E connects endpoints of two different edges of
H.
We show that in a convex bipartite graph with n vertices and
m weighted edges, an induced matching of maximum total
weight can be computed in optimal O(n+m) time.
An unweighted convex bipartite graph has a representation of size
O(n) that records for each
vertex u in U the first and last
neighbor in the ordering of V. Given such a compact representation, we compute
an induced matching of maximum cardinality in O(n) time.
In convex bipartite graphs, maximumcardinality induced matchings are dual to
minimum chain covers. A chain cover is a covering of the edge set by chain
subgraphs, that is, subgraphs that do not contain induced matchings of more
than one edge. Given a compact representation, we compute a representation of
a minimum chain cover in O(n) time. If no compact representation is
given, the cover can be computed in O(n+m) time.
The best previous algorithms for computing a maximumcardinality induced
matching or a minimum chain cover had a running time of O(n^{2}).
Previous ← → Next
Boris Klemz and Günter Rote:

Ordered level planarity and geodesic planarity.
In: Proceedings of the 33rd European Workshop on Computational Geometry
(EuroCG 2017), Malmö, Sweden, April 2017, pp. 269–272.

to appear in: "Graph Drawing and Network Visualization". GD 2017,
Proceedings of the 25th International Symposium on Graph Drawing and
Network Visualization, Boston, September 2017, Revised Selected Papers.
Editors: Frabrizio Frati and KwanLiu Ma, Lecture Notes in Computer
Science, SpringerVerlag, 2017, 14 pages.
 Full version in arXiv:1708.07428 [cs.CG],
25 pages.
Abstract
We introduce and study the problem Ordered Level Planarity, which
asks for a planar drawing of a graph such that vertices are placed at
prescribed positions in the plane and such that every edge is realized as a
ymonotone curve. This can be interpreted as a variant of Level
Planarity in which the vertices on each level appear in a prescribed
total order. We show NPcompleteness even for the special case that the
number of vertices on each level is bounded by 2 and that the maximum
degree is 2. This establishes a tight border of tractability, since the
problem is easy if there is at most one vertex per level.
Our result has applications to other problems, such as TLevel
Planarity, Clustered Level Planarity, and Constrained Level
Planarity. We strengthen previous hardness results and solve open questions
that were posed by Fulek, Pelsmajer, Schaefer and Štefankovič (2015)
and by Angelini, Da Lozzo, Di Battista, Frati and Roselli (2013). In
particular, our result implies that a published polynomial algorithm by Katz,
Krug, Rutter and Wolff (GD'09) for Manhattan Geodesic Planarity is
incorrect unless P=NP.
Previous ← → Next
Pavle V. M. Blagojević, Günter Rote, Johanna K. Steinmeyer, and
Günter M. Ziegler:
Manuscript, May 2017, 7 pages, arXiv:1705.03953 [math.CO].
Abstract
We show that any dcolored set of points in general position in
d dimensions can be partitioned into n subsets with
disjoint convex hulls such that the set of points and all color classes are
partitioned as evenly as possible. This extends results by Holmsen, Kynčl, and
Valculescu (2017) and establishes a central case of their general conjecture.
Our proof utilizes a result of Soberón (2012) on simultaneous
equipartitions of d continuous measures in dspace by
n convex regions, which gives a convex partition with the desired
properties, except that points may lie on the boundaries of the regions. In
order to resolve the ambiguous assignment of these points, we set up a
network flow problem. The equipartition of the continuous measures gives a
fractional flow. The existence of an integer flow then yields the desired
partition of the point set.
Previous ← → Next
Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter
Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber:
In: 27th International Symposium on Algorithms and Computation
(ISAAC 2016), Editor: SeokHee Hong. Leibniz International Proceedings
in Informatics (LIPIcs), Schloss DagstuhlLeibnizZentrum für
Informatik, 2016, Vol. 64, pp. 9:1–9:12.
doi:10.4230/LIPIcs.ISAAC.2016.9.
Abstract
Given a set of points in the plane, we want to establish a connection
network between these points that consists of several disjoint layers.
Motivated by sensor networks, we want that each layer is spanning and plane,
and that no edge is very long, when compared to the minimum length needed
to obtain a spanning graph. We consider two different approaches: first we
show an almost optimal centralized approach to extract two trees. Then we
show a constant factor approximation for a distributed model in which each
point can compute its adjacencies using only local information. This second
approach may create cycles, but maintains planarity.
Previous ← → Next
Felix Herter and Günter Rote:
 In:
Proceedings of the 8th International Conference on Fun
with Algorithms (FUN 2016). La Maddalena, Italy, June 8–10, 2016.
Editors: Erik D. Demaine and Fabrizio Grandoni, Leibniz International
Proceedings in Informatics (LIPIcs), Schloss DagstuhlLeibnizZentrum
für Informatik, 2016, Vol. 49, pp. 19:1–19:18. doi:10.4230/LIPIcs.FUN.2016.19.
 Preprint
arXiv:1604.06707, April 2016.
[cs.DM].
 Revised and extended version, to appear in Theoretical
Computer Science,
special issue for FUN'2016.
Abstract
We give new algorithms for generating all ntuples over an alphabet
of m letters, changing only one letter at a time (Gray codes).
These algorithms are based on the connection with variations of the Towers of
Hanoi game. Our algorithms are loopless, in the sense that the next change
can be determined in a constant number of steps, and they can be implemented
in hardware. We also give another family of loopless algorithms that is based
on the idea of working ahead and saving the work in a buffer.
The appendix of the conference version (1.) contains, as additional material, prototype
simulations of the most important algorithms in the programming language Python.
The appendix of the arXiv preprint (2.) contains
simulations of all algorithms of the paper. Program source
code is contained with the source files of the paper.
The journal version (3.) contains several additional sections that discuss the
results in a larger context.
See Note on the python programs in the appendix
Previous ← → Next
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis
Thomas, and Takeaki Uno:
In: "Algorithms—ESA 2016", Proc. 24th
Annual European Symposium on Algorithms, Aarhus, 2016. Editors:
Piotr Sankowski and Christos Zaroliagis. Leibniz International
Proceedings in Informatics (LIPIcs), Schloss DagstuhlLeibnizZentrum
für Informatik, 2016, pp. 185:1–185:15. doi:10.4230/LIPIcs.ESA.2016.185,
arXiv:1602.05150 [cs.CC]
Abstract
We are given a graph with n vertices
V={1,…,n}. On each
vertex, a distict token from the set
{T_{1},…,T_{n}}
is placed.
A swap is an exchange of tokens between adjacent vertices. We consider the
algorithmic question of finding a shortest sequence of swaps such that
each token
T_{i}
is on vertex i. We are able to achieve essentially
matching upper and lower bounds, for exact algorithms and approximation
algorithms. For exact algorithms, we rule out
2^{o(n)} algorithms
under
the Exponential Time Hypothesis
(ETH). This is matched with a simple 2^{O(n
log n)}
algorithm based on exploring the state space. We give a general
4approximation algorithm and show APXhardness. Thus, there is a
constant δ>1 such that every polynomialtime approximation algorithm
has approximation factor at least δ.
Our results also hold for a generalized version, where tokens and vertices
are colored. In this generalized version each token must go to a vertex with
the same color.
Previous ← → Next
Heuna Kim and Günter Rote:
to appear in:
32st International Symposium on Computational
Geometry (SoCG 2016), Boston, June 2016. Editors: Sándor
Fekete and Anna Lubiw, Leibniz International Proceedings in
Informatics (LIPIcs), Schloss DagstuhlLeibnizZentrum für
Informatik, 2016. pp. 48:1–48:15. doi:10.4230/LIPIcs.SOCG.2016.48
Manuscript, March 2016, 41 pages, arXiv:1603.07269 [cs.CC].
Abstract
We give a deterministic
O(n log n)time algorithm to
decide
if two npoint sets in 4dimensional Euclidean space are the same
up to rotations and translations.
A lower bound of Ω(n log n)
has been
known, and it has been conjectured that O(n log n)
algorithms should exist for any fixed dimension. The best algorithms in
dspace so far are are a deterministic algorithm by Brass
and Knauer (2000) and a randomized Monte Carlo algorithm by Akutsu
(1998). In 4space, they take time
O(n^{2}log n) and
O(n^{3/2}log n),
respectively.
Our algorithm exploits the
geometric structure and the properties of 4dimensional space, such as angles
between planes, packing numbers, Hopf fibrations, Plücker coordinates, the
classification of Coxeter groups, and rotations in 4space.
Previous ← → Next
Günter Rote:
Invited talk.
In: Sixth International Conference on Mathematical Aspects of Computer
and Information Sciences—MACIS 2015, November 2015, Editors: Ilias
S. Kotsireas, Siegfried Rump, and Chee Yap, Lecture Notes in Computer
Science, Vol. 9582, SpringerVerlag, 2016, pp. 50–59. doi:10.1007/9783319328591_4
Abstract
I will survey algorithms for testing whether two point sets are congruent,
that is, equal up to an Euclidean isometry. I will introduce the important
techniques for congruence testing, namely dimension reduction and pruning, or
more generally, condensation. I will illustrate these techniques on the
threedimensional version of the problem, and indicate how they lead for the
first time to an algorithm for four dimensions with nearlinear running time
(joint work with Heuna Kim). On the way, we will encounter some beautiful
and symmetric mathematical structures, like the regular polytopes, and
Hopffibrations of the threedimensional sphere in four dimensions.
Previous ← → Next
Dror Atariah, Günter Rote, and Mathijs Wintraecken:
Beiträge zur Algebra und Geometrie—Contributions to Algebra
and Geometry 59, no. 1 (2018), 113–126. doi:10.1007/s1336601703519,
arXiv:1511.01361 [math.MG].
Abstract
We consider the piecewise linear approximation of saddle functions of the form
f(x,y)
= ax^{2}by^{2}
under the L_{infinity} error norm. We show that
interpolating approximations are not optimal. One can get slightly smaller
errors by allowing the vertices of the approximation to move away from the
graph of the function.
Previous ← → Next
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di
Donato, Philipp Kindermann, Günter Rote, and Ignaz Rutter:
 In: Proceedings of the 27th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA16), San
Francisco, January 2016, pp. 985–996.
doi:10.1137/1.9781611974331.ch70. →BibTeX

ACM Transactions on Algorithms 14 (September 2018),
Article 54, pp. 54:1–54:24. doi:10.1145/3239561 arXiv:1510.02659 [cs.CG].
→BibTeX
Abstract
Windrose planarity asks for planar drawings of a graph, where every edge is
monotone both in in the x and the ydirection. Moreover,
for each edge uv it is specified in which quadrant (NE, NW, SW, or
SE) v lies relative to u. While the wellknown notion of
upward planarity can be used to visualize a partial order, windrose planarity
simultaneously visualize two partial orders defined by the edges of the same
graph by exploiting both the horizontal and the vertical relationship among
vertices.
Testing whether there exists a windroseplanar drawing is NPhard in the
general case. We give a polynomialtime algorithm for the case when the
desired combinatorial embedding is specified as part of the input. This
algorithm is based on a characterization of the plane triangulations admitting
a windroseplanar drawing. Furthermore, for any embedded graph admitting a
windroseplanar drawing we show how to construct one with at most one bend
per edge on
an O(n)×O(n)
grid. This contrasts with
the fact that straightline windroseplanar drawings may require exponential
area.
Previous ← → Next
Péter Hajnal, Alexander Igamberdiev, Günter Rote, and André
Schulz:

In:
41st International Workshop on GraphTheoretic Concepts in
Computer Science—WG 2015, Garching, Germany, June 2015, Revised
Papers. Editor: Ernst Mayr, Lecture Notes in Computer Science,
9224, SpringerVerlag, 2016, pp. 391–405.
doi:10.1007/9783662531747_28,
arXiv:1503.01386 [cs.CG].
→BibTeX

Journal of Graph Algorithms and
Applications 22, no. 1 (2017), pp. 117–138, special
issue on "Graph Drawing Beyond Planarity". doi:10.7155/jgaa.00460
→BibTeX
Abstract
A simple topological graph is a topological graph in which any two
edges have at most one common point, which is either a common endpoint or a
proper crossing. More generally, in a ksimple topological
graph, every pair of edges has at most k common points of this
kind. We construct saturated simple and 2simple graphs with few
edges. These are ksimple graphs in which no further edge can be
added. We improve the previous bounds of Kynčl, Pach, Radoičić,
and Tóth (2013) and show that there are saturated simple
graphs
on n vertices with 7n edges and saturated 2simple
graphs on n vertices with 14.5n edges. As a
consequence, 14.5n edges is also a new upper bound for
ksimple graphs (considering all values of k). We also
construct saturated simple and 2simple graphs that have some vertices with
low degree.
Previous ← → Next
Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell,
Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie:

Journal of Computational Geometry
7 (2016), 77–100. Special issue for the 31st International
Symposium on Computational Geometry (SoCG 2015).
doi:10.20382/jocg.v7i2a5

In: 31st International Symposium on Computational Geometry (SoCG 2015),
Eindhoven, June 2015. Editors: Lars Arge and János Pach, Leibniz
International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–LeibnizZentrum
für Informatik, 2015, pp. 658–673.
doi:10.4230/LIPIcs.SOCG.2015.658

Christian Knauer, Günter Rote, and Lena Schlipf:
Shortest inspectionpath queries in simple polygons.
In: Abstracts of the 24th European Workshop on
Computational Geometry, Nancy, March 2008, pp. 153–156.
(preliminary version of partial results from 1 and 2.)
pdf
file
Abstract
We show how to preprocess a polygonal domain with a fixed starting point
s in order to answer efficiently the following queries: Given
a point q, how should one move from s in order to
see q as soon as possible? This query resembles the
wellknown shortestpathtoapoint query, except that the latter asks for
the fastest way to reach q, instead of seeing it. Our
solution methods include a data structure for a different generalization of
shortestpathtoapoint queries, which may be of independent interest: to
report efficiently a shortest path from s to a query segment
in the domain.
Topi Talvitie has provided an
interactive
visualization of the visibility map for the problem.
Previous ← → Next
Andrei Asinowski and Günter Rote:
Computational Geometry, Theory and
Applications 68 (2018), 7–33. doi:10.1016/j.comgeo.2017.05.006,
arXiv:1502.04925 [cs.CG].
Abstract
The maximum number of noncrossing straightline perfect matchings that
a set of n points in the plane can have is known to
be O(10.0438^{n})
and
Ω^{*}(3^{n}), where the
Ω^{*} notation hides polynomial factors in the aymptotic
expression. The lower bound, due to García, Noy, and Tejel (2000), is
attained by the double chain, which has
Θ(3^{n}/n^{Θ(1)})
such matchings. We reprove this bound in a simplified way that uses the
novel notion of downfree matchings. We then apply this approach to
several other constructions. As a result, we improve the lower bound:
First we show that the double zigzag chain with n points has
Θ^{*}(λ^{n}) noncrossing perfect
matchings with λ≈3.0532. Next we analyze
further generalizations of double zigzag chains: double rchains.
The best choice of parameters leads to a construction that has
Θ^{*}(μ^{n}) noncrossing perfect
matchings with μ≈3.0930. The derivation
of this bound requires an analysis of a coupled dynamicprogramming recursion
between two infinite vectors.
Moral: Don't count your boobies until they are hatched matched.
Previous ← → Next
Dániel Gerbner, Balázs Keszegh, Dömötör
Pálvölgyi, Günter Rote, and Gábor Wiener:
Ars
Mathematica Contemporanea 12 (no. 2) (2017), 301–314.
Abstract
We consider the worstcase query complexity of some variants of certain
PPADcomplete search problems. Suppose we are given a graph G and a
vertex s in G. We denote the directed graph obtained from
G by directing all edges in both directions by G'.
D is a directed subgraph of G'
which is unknown to us,
except that it consists of vertexdisjoint directed paths and cycles and one
of the paths originates in s. Our goal is to find an endvertex of
a path by using as few queries as possible. A query specifies a vertex
v in G and the answer is the set of the edges of
D incident to v, together with their directions.
We also show lower bounds for the special case when D consists of
a single path. Our proofs use the theory of graph separators. Finally, we
consider the case when the graph G is a grid graph. In this case,
using the connection with separators, we give asymptotically tight bounds as a
function of the size of the grid, if the dimension of the grid is
considered as fixed. For this, we prove a separator theorem about grid
graphs, which is interesting on its own right.
Previous ← → Next
Oswin Aichholzer, Michael Hoffmann, Marc van Kreveld, and Günter
Rote:
In:
Proceedings of
the 26th Canadian Conference on Computational Geometry,
(CCCG'2014), Halifax, August
2014, 7 pages.
Abstract
We study plane straightline embeddings of graphs where certain edges are
specified to be longer than other edges. We analyze which graphs are
universal in the sense that they allow a plane embedding for any total
strict order on the edge lengths. In addition, we also briefly consider
circular arc drawings with relative edge length specifications.
Previous ← → Next
Michael Hoffmann, Marc van Kreveld, Vincent Kusters, and Günter
Rote:
In: Proceedings of
the 26th Canadian Conference on Computational Geometry, (CCCG'2014), Halifax,
August 2014, 7 pages.
Abstract
When comparing two different styles to draw a graph, one can wonder how much
better or worse one style can be than another one, in the worst case,
for some quality measure. We compare planar straightline drawings with
fixed and free embeddings, planar circular arc drawings, and nonplanar
straightline drawings, and consider the quality measures angular resolution,
area requirement, edge length ratio, and feature resolution.
Previous ← → Next
Gill Barequet, Günter Rote, and Mira Shalah:

Extended abstract in:
Abstracts of the 30th European Workshop on Computational Geometry
(EuroCG'14), EinGedi, Israel, March 2014, Editors: Paz Carmi, Matthew Katz,
and Shakhar Smorodinsky, 4 pages.

In: "Algorithms—ESA 2015", Proc. 23rd Annual European
Symposium on Algorithms, Patras, 2015. Editors: Nikhil Bansal
and Irene Finocchi. Lecture Notes in Computer Science, Vol. 9294,
SpringerVerlag, 2015, pp. 83–94.
doi:10.1007/9783662483503_8
 Communications of the ACM 59, No. 7,
July 2016, 88–95.
doi:10.1145/2851485,
free PDF @ACM
Abstract
A polyomino (or lattice animal) is an edgeconnected set of squares on
the twodimensional square lattice. Counting polyominoes is an extremely hard
problem in enumerative combinatorics, with important applications in statistical
physics for modeling processes of percolation and collapse of branched
polymers. We investigated a fundamental question related to polyominoes, namely,
what is their growth constant, the asymptotic ratio between A(n + 1)
and A(n) when n goes to infinity, where A(n) is the number of
polyominoes of size n. This value is also known as "Klarner's
constant" and denoted by λ. So far, the best lower
and upper bounds on λ were roughly 3.98
and 4.65, respectively, and so not even a single decimal digit of
λ was known. Using extremely high computing resources,
we have shown (still rigorously) that λ>4.00253,
thereby settling a longstanding problem: proving that the leading digit of
λ is 4.
Previous ← → Next
Günter Rote:
In: Abstracts of the 30th European Workshop on Computational Geometry
(EuroCG'14), EinGedi, Israel, March 2014, Editors: Paz Carmi, Matthew Katz,
and Shakhar Smorodinsky, 4 pages.
Abstract
The Fréchet distance between two curves is the maximum distance in a
simultaneous traversal of the two curves. We refine this notion by not only
looking at the maximum distance but at all other distances. Roughly speaking,
we want to minimize the time T(s)
during which the distance exceeds
a threshold s, subject to upper speed constraints. We optimize these
times lexicographically, giving more weight to larger distances s.
For polygonal curves in general position, this criterion produces a unique
monotone matching between the points on the two curves, which is important
for applications like morphing, and we can compute this matching in polynomial
time.
Previous ← → Next
Rafel Jaume and Günter Rote:
Journal of Computational
Geometry
7
(2016), 185–220.
doi:10.20382/jocg.v7i1a10,
arXiv:1310.4372
[cs.CG].
Abstract
We generalize regular subdivisions (polyhedral complexes resulting from the
projection of the lower faces of a polyhedron) introducing the class of
recursivelyregular subdivisions. Informally, a recursivelyregular
subdivision is a subdivision that can be obtained by splitting some faces
of a regular subdivision by other regular subdivisions (and continuing
recursively). We also define the finest regular coarsening and
the regularity tree of a polyhedral complex. We prove that
recursivelyregular subdivisions are not necessarily connected by flips and that
they are acyclic with respect to the infront relation. We show that the
finest regular coarsening of a subdivision can be efficiently computed, and
that whether a subdivision is recursively regular can be efficiently decided.
As an application, we also extend a theorem known since 1981 on illuminating
space by cones and present connections of recursive regularity to tensegrity
theory and graphembedding problems.
Previous ← → Next
Dror Atariah, Sunayana Ghosh, and Günter Rote:
Journal of WSCG 21 (2013), 11–20.
Papers from the 21st International Conference on Computer Graphics,
Visualization and Computer Vision, Plzeń, Czech Republic, June 24–27,
2013.
Abstract
We study the configuration space of a planar polygonal robot translating
and rotating among polygonal obstacles in the plane. We give explicit
parameterizations of the boundary of the forbidden space, and we study
geometrical and differentialgeometric properties of the various elements which
constitute this boundary.
Previous ← → Next
Tristram Bogart, Christian Haase, Milena Hering, Benjamin Lorenz, Benjamin
Nill, Andreas Paffenholz, Günter Rote, Francisco Santos, and Hal
Schenck:
Israel Journal of Mathematics 207 (2015), 301–329.
doi:10.1007/s1185601511757,
arXiv:1010.3887 [math.CO].
Abstract
We prove that for fixed d and n, there are only finitely
many smooth ddimensional polytopes which contain n lattice
points. As a consequence in algebraic geometry, we obtain that for fixed
n, there are only finitely many embeddings of Qfactorial
toric varieties into ndimensional projective
space P^{n} that are induced by a complete
linear system. We also enumerate all smooth 3polytopes with at most 12
lattice points.
Previous ← → Next
Michael Hoffmann, Vincent Kusters, Günter Rote, Maria Saumell, and
Rodrigo I. Silveira:
In: Proceedings of the 25th Canadian Conference on Computational Geometry,
(CCCG'2013), Waterloo, Ontario, August 2013, pp. 295–300.
Abstract
Given k finite point sets in the plane, we are interested in
finding one translation for each point set such that the union of the
translated point sets is in convex position. We show that if k is
part of the input, then it is NPhard to determine if such translations
exist, even when each point set consists of at most three points.
The original motivation of this problem comes from the question of whether
a given triangulation T of a point set is the empty shape
triangulation with respect to some (strictly convex) shape S. In
other words, we want to find a shape S such that the triangles of
T are precisely those triangles about which we can circumscribe a
homothetic copy of S that does not contain any other vertices of
T. This is the Delaunay criterion with respect to S; for
the usual Delaunay triangulation, S is the circle.
Previous ← → Next
Dániel Gerbner, Viola Mészáros, Dömötör
Pálvölgyi, Alexey Pokrovskiy, and Günter Rote:
Journal of Graph Algorithms and
Applications 18, no. 3 (2014),
439–455. doi:10.7155/jgaa.00331. arXiv:1303.0523 [math.CO].
Abstract
We study the discrete Voronoi game, where two players alternately claim
vertices of a graph for t rounds. In the end, the remaining
vertices are divided such that each player receives the vertices that are
closer to his or her claimed vertices. We prove that there are graphs for
which the second player gets almost all vertices in this game, but this is
not possible for boundeddegree graphs. For trees, the first player can get
at least a quarter of the vertices, and we give examples where she
can get only little more than a third of them. We make some general
observations, relating the result with many rounds to the result for the
oneround game on the same graph.
Previous ← → Next
N. V. Abrosimov, E. Makai, jr., A. D. Mednykh, Yu. G. Nikonorov, and
Günter Rote:
Stud. Sci. Math. Hungarica
51 (2014), 466–519.
doi:10.1556/SScMath.51.2014.4.1292,
arXiv:1304.6579 [math.DG].
Abstract
We prove that, for any dimension n≥3, and any given sequence of
f numbers forming the facet areas of an npolytope with
f facets, there are polytopes with the same facet areas and arbitrarily
small volume. The case of the simplex was known previously. Also, the case
n=2 was settled, but there the infimum was some welldefined
function of the side lengths. For spherical and hyperbolic spaces, we give
some necessary conditions for the existence of a convex polytope with given
facet areas, and some partial results about sufficient conditions for the
existence of (convex) tetrahedra.
Previous ← → Next
Andrei Asinowski, Tillmann Miltzow, and Günter Rote:

Extended abstract. In: Abstracts of the 29th European Workshop on Computational Geometry
(EuroCG'13), Braunschweig, March 2013, Editor: Sándor Fekete,
pp. 225–228.

Journal of Computational Geometry 6 (2015),
185–219. arXiv:1302.4400 [cs.CG].
Abstract
Given n red and n blue points in general position in
the plane, it is wellknown that there is a perfect matching formed by
noncrossing line segments. We characterize the bichromatic point sets which
admit exactly one noncrossing matching. We give several geometric descriptions
of such sets, and find an O(n log n) algorithm that checks
whether a given bichromatic set has this property.
Previous ← → Next
Günter Rote:
In: Abstracts of the 29th European Workshop on Computational Geometry
(EuroCG'13), Braunschweig, March 2013, Editor: Sándor Fekete,
pp. 69–72.
Abstract
We measure the degree of convexity of a planar region by the probability
that two randomly chosen points see each other inside the polygon. We show
that, for a polygonal region with n edges, this measure can
be evaluated in polynomial time as a sum of O(n^{9}) closedform
expressions.
See Note after publication (2017)
Previous ← → Next
Sarit Buzaglo, Rom Pinchasi, and Günter Rote:
In: Thirty Essays on Geometric Graph Theory. Editor: János
Pach, SpringerVerlag, 2013, pp. 71–81. doi:10.1007/9781461401100_6
Abstract
Let P be a set of n points in the plane. A topological
hypergraph G on the set of points of P is a collection
of simple closed curves in the plane that avoid the points of P.
Each of these curves is called an edge of G, and the points of
P are called the vertices of G. We provide bounds on the
number of edges of topological hypergraphs in terms of the number of their
vertices under various restrictions assuming the set of edges is a family of
pseudocircles.
Previous ← → Next
Ivan Izmestiev, Robert B. Kusner, Günter Rote, Boris Springborn, and
John M. Sullivan:
Geometriae Dedicata 166 (2013), 15–29. doi:10.1007/s1071101297825,
arXiv:1207.3605 [math.CO].
Abstract
There is no 5,7triangulation of the torus, that is, no triangulation
with exactly two exceptional vertices, of degree 5 and 7.
Similarly, there is no 3,5quadrangulation. The vertices of a
2,4hexangulation of the torus cannot be bicolored. Similar statements
hold for 4,8triangulations and 2,6quadrangulations. We prove
these results, of which the first two are known and the others seem to be
new, as corollaries of a theorem on the holonomy group of a euclidean cone
metric on the torus with just two cone points. We provide two proofs
of this theorem: One argument is metric in nature, the other relies
on the induced conformal structure and proceeds by invoking the residue
theorem. Similar methods can be used to prove a theorem of Dress on
infinite triangulations of the plane with exactly two irregular vertices. The
nonexistence results for torus decompositions provide infinite families of
graphs which cannot be embedded in the torus.
Previous ← → Next
Darius Geiß, Rolf Klein, Rainer Penninger, and Günter Rote:
Computational Geometry, Theory and Applications 46 (2013),
1009–1016, special issue for the 28th European
Workshop on Computational Geometry (EuroCG'12).
doi:10.1016/j.comgeo.2013.05.005,
arXiv:1206.3057 [math.MG].
Abstract
We consider the following variant of the MongeKantorovich transportation
problem. Let S be a finite set of point sites in d
dimensions. A bounded set C in ddimensional space is to
be distributed among the sites p in S such that (i) each
p receives a subset C_{p}
of prescribed volume, and
(ii) the average distance of all points of C from their
respective sites p is minimized. In our model, volume is quantified
by some measure, and the distance between a site p and
a point z is given by a function d_{p}(z). Under
quite liberal technical assumptions on C and on the
functions
d_{p} we show that a solution of minimum total cost can be obtained
by intersecting with C the Voronoi diagram of the sites in
S, based on the functions d_{p}
with suitable additive
weights. Moreover, this optimum partition is unique up to sets of measure
zero. Unlike the deep analytic methods of classical transportation theory, our
proof is based directly on geometric arguments.
Previous ← → Next
Dror Atariah and Günter Rote:
In: Proceedings of the 28th Annual Symposium on Computational Geometry,
Chapel Hill, USA, June 17–20, 2012. Association for Computing
Machinery, 2012, pp. 415–416.
doi:10.1145/2261250.2261313
Published as part of the 21st Video Review of Computational Geometry.
Abstract
Based on a simple parameterization of contact surfaces, we visualize both the
workspace and the corresponding configuration space of a planar polygonal robot
that moves amid planar polygonal obstacles.
Previous ← → Next
Herbert Edelsbrunner, Brittany Terese Fasy, and Günter Rote:

In: Proceedings of the 28th Annual Symposium on Computational Geometry,
Chapel Hill, USA, June 17–20, 2012. Association for Computing
Machinery, 2012, pp. 91–100.
doi:10.1145/2261250.2261265, free PDF @ACM

Revised version,
Discrete and Computational
Geometry 49 (2013), 797–822.
doi:10.1007/s004540139517x
Abstract
The fact that the sum of isotropic Gaussian kernels (Gaussian distributions)
can have more modes (local maxima) than kernels is surprising. In 2003,
CarreiraPerpiñán and Williams exhibited n+1
isotropic Gaussian distributions in n dimensions
with n+2
modes. Such extra (ghost) modes do
not exist in one dimension and have not been well studied in higher
dimensions.
We study a symmetric configuration of n+1 Gaussian kernels for
which there are exactly n+2 modes. We show that all modes lie on
a finite set of lines, which we call axes, and study the restriction of the
Gaussian mixture to these axes in order to discover that there are an
exponential number of critical points in this configuration. Although the
existence of ghost modes remained unknown due to the difficulty of finding
examples in the plane, we show that the resilience of ghost modes grows
like the square root of the dimension. In addition, we exhibit finite
configurations of isotropic Gaussian kernels with superlinearly many modes.
Previous ← → Next
1. Jean Cardinal, Nathann Cohen, Sébastien Collette, Michael Hoffmann,
Stefan Langerman, and Günter Rote:
In: Abstracts of the 28th European Workshop on Computational Geometry
(EuroCG'12), Assisi, Italy, March 2012, pp. 209–212, Editors: Walter
Didimo and Giuseppe Liotta.
2. Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette,
Thomas Hackl, Michael Hoffmann, Kolja Knauer, Stefan Langerman, Michal
Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt:
to appear in: Algorithms and Data Structures SymposiumWADS 2013, August
2013, Editors: Frank Dehne, JörgRüdiger Sack, and Roberto
SolisOba, Lecture Notes in Computer Science, SpringerVerlag, 2013. arXiv:1302.2426 [cs.CG].
Abstract
We consider a coloring problem on dynamic, onedimensional point sets: points
appearing and disappearing on a line at given times. We wish to color them
with k colors so that at any time, any sequence of p(k)
consecutive points, for some function p, contains at least one point
of each color.
No such function p(k) exists in general. However, in the restricted
case in which points only appear but never disappear, we give a coloring
algorithm guaranteeing the property at any time with p(k)=3k2.
This can be interpreted as coloring point sets in the plane with k
colors such that any bottomless rectangle containing at least 3k2
points contains at least one point of each color. We also prove a lower
bound p(k)>1.67k. Chen, Pach, Szegedy, and Tardos (2009) proved that
such colorings do not always exist in the case of general axisaligned
rectangles. Our result also complements recent contributions of Keszegh and
Pálvölgyi on coverdecomposability of octants (2011,2012).
subject
Last update: July 19, 2013.
Previous ← → Next
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer,
Günter Rote, and André Schulz:

Abstracts of the 28th European Workshop on Computational Geometry
(EuroCG'12), Assisi, Italy, March 2012, pp. 49–52, Editors: Walter
Didimo and Giuseppe Liotta.

Computational Geometry, Theory and Applications 46
(2013), 959–969. Special issue for the 28th European
Workshop on Computational Geometry (EuroCG'12). doi:10.1016/j.comgeo.2013.04.005.
arXiv:1112.5904 [cs.CG].
Abstract
A constantworkspace algorithm has readonly access to an input array and may
use only constantly many additional words of O(log n) bits,
where n is the size of the input. We show that we can find a
triangulation of a plane straightline graph with n vertices in
O(n^{2})
time. We also consider preprocessing a simple ngon,
which is given by the ordered sequence of its vertices, for shortest path
queries when the space constraint is relaxed to allow s words of
working space. After a preprocessing of
O(n^{2})
time, we are able to
solve shortest path queries between any two points inside the polygon in
O(n^{2}/s) time.
Previous ← → Next
Günter Rote:
In: "Graph Drawing". GD 2011, Proceedings of the 19th International
Symposium on Graph Drawing, Eindhoven, September 2011, Revised Selected Papers.
Editors: Marc van Kreveld and Bettina Speckmann, Lecture Notes in Computer
Science, 7034, SpringerVerlag, 2011, pp. 238–241.doi:10.1007/9783642258787_23
Abstract
This invited talk is a survey on methods to construct a threedimensional convex polytope
with a given combinatorial structure, that is, with the edges forming a given
3connected planar graph, focusing on efforts to achieve small integer
coordinates.
Previous ← → Next
Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Katerina Čech
Dobiášová, Bert Jüttler, and Günter Rote:

In "Graph Drawing". GD 2011, Proceedings of the 19th International
Symposium on Graph Drawing, Eindhoven, September 2011, Revised Selected Papers.
Editors: Marc van Kreveld and Bettina Speckmann, Lecture Notes in Computer
Science, 7034, SpringerVerlag, 2012, pp. 296–307. doi:10.1007/9783642258787_29

Journal of Graph Algorithms and
Applications 19, no. 1 (2015), 43–65.
doi:10.7155/jgaa.00346
An important objective in the choice of a triangulation of a point set is
that the smallest angle becomes as large as possible. In the straightline
case, it is known that the Delaunay triangulation is optimal in this respect.
We propose and study the concept of a circular arc triangulation, which
offers additional flexibility for enlarging small angles. We show that angle
optimization and related questions lead to a linear programming problem that
can be solved by simple graphtheoretic methods.
Previous ← → Next
Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida
Dujmovic, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz,
Diane L. Souvaine, and Andrew Winslow:
In: Proceedings of the 23rd Annual Canadian Conference on Computational
Geometry, Vancouver, August 10–12, 2011, pp. 229–234.
Abstract
We show that any simple nvertex polygon can be made convex,
without losing internal visibilities between vertices, using n moves.
Each move translates a vertex of the current polygon along an edge to a
neighbouring vertex. In general, a vertex of the current polygon represents a
set of vertices of the original polygon that have become coincident.
We also show how to modify the method so that vertices become very close
but not coincident.
The proof involves a new visibility property of polygons, namely that every
simple polygon has a visibilityincreasing edge where, as a point travels from
one endpoint of the edge to the other, the visibility region of the point
increases.
Previous ← → Next
Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Günter
Rote, and Ryuhei Uehara:
In: Proceedings of the 23rd Annual Canadian Conference on Computational
Geometry, Vancouver, August 10–12, 2011, pp. 77–82.
Abstract
We investigate the problem of finding common developments that fold to several
different orthogonal boxes. It was shown that there are infinitely many
orthogonal polygons that fold to two incongruent orthogonal boxes in 2008.
In this paper, we first show that there is an orthogonal polygon that
fold to three boxes of size 1×1×5,
1×2×3, and
0×1×11. Although we have to admit a box
to have volume 0, this solves the open problem mentioned in literature.
Moreover, once we admit that a box can be of volume 0, a long rectangular
strip can be folded to an arbitrary number of boxes of volume 0. We next
consider for finding common nonorthogonal developments that fold to plural
incongruent orthogonal boxes. In literature, only orthogonal folding lines or
with 45 degree lines were considered. In this paper, we show some polygons
that can fold to two incongruent orthogonal boxes in more general directions.
Previous ← → Next
1. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:
In: Discrete Geometry and Optimization, Editors: Károly
Bezdek, Antoine Deza, and Yinyu Ye, Fields Institute Communications,
Vol. 69, SpringerVerlag, 2013,
pp. 79–104. doi:10.1007/9783319002002_6
2. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:
In: Computing and Combinatorics. Proceedings of the 18th
Annual International Computing and Combinatorics Conference (COCOON
2012), Sidney, August 2012. Editors: Joachim Gudmundsson, Julian
Mestre, and Taso Viglas. Lecture Notes in Computer Science,
Vol. 7434, SpringerVerlag, 2012, pp. 240–251. doi:10.1007/9783642322419_21
3. Günter Rote:
In: Abstracts of the 27th European Workshop on Computational Geometry
(EuroCG'11), Morschach, Switzerland, March 2011, pp. 183–184, Editor:
Michael Hoffmann.
This is a preliminary version with partial results.
Abstract
Consider a connected subdivision of the plane into n convex
faces where every vertex is incident to at most d edges.
Then, starting from every vertex there is a path with at least
Ω(log_{d}n) edges that is monotone in
some direction. This bound is best possible. Consider now a connected
subdivision of the plane into n convex faces where exactly
k faces are unbounded. Then, there is a path with at least
Ω(log(n/k)/log log(n/k))
edges that is monotone in some direction. This bound is also best possible.
Our methods are constructive and lead to efficient algorithms for computing
monotone paths of lengths specified above. In 3space, we show
that for every n>3, there exists a polytope
with
n vertices, bounded vertex degrees, and triangular faces such
that every monotone path on its 1skeleton has at most
O(log^{2}n) edges. We also construct a polytope
with n vertices, and triangular faces, (with unbounded degree
however), such that every monotone path on its 1skeleton has
at most O(log n) edges.
Previous ← → Next
Andrei Asinowski, Ronnie Barequet, Gill Barequet, and Günter Rote:

In: "Computing and Combinatorics". Proceedings of the 17th
Annual International Computing and Combinatorics Conference
(COCOON 2011), Dallas, Texas, August 2011. Editors: Bin Fu
and DingZhu Du. Lecture Notes in Computer Science 6842,
SpringerVerlag, 2011, pp. 181–191. doi:10.1007/9783642226854_16

Journal of Integer Sequences
15 (2012),
Article 12.8.4, 16 pages.
Abstract
A ddimensional polycube of size n is a connected set of
n cubes in d dimensions, where connectivity is through
(d−1)dimensional faces. Enumeration of polycubes, and, in particular,
specific types of polycubes, as well as computing the asymptotic growth rate
of polycubes, is a popular problem in discrete geometry. This is also an
important tool in statistical physics for computations related to percolation
processes and branched polymers. In this paper we consider proper
polycubes: A polycube is said to be proper in d dimensions
if the convex hull of the centers of its cubes is ddimensional. We
prove a formula for the number of polycubes of size n that are
proper in n−3 dimensions.
Previous ← → Next
Günter Rote:
Internat. Math. Nachrichten 213 (2010), 1–5.
Abstract
This is a critical discussion of a certain methodologicalmathematical aspect
regarding the comparison of journals in the study of the use of citation
counts and impact factors by Robert Adler, John Ewing, and Peter Taylor from
2008, that was commissioned by the International Mathematical Union, see
http://www.mathunion.org/fileadmin/IMU/Report/CitationStatistics.pdf.
Previous ← → Next
Günter Rote and Uri Zwick:
In: Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), San Francisco, January 2011, pp. 606–613.
Abstract
The problem of checking whether a given tower of bricks is stable can be
easily answered by checking whether a system of linear equations has a
feasible solution. A more challenging problem is to determine how an
unstable tower of bricks collapses. We use Gauß' principle of
least restraint to show that this, and more general rigidbody simulation
problems in which many parts touch each other, can be reduced to solving a
sequence of convex quadratic programs, with linear constraints, corresponding to
a discretization of time. The first of these quadratic programs gives an
exact description of initial infinitesimal collapse. The results of the
subsequent programs need to be integrated over time to yield an approximation
of the global motion of the system.
Previous ← → Next
Günter Rote:
In: 26th European Workshop on Computational Geometry (EuroCG'10), Dortmund,
March 2010, pp. 249–251, Editor: Jan Vahrenhold.
Abstract
We consider the problem of translating a given pattern set
B of size m, and matching every point of B to
some point of a larger ground set A of size n
in an injective way, minimizing the sum of the squared distances between
matched points. We show that when B
can only be translated along a
line, there can be at most m(n  m) + 1 different matchings as
B moves along the line, and hence the optimal translation can be
found in polynomial time.
Previous ← → Next
Boris Aronov, Otfried Cheong, Xavier Goaoc, and Günter Rote:
Discrete and Computational Geometry
45 (2011), 230–260. doi:10.1007/s0045401092886,
arXiv:1002.3294 [math.MG].
Abstract
A line g is a transversal to a family F of convex
polytopes in 3dimensional space if it intersects every member of F.
If, in addition, g is an isolated point of the space of line
transversals to F, we say that F is a pinning of
g. We show that any minimal pinning of a line by convex polytopes
such that no face of a polytope is coplanar with the line has size at most
eight. If, in addition, the polytopes are disjoint, then it has size at most
six. We completely characterize configurations of disjoint polytopes that form
minimal pinnings of a line.
Previous ← → Next
Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer,
Daria Schymura, and Mariano Zelke:
In: Proceedings of the 21st Annual Canadian Conference on Computational
Geometry, Vancouver, August 17–19, 2009, pp. 145–148.
Computational Geometry, Theory and Applications 44 (2011),
82–94. (Special issue for the 21st Canadian Conference
on Computational Geometry, Vancouver, 2009) doi:10.1016/j.comgeo.2010.09.004
Abstract
An ntown, for a natural number n, is a group of
n buildings, each occupying a distinct position on a 2dimensional
integer grid. If we measure the distance between two buildings along the
axisparallel street grid, then an ntown has optimal shape if the
sum of all pairwise Manhattan distances is minimized. This problem has been
studied for cities, i.e., the limiting case of very large n. For cities, it is known that the
optimal shape can be described by a differential equation, for which no closedform
solution is known. We show that optimal ntowns can be computed in
O(n^{7.5})
time. This is also practically useful, as it allows us to
compute optimal solutions up to n=80.
See Python programs and numerical results
Previous ← → Next
1. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang:
Journal of Computational Geometry 2 (2011),
46–68.
2. Tetsuo Asano and Günter Rote:
In: Proceedings of the 21st Annual Canadian Conference on Computational
Geometry, Vancouver, August 17–19, 2009, pp. 87–90.
(This is a preliminary short version with parts of the results.)
Abstract
Constantworkspace algorithms may use only constantly many cells of storage in
addition to their input, which is provided as a readonly array. We show how
to construct several geometric structures efficiently in the constantworkspace
model. Traditional algorithms process the input into a suitable data structure
(like a doublyconnected edge list) that allows efficient traversal of the
structure at hand. In the constantworkspace setting, however, we cannot
afford to do this. Instead, we provide a zerospace data structure that
constructs the desired features on the fly by accessing the input. The whole
geometric structure can be obtained by using this data structure to enumerate
all the features. Of course, we must pay for the space savings by slower
running times. While the standard data structure allows us to implement
traversal operations in constant time, our schemes typically take linear time
to read the input data in each step.
We begin with two simple problems: triangulating a planar point set and
finding the trapezoidal decomposition of a simple polygon. In both cases
adjacent features can be enumerated in linear time per step, resulting in
total quadratic running time to output the whole structure. Actually, we show
that the former result carries over to the Delaunay triangulation, and hence
the Voronoi diagram. This also means that we can compute the largest empty
circle of a planar point set in quadratic time and constant workspace. As
another application, we demonstrate how to enumerate the features of an
Euclidean minimum spanning tree in quadratic time per step, so that the whole tree can be
found in cubic time using constant workspace.
Finally, we describe how to compute a shortest geodesic path between two
points in a simple polygon. Although the shortest path problem in general
graphs is NLcomplete, this constrained problem can be solved in quadratic
time using only constant workspace.
Previous ← → Next
Oswin Aichholzer, Thomas Hackl, Davíd Orden, Pedro Ramos, Günter
Rote, André Schulz, and Bettina Speckmann:

In: European Conference on Combinatorics, Graph Theory and Applications
(EuroComb 2009), Bordeaux, September 2009, Editors: Jaroslav Nešetřil and
André Raspaud, Electronic
Notes in Discrete Mathematics
34 (2009), 509–513.
doi:10.1016/j.endm.2009.07.084

Graphs and Combinatorics 29 (2013), 1577–1593.
doi:10.1007/s0037301212290
arXiv:0903.2184
[math.CO].
Abstract
We study flip graphs of (pseudo)triangulations whose maximum vertex degree is
bounded by a constant k. In particular, we consider triangulations
of sets of n points in convex position in the plane and prove
that their flip graph is connected if and only if k>6; the
diameter of the flip graph is O(n^{2}). We also show that for general
point sets, flip graphs of pointed pseudotriangulations can be disconnected
for k<10, and flip graphs of triangulations can be disconnected for
any k.
Previous ← → Next
Günter Rote and André Schulz:
In: Algorithms and Data Structures SymposiumWADS 2009, Banff,
August 2009, Editors: Frank Dehne, Ian Munro, JörgRüdiger
Sack, and Roberto Tamassia, Lecture Notes in Computer Science,
5664, SpringerVerlag, 2009, pp. 530–541. doi:10.1007/9783642033674_46
Abstract
We consider the pair (p_{i},
f_{i}) as a force with
twodimensional direction vector
f_{i} applied at the point
p_{i} in the plane. For a given
set of forces we ask for a noncrossing geometric graph on the points
p_{i} that has the following
property: there exists a weight assignment to the edges of the graph,
such that for every p_{i} the sum
of the weighted edges (seen as vectors) around
p_{i} yields
−f_{i}. As additional
constraint we restrict ourselves to weights that are nonnegative on
every edge that is not on the convex hull of the point set. We show
that (under a generic assumption) for any reasonable set of forces
there is exactly one pointed pseudotriangulation that fulfils the
desired properties. Our results will be obtained by linear programming
duality over the PPTpolytope. For the case where the forces appear
only at convex hull vertices we show that the pseudotriangulation
that resolves the load can be computed as weighted Delaunay
triangulation. Our observations lead to a new characterization of
pointed pseudotriangulations, structures that have been proven to be
extremely useful in the design and analysis of efficient geometric
algorithms.
As an application, we discuss how to compute the maximal locally convex
function for a polygon whose corners lie on its convex hull.
This extends results that were presented in the earlier paper
A pointed Delaunay pseudotriangulation of a simple polygon
mentioned below.
Our studies are
motivated by the construction of discrete LaplaceBeltrami operators.
Günter Rote and André Schulz:
In: Abstracts of the 21st European Workshop on Computational Geometry,
Eindhoven, March 2005, pp. 7780.
Previous ← → Next
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter
Rote, Bettina Speckmann, and Birgit Vogtenhuber:

In: Algorithms and Data Structures Symposium—WADS 2009, Banff,
August 2009, Editors: Frank Dehne, Ian Munro, JörgRüdiger
Sack, and Roberto Tamassia, Lecture Notes in Computer Science,
5664, SpringerVerlag, 2009, pp. 13–24.
doi:10.1007/9783642033674_2

Graphs and Combinatorics 30 (2014), 47–69. doi:10.1007/s003730121247y
Abstract
Let S be a set of n points in general position in the
plane. For each point of S we are given a parity constraint,
telling whether it should be even or odd. We study how well such constraints
can be satisfied by various classes of planar graphs on S.
Specifically, we show that we can always find a plane tree, a twoconnected
outerplanar graph, or a pointed pseudotriangulation that satisfies all but at
most three parity constraints. With triangulations, we can satisfy about 2/3
of all parity constraints.
For a polygon with holes, it is NPcomplete to decide whether it has a
triangulation that satisfies all parity constraints on the vertices.
Previous ← → Next
Panos Giannopoulos, Christian Knauer, and Günter Rote:
In: Proc. 4th Int. Workshop on Parameterized and Exact
ComputationIWPEC 2009, Copenhagen, September 2009, Editors: Jianer
Chen and Fedor V. Fomin, Lecture Notes in Computer Science,
Vol. 5917, SpringerVerlag, 2009, pp. 198–209. doi:10.1007/9783642112690_16,
arXiv:0906.3469 [cs.CG].
Abstract
We study the parameterized complexity of the following fundamental geometric
problems with respect to the dimension d:
 Given n points in d, compute their minimum enclosing
cylinder.
 Given two npoint sets in d dimensions,
decide whether they can be separated by two hyperplanes.
 Given a system
of n linear inequalities with d variables, find a
maximumsize feasible subsystem.
We show that the decision versions of all these problems are W[1]hard
when parameterized by the dimension d, and hence not solvable
in O(f(d)n^{c}) time, for any computable function f and
constant c (unless FPT=W[1]). Our reductions also give an
n^{Ω(d)}time lower bound (under the Exponential Time
Hypothesis).
Previous ← → Next
Ronnie Barequet, Gill Barequet, and Günter Rote:
 In: European Conference on Combinatorics, Graph Theory and Applications
(EuroComb 2009), Bordeaux, September 2009. Editors: Jaroslav Nešetřil
and André Raspaud. Electronic
Notes in Discrete Mathematics 34 (2009), 459–463.
doi:10.1016/j.endm.2009.07.076

Combinatorica 30 (2010), 257–275. doi:10.1007/s0049301024488
Abstract
A ddimensional polycube is a facetconnected set of cubes in
d dimensions. Fixed polycubes are considered distinct if they differ
in their shape or orientation. A proper ddimensional
polycube spans all the d dimensions, that is, the convex hull of
the centers of its cubes is ddimensional. In this paper we prove
rigorously some (previously conjectured) closed formulae for fixed (proper and
improper) polycubes, and show that the growthrate limit of the number of
polycubes in d dimensions is 2ed−o(d). We conjecture that
it is asymptotically equal to (2d−3)e + O(1/d).
Previous ← → Next
Günter Rote:
In: Abstracts of the 25th European Workshop on Computational Geometry
(EuroCG'09), Brussels, March 2009, pp. 187–189.
Abstract
The two following problems can be solved by a reduction to a minimumweight
bipartite matching problem: (a) Floodlight illumination: We are given
n infinite wedges (sectors, spotlights) that can cover the whole
plane when placed at the origin. They are to be assigned to n
given locations (in arbitrary order, but without rotation) such that they
still cover the whole plane. (b) Convex partition: Partition a convex
mgon into m convex parts, each part containing one of
the edges and a given number of points from a given point set inside the
polygon.
See Note on priority
Previous ← → Next
Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel
Werner:

In: Abstracts of the 25th European Workshop on Computational Geometry
(EuroCG'09), Brussels, March 2009, pp. 281–284.
 Computational Geometry, Theory and Applications 46 (2013),
839–860. Special issue for the 25th European
Workshop on Computational Geometry (EuroCG'09). doi:10.1016/j.comgeo.2011.06.005,
arXiv:0906.3896 [cs.CG].
Abstract
We study the parameterized complexity of several stabbing problems. We show
that the (decision) problem of stabbing a set of axisparallel unit squares
with k axisparallel lines is W[1]hard with respect to k,
and thus, not fixedparameter tractable unless W[1]=FPT. When the lines can
have arbitrary directions, it is even W[1]hard for disjoint squares. For
stabbing disjoint unit squares with axisparallel lines, we show that the
problem is fixedparameter tractable by giving an algorithm that runs in
O(n log n) time for every fixed k. Deciding
whether a set of unit balls in d dimensions can be stabbed by one
line is W[1]hard with respect to the dimension d.
Previous ← → Next
Dania ElKhechen, Thomas Fevens, John Iacono, and Günter Rote:
Partitioning a polygon into two mirror congruent pieces.
In: Proceedings of the 20th Canadian
Conference on Computational Geometry, Montréal, August 13–15,
2008, pp. 131–134.
Previous ← → Next
Günter Rote:
Technical report ACSTR36150301,
May 2008, 12 pages.
Abstract
We present a subdivision algorithm for computing the intersection of
spline
curves. The complexity depends on geometric quantities that represent
the
hardness of the computation in a natural way, like the angle of the
intersection. The main idea is the application of the supercomposition
technique, which considers unions of adjacent parameter intervals that
are not
siblings in the subdivision tree. This approach addresses the common
difficulty
of nontermination of the classical subdivision approach when the
intersection
coincides with a subdivision point, but it avoids the numerical
overhead
associated to alternative methods like a random shift of the parameter.
Previous ← → Next
Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun
Luo, Günter Rote, Rodrigo I. Silveira, Bettina Speckmann, and Thomas
Wolle:
In: Advances in GIScience.
Proceedings of the 12th AGILE International Conference on Geographic
Information Science, Hannover, Germany, June 2009, Editors: Monika Sester, Lars
Bernard, Volker Paelke. Lecture Notes in Geoinformation and Cartography,
SpringerVerlag, 2009, pp. 217–231.
(Best paper award).
doi:10.1007/9783642003189_11
Journal of Graph Algorithms and
Applications 14 (2010), 307–336.
doi:10.7155/jgaa.00209
Abstract
We study a point pattern detection problem on networks, motivated by
applications in geographical analysis, such as crime hotspot detection. Given a
network N (a connected graph with positive edge lengths) together
with a set of sites, which lie on the edges or vertices of N, we
look for a connected subnetwork F of N of small total
length that contains many sites. The edges of F can form parts of
the edges of N.
We consider different variants of this problem where N is either a
general graph or restricted to a tree, and the subnetwork F that
we are looking for is either a simple path, a path with selfintersections
at vertices, or a tree. We give polynomialtime algorithms, NPhardness and
NPcompleteness proofs, approximation algorithms, and also fixedparameter
tractable algorithms.
Previous ← → Next
1. Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Bernhard Kornberger, Simon
Plantinga, Günter Rote, Astrid Sturm, and Gert Vegter:
In: Abstracts of the 24th European Workshop on Computational Geometry,
Nancy, March 2008, pp. 13–16.
(preliminary version)
2. Oswin Aichholzer, Franz Aurenhammer, Bernhard Kornberger, Simon Plantinga,
Günter Rote, Astrid Sturm, and Gert Vegter:
In: Eurographics Symposium on Geometry Processing, Berlin, July 2009,
Editors: Marc Alexa, Michael Kazhdan, Computer Graphics Forum 28 (2009),
1349–1360.
Abstract
For a surface F in 3space that is represented by a
set S of sample points, we construct a coarse approximating
polytope P that uses a subset of S as its vertices
and preserves the topology of F. In contrast to surface
reconstruction we do not use all the sample points, but we try to use as
few points as possible. Such a polytope P is useful as a
seed polytope for starting an incremental refinement procedure to
generate better and better approximations of F based on interpolating
subdivision surfaces or e.g. Bézier patches.
Our algorithm starts from an rsample S of
F. Based on S, a set of surface covering balls with
maximal radii is calculated such that the topology is retained. From the
weighted αshape of a proper subset of these highly
overlapping surface balls we get the desired polytope. As there is a
range for the possible radii for the surface balls, the method can be
used to construct triangular surfaces from point clouds in a scalable manner.
We also briefly sketch how to combine parts of our algorithm with existing
medial axis algorithms for balls, in order to compute stable medial axis
approximations with scalable level of detail.
Previous ← → Next
1. Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter
Rote:
In: Proceedings of the 19th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), San Francisco, January 2008, pp. 836–843. doi:10.1145/1347082.1347174
preliminary version without the hardness result for covering by 4
unit cubes
2. Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, and
Günter Rote:
ACM Transactions on Algorithms 7 (2011),
Article 43, 27 pages. doi:10.1145/2000807.2000811
Abstract
We present an algorithm for finding the smallest side length for 3
axisaligned cubes that cover a given npoint set in d
dimensions in
O(6^{d}dn
log (dn)) time. This shows that the
problem is fixedparameter tractable when parameterized with d.
On the other hand, using tools from parameterized complexity theory, we
show that this is unlikely to be the case for 4 cubes, and with the
kcenter problem in the Euclidean metric, for any k>1.
In particular, we prove that deciding whether a given ddimensional
set of n points can be covered by the union of 2 balls of given
radius, or by 4 axisaligned cubes of given side length, is W[1]hard with
respect to d, and thus not fixedparameter tractable unless FPT=W[1].
Previous ← → Next
Rom Pinchasi and Günter Rote:
Israel Journal of
Mathematics 172 (2009), 337–348.
doi:10.1007/s118560090076z,
arXiv:0707.0311 [math.MG].
Abstract
We show that the maximum cardinality of an antichain composed of
intersections of a given set of n points in the plane with
halfplanes
is close to n^{2}. We approach this problem by
establishing the
equivalence with the problem of the maximum monotone path in an
arrangement
of n lines. For a related problem on antichains in families of
convex
pseudodiscs we can establish the precise asymptotic bound: it is
quadratic in
n. The sets in such a family are characterized as intersections
of a
given set of n points with convex sets, such that the
difference
between the convex hulls of any two sets is nonempty and connected.
Previous ← → Next
Oswin Aichholzer, Günter Rote, André Schulz, and Birgit
Vogtenhuber:
 In: Proceedings of the 19th Canadian Conference on Computational Geometry,
Ottawa, August 20–22, 2007,
Editor: Prosenjit Bose,
pp. 237–240.

Computational Geometry, Theory and
Applications 45 (2012), 482–494
(special issue for
the 19th Canadian Conference on Computational Geometry).
doi:10.1016/j.comgeo.2010.08.001 (open access)
Abstract
We study the problem how to draw a planar graph such that every vertex
is
incident to an angle greater than 180 degrees. In general a
straightline
embedding can not guarantee this property. We present algorithms which
construct such drawings with either tangentcontinuous biarcs or
quadratic
Bézier curves (parabolic arcs), even if the positions of the
vertices
are predefined by a given plane straightline embedding of the graph.
Moreover, the graph can be embedded with circular arcs if the vertices
can
be placed arbitrarily.
Previous ← → Next
Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter
Rote:
In: Proceedings of the 23rd Annual Symposium on Computational
Geometry, Gyeongju, South Korea, June 6–8, 2007. Association
for Computing Machinery, 2007, pp. 275–283. doi:10.1145/1247069.1247119
In: Abstracts of the 23rd European Workshop on Computational
Geometry,
Graz, March 2007, pp. 122–125.
Computational Geometry, Theory and
Applications 42 (2009), pp. 772–789.
doi:10.1016/j.comgeo.2008.02.007
Abstract
Principal component analysis (PCA) is commonly used to compute a
bounding box
of a point set in R^{d}. The popularity of this
heuristic lies in its
speed, easy implementation and in the fact that usually, PCA bounding
boxes
approximate the minimumvolume bounding boxes quite well.
There are examples of discrete points sets in the plane showing that
the
worst case ratio tends to infinity. Thus, we consider PCA bounding
boxes for
continuous sets, especially for the convex hull of a point set. We
contribute
new upper bounds on the approximation factor of PCA bounding boxes of
convex
sets in R^{2} and R^{3}.
Previous ← → Next
Ares Ribó Mor, Günter Rote, and André Schulz:
In: Proceedings of the 23rd Annual Symposium on Computational
Geometry, Gyeongju, South Korea, June 6–8, 2007. Association for
Computing Machinery, 2007, pp. 112–118. doi:10.1145/1247069.1247086
Discrete and Computational
Geometry 45 (2011), 65–87. doi:10.1007/s0045401093010,
arXiv:0908.0488 [cs.CG].
Abstract
We present a constructive method for embedding a 3connected planar graph with
n vertices as a 3polytope with small integer coordinates. The
embedding will need no coordinate greater than
O(2^{7.55n})=O(188^{n}).
Finding a plane embedding which supports an equilibrium stress is the crucial
part in the construction. In order to guarantee that the size of the
coordinates and the stresses are small, we extend Tutte's spring embedding
method.
Previous ← → Next
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and
Günter
Rote:
 In: Proceedings of the 23rd Annual Symposium on Computational
Geometry, Gyeongju, South Korea, June 68, 2007. Association
for Computing Machinery, 2007, pp. 142149. doi:10.1145/1247069.1247098
 Discrete and Computational Geometry 39 (2008), pp. 316.
doi:10.1007/s0045400790230
Abstract
A finite planar point set P is called a magic configuration
if
there is an assignment of positive weights to the points of P
such that, for every line l determined by P,
the sum of
the weights of all points of P on l equals 1.
We prove
a conjecture of Murty from 1971 and show that a magic configuration
consists
either of points in general position, or all points are collinear, with
the
possible exception of one point, or they form a special configuration
of 7
points.
free PDF view@Springer
Previous ← → Next
Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and
Carola
Wenk:
In: Abstracts of the 23rd European Workshop on Computational
Geometry,
Graz, March 2007, pp. 170173.
Abstract
We study the complexity of computing the Fréchet distance (also
called
dogleash distance) between two polygonal curves with a total number of
n vertices. For two polygonal curves in the plane we prove an
Ω(n log n) lower bound for the decision problem in the
algebraic
computation tree model allowing arithmetic operations and tests. Up to
now
only a O(n^{2}) upper bound for the decision
problem
was known.
The lower bound extends to variants of the Fréchet distance
such as
the weak as well as the discrete Fréchet distance. For two
polygonal
curves in one dimension, we give a lineartime algorithm to compute
their
weak Fréchet distance.
Previous ← → Next
Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, and Gert
Vegter:
In: Abstracts of the 23rd European Workshop on Computational Geometry,
Graz, March 2007, pp. 26–29.
Abstract
Given points in convex position in three dimensions, we want to find an
approximating convex surface consisting of spherical patches, such that all
points are within some specified tolerance bound of the approximating surface.
We describe a greedy algorithm which constructs an approximating surface whose
spherical patches are associated to the faces of an inscribed polytope. We
show that deciding whether an approximation with not more than a given number
of spherical patches exists is NPhard.
Previous ← → Next
Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote,
and Gerard
Tel:
 In: Proceedings of the fourth conference on Fun with
Algorithms
(FUN 2007). Castiglioncello, June 2007, Editors: Pilu Crescenzi,
Giuseppe Prencipe, and Geppino Pucci. Lecture Notes in Computer
Science, 4475, SpringerVerlag, 2007, pp. 16–29. doi:10.1007/9783540729143_4
 Theory of Computing Systems 44 (2009), 160–174. doi:10.1007/s0022400891043
Abstract
We discuss some new geometric puzzles and the complexity of their
extension to arbitrary sizes. For gate puzzles and twolayer puzzles we
prove NPcompleteness of solving them. Not only the solution of puzzles
leads to interesting questions, but also puzzle design gives rise to
interesting theoretical questions. This leads to the search for
instances of
partition that use only integers and are uniquely solvable. We show
that
instances of polynomial size exist with this property. This result also
holds
for partition into k subsets with the same sum: We
construct
instances of n integers with subset sum O(n^{k+1}),
for
fixed k.
Previous ← → Next
Günter Rote, Francisco Santos, and Ileana Streinu:
In: Surveys on Discrete and Computational Geometry—Twenty Years Later.
Editors: Jacob E. Goodman, János Pach, and Richard Pollack. Contemporary
Mathematics, volume 453, American Mathematical Society, 2008, pp. 343–410.
arXiv:math/0612672 [math.CO].
Abstract
A pseudotriangle is a simple polygon with three convex vertices, and a
pseudotriangulation is a tiling of a planar region into pseudotriangles.
Pseudotriangulations appear as data structures in computational geometry,
as planar barandjoint frameworks in rigidity theory and as projections
of locally convex surfaces. This survey of current literature includes
combinatorial properties and counting of special classes, rigidity theoretical
results, representations as polytopes, straightline drawings from abstract
versions called combinatorial pseudotriangulations, algorithms and applications
of pseudotriangulations.
Previous ← → Next
Günter Rote and Gert Vegter:
In: Effective Computational Geometry for Curves and Surfaces. Editors:
JeanDaniel Boissonnat and Monique Teillaud, Chapter 5. Mathematics and
Visualization, SpringerVerlag, 2006, pp. 277–312. doi:10.1007/9783540332596_7
Abstract
This is an introduction to combinatorial topology, with an emphasis on
subjects that are of interest for computational geometry in two and three
dimensions. It covers the notions of homotopy and isotopy, simplicial homology,
Betti numbers, and basic results from Morse Theory.
Previous ← → Next
JeanDaniel Boissonnat, David CohenSteiner, Bernard Mourrain, Günter
Rote, and Gert Vegter:
In: Effective Computational Geometry for Curves and Surfaces. Editors:
JeanDaniel Boissonnat and Monique Teillaud, Chapter 5. Mathematics and
Visualization, SpringerVerlag, 2006, pp. 181–229. doi:10.1007/9783540332596_5
Abstract
Meshing is the process of computing, for a given surface, a representation
consisting of pieces of simple surface patches, like triangles. This survey
discusses all currently known surface (and curve) meshing algorithms that come
with correctness and quality guarantees.
Previous ← → Next
Günter Rote and Martin Zachariasen:
In: Proceedings of the 18th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), New Orleans, January 2007, pp. 848854.
Abstract
A given nonnegative n×n matrix A=(a_{ij})
is to be scaled, by
multiplying its rows and columns by unknown positive multipliers λ_{i}
and
μ_{j}, such that the resulting matrix (a_{ij}λ_{i}μ_{j})
has specified row and
column sums r_{i} and s_{j}. We give an
algorithm that achieves the
desired row and column sums with a maximum absolute error ε
in
O(n^{4}(logn+log(h/ε)))
steps,
where h is the overall total of the
result matrix. Our algorithm is a scaling algorithm. It solves a
sequence of
more and more refined discretizations. The discretizations are
minimumcost
network flow problems with convex piecewise linear costs. These
discretizations
are interesting in their own right because they arise in proportional
elections.
Previous ← → Next
R. L. Scot Drysdale, Günter Rote, and Astrid Sturm:
In: Abstracts of the 22nd European Workshop on Computational
Geometry,
Delphi, March 2006, pp. 25–28. (preliminary version with partial
results)
Computational Geometry,
Theory and Applications 41 (2008), 31–47. doi:10.1016/j.comgeo.2007.10.009
Abstract
We present an algorithm for approximating a given open polygonal curve
with a
minimum number of circular arcs. In computeraided manufacturing
environments,
the paths of cutting tools are usually described with circular arcs and
straight line segments. Greedy algorithms for approximating a polygonal
curve
with curves of higher order can be found in the literature. Without
theoretical bounds it is difficult to say anything about the quality of
these
algorithms. We present an algorithm which finds a series of circular
arcs
that approximate the polygonal curve while remaining within a given
tolerance
region. This series contains the minimum number of arcs of any such
series.
Our algorithm takes O(n^{2} log n) time
for
an original
polygonal chain
with n vertices.
Using a similar approach, we design an algorithm with a runtime of O(n^{2}
log n), for computing a tangentcontinuous
approximation with the
minimum number of biarcs, for a sequence of points with given tangent
directions.
Previous ← → Next
Sergio Cabello and Günter Rote:
 In: Proceedings of the 18th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), New
Orleans, January 2007, pp. 98–107. doi:10.1145/1283383.1283395
 SIAM Journal on Discrete Mathematics 24
(2010), 1713–1730. doi:10.1137/09077638X
Abstract
We consider the problem of finding obnoxious centers in graphs. For arbitrary
graphs with n vertices and m edges, we give a randomized
algorithm with
with O(n log^{2}n + m
log n)
expected time. For planar graphs, we
give algorithms with O(n log n) expected time and O(n
log^{3}n)
worstcase time. For graphs with bounded treewidth, we give an
algorithm
taking O(n log n) worstcase time. The algorithms
make use of parametric
search and several results for computing distances on graphs of bounded
treewidth and planar graphs.
Previous ← → Next
Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter
Rote:
In: Abstracts of the 22nd European Workshop on Computational
Geometry,
Delphi, March 2006, pp. 193196. (preliminary version with partial
results)
In: WSCG'2007, Prof. 15th Int. Conf. in Central Europe on Computer
Graphics, Visualization and Computer Vision, Plzen, Czech Republic,
January
29  February 1, 2007, Editors: Jarek Rossignac and Vaclav Skala,
pp. 185192.
Abstract
Principal component analysis (PCA) is commonly used to compute a
bounding box
of a point set in R^{d}. The popularity of this
heuristic lies in its
speed, easy implementation and in the fact that usually, PCA bounding
boxes
approximate the minimumvolume bounding boxes quite well. In this paper
we
give a lower bound on the approximation factor of PCA bounding boxes
of convex polytopes in arbitrary dimension, and an upper bound on the
approximation factor of PCA bounding boxes of convex polygons in R^{2}.
Previous ← → Next
Günter Rote:
In: Oberwolfach Reports, 3, European Mathematical Society 
Publishing House, 2006, pp. 696–698. doi:0.4171/OWR/2006/12
Abstract
Classical Morse Theory considers the topological changes of the level
sets
M_{h}={x in M  f(x)=h}
of a smooth function f defined on a
manifold M as the height h varies. At critical
points, where
the gradient of f vanishes, the topology changes. These changes
can be
classified locally, and they can be related to global topological
properties
of M. Between critical values, the level sets vary smoothly. We
prove
that the same statement is true for piecewise linear
functions in up
to three variables: between critical values, all level sets are
isotopic.
Previous ← → Next
Eyal Ackerman, Kevin Buchin, Christiane Knauer, and Günter Rote:
 In: Proceedings of the 10th Scandinavian Workshop on
Algorithm Theory (SWAT). Riga, July 2006, Editors: Lars Arge
and Rusins Freivalds. Lecture Notes in Computer Science, 4059,
SpringerVerlag, 2006, pp. 266–277. doi:10.1007/11785293_26

In: Abstracts of the 22nd European Workshop on Computational Geometry,
Delphi, March 2006, pp. 207–210.

Journal of Graph Algorithms and Applications
14, No. 2 (2010), 367–384.
doi:10.7155/jgaa.00211
Abstract
Given a set of curves in the plane or a topological graph, we ask for an
orientation of the curves or edges which induces an acyclic orientation on
the corresponding planar map. Depending on the maximum number of crossings on
a curve or an edge, we provide algorithms and hardness proofs for this
problem.
Previous ← → Next
Wolfgang Mulzer and Günter Rote:
 In: Proceedings of the 22nd Annual Symposium on
Computational Geometry, Sedona, June 5–7, 2006. Association
for Computing Machinery, 2006, pp. 1–10. doi:10.1145/1137856.1137859
 Technical report B0523revised, February 2008,
45 pages, arXiv:cs/0601002
[cs.CG], complete version with extra appendices.
 Journal of the ACM 55, no. 2 (May
2008), Article 11, 29 pp.
doi:10.1145/1346330.1346336
Abstract
A triangulation of a planar point set is a maximal plane straightline
graph whose vertex set is the given set. In the minimumweight
triangulation (MWT) problem, we are looking for a triangulation of
a
given point set that minimizes the sum of the edge lengths. We prove
that
the decision version of this problem is NPhard. We use a reduction
from
PLANAR 1IN3SAT. The correct working of the gadgets is established
with
computer assistance, using dynamic programming on polygonal faces, as
well as
the βskeleton heuristic to certify that certain
edges
belong to the minimumweight triangulation.
See Note on priority
Previous ← → Next
Ares Ribó Mor and Günter Rote:
Lower bounds for the maximum number of spanning trees of a planar graph.
manuscript, March 2009, (in preparation).
Previous ← → Next
Günter Rote:
In: Oberwolfach Reports, 2, European Mathematical Society 
Publishing House, 2005, pp. 969–973. doi:10.4171/OWR/2005/17
Abstract
A planar graph with n
vertices has at most 5.333...^{n}
spanning trees. If it
has no triangle, it has at most 3.53^{n} spanning trees.
If it is
3connected
planar and without a face cycle of length three or four it has at most
2.848^{n} spanning
trees. These bound are obtained with a probabilistic method.
They are applied to the construction of 3dimensional polytopes with a
given
combinatorial structure and with small integral vertex
coordinates.
Previous ← → Next
Sergio Cabello, Panos Giannopoulos, Christian Knauer, and
Günter
Rote:
 In: Abstracts of the 21st European Workshop on Computational
Geometry,
Eindhoven, March 2005, pp. 5760.
 In: "Algorithms  ESA 2005", Proc. Thirteenth Annual European
Symposium on
Algorithms, Palma de Mallorca, 2005. Editors: Gerth Stolting Brodal and
Stefano
Leonardi. Lecture Notes in Computer Science 3669, SpringerVerlag,
2005,
pp. 520531. doi:10.1007/11561071_47
 Computational Geometry,
Theory and Applications 39 (2008), pp. 118133. doi:10.1016/j.comgeo.2006.10.001
Abstract
The Earth Mover's Distance (EMD) between two weighted point sets (point
distributions) is a distance measure commonly used in computer vision
for
colorbased image retrieval and shape matching. It measures the minimum
amount of work needed to transform one set into the other one by weight
transportation. We study the following shape matching problem: Given
two
weighted point sets A and B in the plane, compute a
rigid
motion of A that minimizes its Earth Mover's Distance to B.
No
algorithm is known that computes an exact solution to this problem. We
present simple FPTASs and polynomialtime (2+ε)approximation
algorithms for the minimum Euclidean EMD between A and B
under
translations and rigid motions.
Previous ← → Next
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor
P.
Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, and
Günter Rote:
 In: Proceedings of the 22nd Annual Symposium on
Computational Geometry, Sedona, June 5–7, 2006. Association
for Computing Machinery, 2006, pp. 61–70.
doi:10.1145/1137856.1137868.

Discrete and Computational
Geometry 44 (2010), 439–462. doi:10.1007/s0045401092623,
arXiv:cs/0604022 [cs.CG].
Abstract
We extend linkage unfolding results from the wellstudied case of
polygonal
linkages to the more general case of linkages of polygons. More
precisely, we
consider chains of nonoverlapping rigid planar shapes (Jordan regions)
that
are hinged together sequentially at rotatable joints. Our goal is to
characterize the familes of planar shapes that admit locked chains,
where
some configurations cannot be reached by continuous reconfiguration
without
selfintersection, and which families of planar shapes guarantee
universal
foldability, where every chain is guaranteed to have a connected
configuration
space. Previously, only obtuse triangles were known to admit locked
shapes,
and only line segments were known to guarantee universal foldability.
We show
that a surprisingly general family of planar shapes, called slender
adornments,
guarantees universal foldability: roughly, the inward normal from any
point on
the shape's boundary should intersect the line segment connecting the
two
incident hinges. In constrast, we show that isosceles triangles with
any
desired apex angle less than 90 degrees admit locked chains, which is
precisely the threshold beyond which the inwardnormal property no longer
holds.
Previous ← → Next
Gill Barequet, Micha Moffie, Ares Ribó, and Günter Rote:
 Discrete
Mathematics and Theoretical
Computer Science AE (2005), 369374.
 INTEGERS: The
Electronic Journal of
Combinatorial Number Theory 6 (2006), article #A22, 37 pages.
Abstract
Using numerical methods, we analyze the growth in the number of
polyominoes
on a twisted cylinder as the number of cells increases. These
polyominoes are
related to classical polyominoes (connected subsets of a square grid)
that lie
in the plane. We thus obtain an improved lower bound of 3.980137 on the
growth rate of the number of polyominoes, which is also known as
Klarner's
constant. We use a dynamic programming approach. For storing
information about
partial polyominos, we make use of a bijection between "states" of our
system and Motzkin paths.
Previous ← → Next
Günter Rote and André Schulz:
Applied Mathematics Letters 19 (2006), 108112. doi:10.1016/j.aml.2005.03.010
Abstract
We show that a combinatorial question which has been studied in connection
with lower bounds for the knapsack problem by Brimkov and Dantchev (Applied
Mathematics Letters, 2002) is related to threshold graphs, threshold
arrangements, and other wellstudied combinatorial objects, and we correct an
error in the analysis given in that paper.
Previous ← → Next
Imre Bárány and Günter Rote:
Documenta
Mathematica 11 (2006), 369–391.
→BibTeX
Abstract
Every threeconnected planar graph with n vertices has a
drawing on an
O(n^{2})×O(n^{2})
grid in which all faces are strictly convex
polygons. More
generally, there is a drawing on an
O(nw) ×O(n^{3}/w)
grid, for any
choice of a parameter w
in the range 1<w<n.
These drawings are obtained by perturbing (not strictly) convex
drawings on
O(n) ×O(n) grids. Tighter bounds are
obtained when the faces have
fewer
sides. In the proof, we derive an explicit lower bound on the number of
primitive vectors in a triangle.
As an auxiliary result, we prove that the right triangle (0,0),(a,0),(a,b)
contains at least ab/4 primitive vectors, for every integer a≥1 and every
b≥2.
This paper improves a conference paper by the second author with the
same title,
in which a weaker bound of
O(n^{7/3})×O(n^{7/3})
on the grid size had been established:
Günter Rote:
Strictly convex drawings of planar graphs
In: Proceedings of the 16th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), Vancouver, January 2005, pp. 728–734.
→BibTeX
See Erratum
Previous ← → Next
1. Adrian Dumitrescu, Ansgar Grüne, and Günter Rote:
In: Abstracts of the 21st European Workshop on Computational
Geometry,
Eindhoven, March 2005, pp. 3740.
2. Adrian Dumitrescu, Annette EbbersBaumann, Ansgar Grüne,
Rolf Klein, and Günter Rote:
In: Proceedings of the Workshop on Algorithms and Data
Structures (WADS 2005), Waterloo, Canada, August 2005, Editors:
Alexandro
LópezOrtiz, Frank Dehne, and JörgRüdiger Sack.
Lecture
Notes in
Computer Science, 3608, SpringerVerlag, 2005, pp. 244255.
doi:10.1007/11534273_22
3. Adrian Dumitrescu, Annette EbbersBaumann, Ansgar Grüne,
Rolf Klein, and
Günter Rote:
Computational Geometry, Theory and Applications 36 (2006),
1638. arXiv:math/0407135
[math.MG]. doi:10.1016/j.comgeo.2005.07.004
(This is a detailed and combined version of 1 and
2.)
Abstract
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 Euclidean
distance. The
maximum detour over all pairs of points is called the geometric
dilation.
EbbersBaumann, Grüne and Klein have shown that every finite point
set is
contained in a planar graph whose geometric dilation is at most 1.678,
and
some point sets require graphs with dilation ≥pi/2=1.57... We
prove
a
stronger lower bound of (1+10^{11})pi/2 by relating graphs
with small dilation to
a problem of packing and covering the plane by circular disks.
The proof relies on halving pairs, pairs of points dividing a given
closed
curve C in two parts of equal length, and their minimum and
maximum
distances h and H. Additionally, we analyze
curves of
constant halving
distance (h=H), examine the relation of h to
other geometric
quantities and geometric problems (like Ulam's floating body problem)
and prove some new dilation bounds.
Previous ← → Next
Joe S. B. Mitchell, Günter Rote, and Lutz Kettner
(editors):
Proceedings of the TwentyFirst Annual Symposium on Computational Geometry
(SCG'05).
Pisa, June 6–8, 2005, Association for Computing Machinery, 2005;
x+387 pages.
Previous ← → Next
Adrian Dumitrescu and Günter Rote:
In: Proceedings of the 16th Canadian Conference on Computational Geometry
(CCCG'04), Montreal, August 911, 2004, pp. 162165.
Abstract
The Fréchet distance of two curves measures the resemblance of the
curves and is known to have applications in shape comparison and recognition.
We extend this notion to a set of curves and show how it can be computed
and approximated.
In particular, we show that the multiple Fréchet distance can be
bounded in terms of pairwise Fréchet distances, and we provide an
example which shows the tightness of this bound.
Previous ← → Next
Sergio Cabello, Erik D. Demaine, and Günter Rote:
 In: "Graph Drawing". GD 2003, Proceedings of the 11th
International
Symposium on Graph Drawing, Perugia, September 2003, Revised Papers.
Editor:
Giuseppe Liotta. Lecture Notes in Computer Science, 2912,
SpringerVerlag, 2004,
pp. 283–294.
doi:10.1007/9783540245957_26
 Journal of Graph Algorithms
and Applications
11, No. 1 (2007), pp. 259–276.
doi:10.7155/jgaa.00145
Abstract
We consider the problem of finding a planar embedding of a planar
graph
with
a prescribed Euclidean length on every edge. There has been substantial
previous work on the problem without the planarity restrictions, which
has
close connections to rigidity theory, and where it is easy to see that
the
problem is NPhard. In contrast, we show that the problem is
tractableindeed,
solvable in linear time on a real RAMfor planar embeddings of planar
3connected triangulations, even if the outer face is not a triangle.
This
result is essentially tight: the problem becomes NPhard if we consider
instead planar embeddings of planar 3connected infinitesimally rigid
graphs, a
natural relaxation of triangulations in this context.
Previous ← → Next
Günter Rote:
 In: Abstracts of the 20th European Workshop on Computational
Geometry,
Seville, March 2004, pp. 147150.
 Computational Geometry, Theory and Applications 37
(2007),
162174. (Special issue for the 20th European Workshop on
Computational
Geometry)doi:10.1016/j.comgeo.2005.01.004
Abstract
We consider the Fréchet distance between two curves which are
given
as a sequence of m+n curved pieces. If these pieces are
sufficiently wellbehaved, we can compute the Fréchet distance
in
O(mn log(mn)) time. The decision version of the
problem
can be
solved in O(mn) time.
Previous ← → Next
YiJen Chiang, Tobias Lenz, Xiang Lu, and Günter Rote:
Technical report ECGTR24430001, May 2003, 21 pages.
Computational Geometry, Theory and Applications 30
(2005), 165195. doi:10.1016/j.comgeo.2004.05.002
Abstract
Contour trees are used when highdimensional data are preprocessed
for
efficient extraction of isocontours for the purpose of visualization.
So far,
efficient algorithms for contour trees are based on processing the data
in
sorted order. We present a new algorithm that avoids sorting the
whole
data set, but sorts only the componentcritical points. They form only
a
small fraction of the points, for typical data that arise in practice.
The
algorithm works in any dimension.
In addition, we provide a comprehensive discussion of critical and
regular points
of piecewise linear functions of two and three variables.
Previous ← → Next
Oswin Aichholzer, Günter Rote, Bettina Speckmann, and Ileana
Streinu:
In: "Algorithms and Data Structures". Proceedings of the 8th
International Workshop on Algorithms and Data Structures (WADS 2003),
Ottawa, July 2003. Editors: Frank Dehne, JörgRüdiger
Sack, and Michiel Smid. Lecture Notes in Computer Science 2748,
SpringerVerlag, 2003, pp. 377–388. doi:10.1007/9783540450788_33
Abstract
The concept of a zigzag path of a pseudotriangulation is a tool that
allows to solve counting and optimization problems for
pseudottriangulations in a divideandconquer style. We present an
algorithm that enumerates all zigzag paths of a given point set with
respect to a given line in O(n^{2}) time per path and O(n^{2})
space.
Previous ← → Next
David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman
Servatius, and Walter Whiteley:
Discrete and Computational Geometry 32 (2004), 567–600.
(Special issue in honor of Lou Billera), doi:10.1007/s004540041139x,
arXiv:math/0309156 [math.MG].
Abstract
We study noncrossing frameworks in the plane for which the classical
reciprocal on the dual graph is also noncrossing. We give a complete
description of the selfstresses on noncrossing frameworks G
whose reciprocals are noncrossing, in terms of: the types of faces (only
pseudotriangles and pseudoquadrangles are allowed); the sign patterns in the
stress on G; and a geometric condition on the stress vectors at
some of the vertices.
As in other recent papers where the interplay of noncrossingness and rigidity
of straightline plane graphs is studied, pseudotriangulations show up as
objects of special interest. For example, it is known that all planar Laman
circuits can be embedded as a pseudotriangulation with one nonpointed vertex.
We show that for such pseudotriangulation embeddings of planar Laman circuits
which are sufficiently generic, the reciprocal is noncrossing and again a
pseudotriangulation embedding of a planar Laman circuit. For a singular
(nongeneric) pseudotriangulation embedding of a planar Laman circuit, the
reciprocal is still noncrossing and a pseudotriangulation, but its underlying
graph may not be a Laman circuit. Moreover, all the pseudotriangulations
which admit a noncrossing reciprocal arise as the reciprocals of such,
possibly singular, stresses on pseudotriangulation Laman circuits.
All selfstresses on a planar graph correspond to liftings to piecewise
linear surfaces in 3space. We prove characteristic geometric properties of the
lifts of such noncrossing reciprocal pairs.
Previous ← → Next
Ruth Haas, David Orden, Günter Rote, Francisco Santos,
Brigitte
Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter
Whiteley:
 in: Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 154–163. doi:10.1145/777792.777817
 Computational Geometry, Theory and Applications 31
(2005), 31–61. doi:10.1016/j.comgeo.2004.07.003, arXiv:math.CO/0307347.
(This is an
extended version of parts of the results of 1.)
Abstract
Pointed pseudotriangulations are planar minimally rigid graphs
embedded in the
plane with pointed vertices (adjacent to an angle larger than
pi). In
this paper we prove that the opposite statement is also true, namely
that
planar minimally rigid graphs always admit pointed embeddings, even
under
certain natural topological and combinatorial constraints. The proofs
yield
efficient embedding algorithms. They also provide the first
algorithmically
effective result on graph embeddings with oriented matroid constraints
other
than convexity of faces. These constraints are described by combinatorial
pseudotriangulations, first defined and studied in this paper.
Also of
interest are our two proof techniques, one based on Henneberg inductive
constructions from combinatorial rigidity theory, the other on a
generalization
of Tutte's barycentric embeddings to directed graphs.
Previous ← → Next
Helmut Alt, Christian Knauer, Günter Rote, and Sue Whitesides:
In: Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 164–170. doi:10.1145/777792.777818
In: "Towards a Theory of Geometric Graphs". Editor: János
Pach,
American Mathematical Society, 2004, Contemporary Mathematics,
Vol. 342,
pp. 1–13.
Abstract
We consider the problem of reconguring a linkage of rigid straight
segments
from a given start to a given target position with a continuous
nonintersecting motion. The problem is nontrivial even for trees in two
dimensions since it is known that not all congurations can be
recongured to
a straight position. We show that deciding recongurability for trees in
two
dimensions and for chains in three dimensions is PSPACEcomplete.
Previous ← → Next
Nina Amenta, Sunghee Choi, and Günter Rote:
in: Proceedings of the Nineteenth Annual Symposium on
Computational Geometry, San Diego, June 810, 2003. Association
for Computing Machinery, 2003, pp. 211219. doi:10.1145/777792.777824
Abstract
Randomized incremental constructions are widely used in computational
geometry,
but they perform very badly on large data because of their inherently
random
memory access patterns. We define a biased randomized insertion order
which
removes enough randomness to significantly improve performance, but
leaves
enough randomness so that the algorithms remain theoretically optimal.
We also give a precise definition and analysis of
"realistic"
problem
instances which are typical of data arising in practice and do not
exhibit
the theoretical worstcase behavior.
Previous ← → Next
Günter Rote:
EATCS Bulletin (Bulletin of the European Association for
Theoretical
Computer Science), No. 78, October 2002, 241246.
Abstract
We solve the general case of the bridgecrossing puzzle, where n
people
with
different walking speeds have to cross a bridge that can carry at most
two
people at a time. A flashlight is necessary to cross the bridge but
they
share only a single flashlight.
The solution is obtained through a graphtheoretic model.
Previous ← → Next
Günter Rote:
Pursuitevasion with imprecise target location.
In: Proceedings of the 14th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), Baltimore,
January 12–14, 2003. pp. 747–753. http://dl.acm.org/citation.cfm?id=644108.644231
Previous ← → Next
Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk:
In: Proceedings of the 14th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), Baltimore, January 12–14, 2003,
pp. 589–598.
Journal of Algorithms 49 (2003), 262–283. doi:10.1016/S01966774(03)000853
Abstract
We generalize the notion of the Fréchet distance from two curves
to a curve and a graph and to two graphs, and we give efficient
algorithms for computing the Fréchet distance in these cases.
3. Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan,
and Günter Rote:
in: Video and Multimedia Review of Computational Geometry,
Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 384–385.
doi:10.1145/777792.777855
Previous ← → Next
Günter Rote, Cao An Wang, Lusheng Wang, and Yinfeng Xu:
In: "Computing and Combinatorics". Proceedings of the 9th Annual
International Computing and Combinatorics Conference (COCOON 2003), Big Sky,
Montana, USA, July 2003. Editors: Tandy Warnow and Binhai Zhu. Lecture Notes
in Computer Science 2697, SpringerVerlag, 2003, pp. 445–454.
doi:10.1007/3540450718_45
→BibTeX
Abstract
We present three combinatorial bounds: the ratio of the size of minimum
pseudotriangulation of a point set S and the size of minimal
pseudotriangulation contained in a triangulation T of S,
the ratio of the size of the best minimal pseudotriangulation and the
worst minimal pseudotriangulation both contained in a given triangulation
T. We also present a lineartime algorithm for finding a minimal
pseudotriangulation contained in a given triangulation, and we study the
minimum pseudotriangulation containing a given set of noncrossing line
segments.
Previous ← → Next
Günter Rote:
Pseudotriangulations, polytopes, and how to expand linkages (invited talk).
in: Proceedings of the Eighteenth Annual Symposium on
Computational Geometry, Barcelona, June 2002. Association for
Computing Machinery, 2002, pp. 133–134. doi:10.1145/513400.513442
Previous ← → Next
Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter
Rote, and Carola Wenk:
In: Proceedings of the 13th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), San Francisco,
January 2002, pp. 453–454. doi:10.1145/545381.545441
Algorithmica 38 (2003), 145–160.
doi:10.1007/s0045300310470
Abstract
We address the problem of how to cover a set of required points by a small
number of axisparallel ellipses that avoid a second set of forbidden points.
We study geometric properties of such covers and present an efficient
randomized approximation algorithm for the cover construction. This question
is motivated by a pattern recognition task where one has to identify
ellipseshaped protein spots in twodimensional electrophoresis images.
Previous ← → Next
Robert Elsässer, Burkhard Monien, Günter Rote, and Stefan
Schamberger:
Toward optimal diffusion matrices.
Technical report ALCOMFTTR0298, May 2002, 8 pages.
Previous ← → Next
Robert Elsässer, Burkhard Monien, Günter Rote, and Stefan
Schamberger:
Toward optimal diffusion matrices.
In: "International Parallel and Distributed Processing Symposium." IPDPS
2002, Proceedings. 15–19 April 2002, Fort Lauderdale, California. IEEE
Computer Society Press 2002, pp. 0067b, 8 pages. doi:10.1109/IPDPS.2002.1015569
Previous ← → Next
Günter Rote:
Séminaire
Lotharingien de Combinatoire B38b, (1997), 6 pages, (Zbl 980.13720).
Comment on a paper by Helmut Prodinger in the same issue.
Abstract
We give three combinatorial proofs for the number of binary trees having a
given number of nodes with 0, 1, and 2 children. We extend these results
to ordered trees with given distribution of nodes according to their numbers
of children.
Previous ← → Next
Robert Connelly, Erik D. Demaine, and Günter Rote:
in: "Physical Knots: Knotting, Linking, and Folding Geometric Objects in
R^{3}." Editors: Jorge Alberto Calvo, Kenneth C. Millett, and
Eric J. Rawdon. Contemporary Mathematics 304, American Mathematical Society
2002, pp. 287311,
Abstract
We propose a new algorithmic approach for analyzing whether planar linkages
are locked in many cases of interest. The idea is to examine selftouching
or degenerate frameworks in which multiple edges coincide geometrically.
We show how to study whether such frameworks are locked using techniques
from rigidity theory, in particular firstorder rigidity and equilibrium
stresses. Then we show how to relate locked selftouching frameworks to
locked frameworks that closely approximate the selftouching frameworks.
Our motivation is that most existing approaches to locked linkages
are based on approximations to selftouching frameworks. In particular,
we show that a previously proposed locked tree in the plane can be easily
proved locked using our techniques, instead of the tedious arguments required
by standard analysis. We also present a new locked tree in the plane
with only one degree3 vertex and all other vertices degree 1 or 2. This
tree can also be easily proved locked with our methods, and implies that
the result about opening polygonal arcs and cycles (Connelly,
Demaine, and Rote 2002) is the best possible.
Previous ← → Next
Günter Rote, Francisco Santos, and Ileana Streinu:
In: Discrete and Computational Geometry—The Goodman–Pollack
Festschrift. Editors: Boris Aronov, Saugata Basu, János
Pach, and Micha Sharir, Algorithms and Combinatorics, vol. 25,
Springer Verlag, Berlin 2003, pp. 699–736.
doi:10.1007/9783642555664_33,
arXiv:math/0206027 [math.CO].
Abstract
We introduce the polytope of pointed pseudotriangulations of a point set in
the plane, defined as the polytope of infinitesimal expansive motions of the
points subject to certain constraints on the increase of their distances. Its
1skeleton is the graph whose vertices are the pointed pseudotriangulations of
the point set and whose edges are flips of interior pseudotriangulation
edges.
For points in convex position we obtain a new realization of the
associahedron, i.e., a geometric representation of the set of
triangulations of
an ngon, or of the set of binary trees on n vertices, or of many other
combinatorial objects that are counted by the Catalan numbers. By
considering
the 1dimensional version of the polytope of constrained expansive
motions we
obtain a second distinct realization of the associahedron as a
perturbation of
the positive cell in a Coxeter arrangement.
Our methods produce as a byproduct a new proof that every simple
polygon or
polygonal arc in the plane has expansive motions, a key step in the
proofs
of the Carpenter's Rule Theorem by Connelly,
Demaine and Rote (2000) and by
Streinu (2000).
Previous ← → Next
Dana Randall, Günter Rote, Francisco Santos, and Jack Snoeyink:
In: Proceedings of the 13th Canadian Conference on Computational
Geometry (CCCG'01), Waterloo, August 6–10, 2001. Editor:
T. Biedl; pp. 149–152.
→BibTeX
Abstract
Motivated by several open questions on triangulations and pseudotriangulations,we
give closed form expressions for the number of triangulations and the number
of minimum pseudotriangulations of n points in wheel configurations,
that is, with n−1 in convex position.Although the numbers of triangulations
and pseudotriangulations vary depending on the placement of the interior
point, their difference is always the (n−2)^{nd} Catalan
number.
We also prove an inequality #PT <= 3^{i}#T for the
numbers of minimum pseudotriangulations and triangulations of any point
configuration with i interior points.
Previous ← → Next
Peter Braß, Günter Rote, and Konrad J. Swanepoel:
Discrete and Computational Geometry 26 (2001), 51–58. doi:10.1007/s0045400100106
Abstract
We show the following two results on a set of n points in the
plane, thus answering questions posed by Erdös and Purdy (1971): 1. The
maximum number of triangles of maximum area (or of maximum perimeter) in a
set of n points in the plane is exactly n. 2. The
maximum possible number of triangles of minimum positive area in a set of
n points in the plane is Θ(n^{2}).
Previous ← → Next
Friedrich Eisenbrand and Günter Rote:
In: IPCO 2001  Proceedings of the 8th Conference on Integer Programming
and Combinatorial Optimization, Utrecht, June 13–15, 2001. Editors: K.
Aardal, B. Gerards. Lecture Notes in Computer Science 2081, SpringerVerlag,
2001, pp. 78–89. doi:10.1007/3540455353_7
Abstract
We show that a 2variable integer program defined by m constraints involving
coefficients with at most s bits can be solved with O(m+slogm)
arithmetic operations or with O(m+logmlogs)M(s)
bit operations, where M(s) is the time needed for sbit
integer multiplication.
Thus, when the number of constraints is fixed, integer programming
in two variables is not harder than greatest common divisor computation.
Our algorithm avoids the binary search that is associated with the usual
approach by letting the objective function slide into the polyhedron, until
the lattice width of the truncated polyhedron equals the flatness constant
from Khintchin's Flatness theorem.
Previous ← → Next
Friedrich Eisenbrand and Günter Rote:
In: Cryptography and Lattices—International Conference, CaLC
2001, Providence, Rhode Island, March 29–30, 2001, Revised
Papers. Editor: Joseph H. Silverman. Lecture Notes in Computer
Science 2146, SpringerVerlag, 2001, pp. 32–44. doi:10.1007/3540446702_4
Abstract
We show that a positive definite integral ternary form can be reduced with
O(M(s)log^{2}s) bit operations, where
s is the binary encoding length of the form and M(s)
is the bitcomplexity of sbit integer multiplication.
This result is achieved in two steps. First we prove that the the classical
Gaussian algorithm for ternary form reduction, in the variant of Lagarias,
has this worst case running time. Then we show that, given a ternary form
which is reduced in the Gaussian sense, it takes only a constant number
of arithmetic operations and a constant number of binaryform reductions
to fully reduce the form.
Finally we describe how this algorithm can be generalized to higher
dimensions. Lattice basis reduction and shortest vector computation in
fixed dimension d can be done with O(M(s)log^{d1}s)
bitoperations.
Previous ← → Next
Robert Connelly, Erik D. Demaine, and Günter Rote:
 Every polygon can be untangled
In: Proceedings of the 16th European Workshop on Computational Geometry,
BenGurion University of the Negev, Israel, January 2000, pp. 62–65.
 In: Proceedings of the 41st Annual Symposium on Foundations
of
Computer
Science, Redondo Beach, California, (FOCS), November 12–14, 2000. IEEE
Computer
Society Press, 2000, pp. 432–442. doi:10.1109/SFCS.2000.892131
 Discrete and Computational Geometry 30
(2003), 205–239. doi:10.1007/s0045400300067
(This
is a more detailed version of 2.)
 Technical
report B0202, Revised version, February 2002, 49 pages. (This
is a version of 3 expanded by an appendix with
supplementary
proofs.)
Abstract
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 cycle. We prove
that
the linkage can be continuously moved so that the arcs become straight,
the cycles become convex, and no bars cross while preserving the bar
lengths.
Furthermore, our motion is piecewisedifferentiable, does not decrease
the distance between any pair of vertices, and preserves any symmetry
present
in the initial configuration. Furthermore, our motion strictly
increases
the distance between every pair of vertices that are not connected by a
straight subchain of bars and are not on a common convex chain.
See also Erik
Demaine's linkage page for information about related problems.
Previous ← → Next
Günter Rote:
In: "Computational Discrete Mathematics." Editor: Helmut Alt. Lecture Notes
in Computer Science 2122, SpringerVerlag, 2001, pp. 119–135. doi:10.1007/354045506X_9
Abstract
The most common algorithm for computing the determinant of an n×nmatrix
is Gaussian elimination and needs
O(n^{3}) arithmetic operations. On the other
hand, the explicit definition of the determinant as the sum of n!
products shows that the determinant can be computed without divisions.
In this introductory survey, we will describe an O(n^{4})
algorithm that works without divisions and goes back to Faddeyev and Faddeyeva.
We will look at this algorithm from a combinatorial and an algebraic viewpoint.
We will also consider the Pfaffian of a skewsymmetric matrix, a quantity
closely related to the determinant. The results are in many ways analogous
to those for the determinant, but the algebraic aspect of the algorithms
is not explored yet.
Previous ← → Next
Günter Rote and Gerhard J. Woeginger:
Acta Cybernetica 13 (1998), 423429.
Abstract
This paper investigates a singlemachine sequencing problem where the jobs
are divided into families, and where a setup time is incurred whenever
there is a switch from a job in one family to a job in another family.
This setup only depends on the family of the job next to come and hence
is sequence independent. The jobs have duedates, and the objective is
to find a sequence of jobs that minimizes the number of tardy jobs.
The special case of this problem where in every family the jobs have
at most two different due dates is known to be NPcomplete [Bruno and Downey
1978]. The main result of this paper is a polynomial time algorithm for
the remaining open case where in every family all the jobs have the same
due date. This case may be formulated as a dual resource allocation problem
with a treestructured constraint system, which can be solved to optimality
in polynomial time.
Previous ← → Next
Tamás Fleiner, Volker Kaibel, and Günter Rote:
European Journal of Combinatorics 21 (2000), 121–130.
doi:10.1006/eujc.1999.0326
Abstract
We prove two upper bounds on the number of facets that a ddimensional
0/1polytope (a polytope whose vertices have coordinates 0 and 1) can have.
The first one is 2(d1)!+2(d1), which is the best one currently
known for small dimensions, while the second one, O((d2)!),
is the best bound for large dimensions.
This question was posed by Günter Ziegler in his book Lectures
on Polytopes (1995) (exercise 0.15). Our bounds improve the best previously
known bound of O(d!), which follows from a simple volume
argument due to Imre Bárány. The known lower bounds are exponential,
the current record being 3.6^{d} for large enough d.
(Thomas Christof and Gerhard Reinelt 1997). They follow from explicit polytopes
in low dimensions. (Since the paper was published, superexponential lower
bounds were proved by Bárány and Por.)
We also prove bounds for the number of faces of lower dimensions, and
for integral convex polytopes with coordinates between 0 and k.
Previous ← → Next
Rainer E. Burkard, Yixun Lin, Helidon Dollani, and Günter Rote:
SIAM Journal on Discrete Mathematics 14 (2001),
498–509.
doi:10.1137/S0895480198340967
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 possible. We derive algorithms
with linear running time for the cases when G is a path or a star,
thus improving previous results of Tamir (1988). For subdivided stars we
present an algorithm of running time O(n log n). For
general trees, we improve an algorithm of Tamir by a factor of log n.
Moreover, we describe a linear algorithm for the unweighted center problem
on an arbitrary tree with neutral and obnoxious vertices.
Previous ← → Next
Martin Gavalec and Günter Rote:
Tatra Mountains Mathematical Publications 16 (1999), 61–79.
Abstract
Given an n×n matrix A, the
problem is to decide whether there is an nvector
x such that the sequence of matrix powers A,
A^{2}, A^{3}, ... has the
same period length as the sequence Ax,
A^{2}x, A^{3}x, ... of
iterates of x. In these matrixmatrix and matrixvector
multiplications, the usual operations + and * are replaced by max and
min, respectively.
In general, this problem is NPcomplete. Two conditions are
described, which both together imply that it can be solved in
O(n^{2}) time. If only one of the
conditions is satisfied, the problem remains NPcomplete.
Previous ← → Next
Günter Rote and Gerhard J. Woeginger:
Journal of Scheduling 1 (1998), 149–155.
doi:10.1002/(SICI)10991425(1998100)1:3<149::AIDJOS10>3.0.CO;24
Abstract
We consider the scheduling problems F2.C_{max}
and F2nowaitC_{max}, i.e.
makespan minimization in a two machine flow shop, with and without no
wait in process. For both problems solution algorithms based on sorting
with O(n log n) running time are known, where n denotes
the number of jobs
[Johnson 1954, Gilmore and Gomory 1964].
We prove that no asymptotically faster algorithms can solve these problems.
This is done by establishing Ω(n log n) lower bounds
in the algebraic
computation tree model of computation. Moreover, we develop for every
ε>0 approximation algorithms with linear running time
O(n log(1/ε))
that deliver feasible schedules whose makespan is at
most 1+ε times the
optimum makespan.
Previous ← → Next
Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar
Langetepe, and Günter Rote:

In: "Algorithms and Computation—Ninth Annual International
Symposium on Algorithms and Computation. Taejon, Korea, December
1998". Proceedings of ISAAC'98. Editors: KyungYong Chwa and
Oscar H. Ibarra. Lecture Notes in Computer Science 1533,
SpringerVerlag, 1998, pp. 317–327. doi:10.1007/3540493816_34

Discrete Applied Mathematics 109 (2001), 3–24. doi:10.1016/S0166218X(00)00233X
Abstract
For an angle φ between 0 and 180^{o}, we consider the class of
oriented curves which are φselfapproaching in the following sense:
for any point A on the considered curve, the rest of the curve is
inside a wedge of angle φ at A. This is a direct generalization
of selfapproaching curves which are 90^{o}selfapproaching. We
prove a tight upper bound on the length of a φselfapproaching curve
in terms of the distance between its endpoints. The upper bound only depends
on the angle φ.
This problem arises in the performance analysis of certain online navigation
strategies. A closely related problem concerns curves
with increasing chords.
Previous ← → Next
Jerrold R. Griggs and Günter Rote:
In: "Contemporary Trends in Discrete Mathematics." Editors: Ronald L.
Graham, Jan Kratochvíl, Jaroslav Nešetřil, and Fred S. Roberts.
DIMACS series in discrete mathematics and theoretical computer science,
American Mathematical Society, 1999; pp. 139142.
Abstract
An analog of the LittlewoodOfford problem that was 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
general position. This note reviews past progress and motivation for this
problem, and presents a construction that gives a respectable new lower
bound, Omega(2^{n}n^{13d/2}), which compares
for d>1 to the previously known upper bound O(2^{n}n^{1d/2}).
Previous ← → Next
Prosenjit Bose, Hazel Everett, Sándor Fekete, Michael E. Houle,
Anna Lubiw, Henk Meijer, Kathleen Romanik, Günter Rote, Tom Shermer,
Sue Whitesides, and Christian Zelle:
Journal of Graph Algorithms and
Applications 2, no. 3 (1998), 1–16. doi:10.7155/jgaa.00006
Abstract
We propose a 3dimensional visibility representation of graphs in which
vertices are mapped to horizontal axisparallel rectangles floating in
3space, with edges represented by vertical lines of sight. We apply an
extension of the ErdösSzekeres Theorem in a geometric setting to
obtain an upper bound of 56 for size of the largest complete graph which
is representable. On the other hand, we construct a representation of the
complete graph with 22 vertices. These are the best existing bounds.
Previous ← → Next
Imre Bárány, Günter Rote, William Steiger, and CunHui
Zhang:
Discrete and Computational Geometry 23 (2000), 35–50. doi:10.1007/PL00009490
Abstract
We consider the probability that n points drawn uniformly at random from
the unit square form a convex chain together with the two corners (0,0)
and (1,1). Conditioned under this event, these chains converge to a parabolic
limit shape. We even get an almost sure limit theorem, which uses only
probabilistic arguments and which strengthens similar limit shape statements
established by other authors. The main result is an accompanying central
limit theorem for these chains. A weak convergence result implies several
other statements concerning the deviations between random convex chains
and their limit.
Previous ← → Next
Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and YinFeng Xu:
 In: Proceedings of the Second International Symposium on Operations Research
and its Applications (ISORA'96), Guilin, China, December 11–13, 1996. Editors:
DingZhu Du, XiangSun Zhang, and Kan Cheng. Lecture Notes in Operations
Research 2, World Publishing Corporation, Beijing 1996, pp. 309–318.
 Journal of Combinatorial Optimization 2 (1999),
361–369.
Abstract
The wellknown greedy triangulation of a finite point set is obtained by
looking at the edges in order of increasing length and inserting an edge if
it does not cross previously inserted ones. Exploiting the concept of
socalled light edges, we introduce a new way of defining the greedy
triangulation. It does not rely on the length ordering of the edges. It
decomposes the greedy triangulation into levels, and the number k of levels
allows us to bound the total edge length by
3·2^{k+1} times the minimumweight
triangulation of the point set.
Previous ← → Next
Günter Rote and Guochuan Zhang:
SFBBericht Nr. 71, June 1996, 34 pages.
Abstract
We consider a variant of the classical "jeep problem", whose origins date
back more than 1000 years. We have n cans of fuel on the edge of
a desert and a jeep whose tank can hold the contents of one can. The jeep
can carry one can in addition the fuel in its tank, and therefore it can
establish depots in the desert for later use. When a can is opened, the
fuel must immediately be filled into the jeep's tank. The goal is to find
the farthest point in the desert which the jeep can reach.
We give a simple algorithm for the jeep which improves previous solutions
of Derick Wood (1984) and Ute and Wilfried Brauer (1989), and we use a
linear programming formulation to derive an upper bound which shows that
our solution is optimal.
Previous ← → Next
Helmut Alt, Ulrich Fuchs, Günter Rote, and Gerald Weber:

In: Algorithms—ESA '96", Proc. Fourth Annual European Symposium
on Algorithms, Barcelona, September 25–27, 1996. Editors: Josep
Díaz and
María Serna. Lecture Notes in Computer Science 1136, SpringerVerlag,
1996, pp. 320–333.
doi:10.1007/3540616802_65
 Algorithmica
21 (1998), 89–103. doi:10.1007/PL00009210
Abstract
We consider the problem of moving one convex figure over another, minimizing
the area of their symmetric difference. We show that if we just let the two
centers of coincide, the resulting symmetric difference is within a factor of
11/3 of the optimum. This leads to efficient approximate matching algorithms
for convex figures.
Previous ← → Next
Marek Lassak, Janusz Januszewski, Günter Rote, and Gerhard Woeginger:
Beiträge zur Algebra
und Geometrie  Contributions to Algebra and Geometry 37 (no. 1) (1996),
5165, (Zbl 863.52010).
Abstract
In the online covering problem for covering the unit cube by cubes, we
are given a sequence of smaller cubes of side lengths s_{1},
s_{2},...,s_{n}, and we have to place them
in such a way that the whole unit cube in ddimensional Euclidean
space is covered if possible. The cubes are axisparallel, they are allowed
to overlap, but the algorithm must place the ith cube before knowing
the future cubes s_{i}_{+1}, s_{i}_{+2},...
We describe algorithms which are guaranteed to find a covering online
provided that the total volume (the sum of s_{i}^{d})
is at least 2^{d}+3. (The true bound is actually a little
smaller.) This performance guarantee is quite strong, considering that
the existence of an (offline) covering can only be ensured if the total
volume is at least 2^{d}1. The best previous online bound
was 4^{d}, due to Wlodek Kuperberg.
We reduce this problem to an online interval covering problem for qadic
intervals. In this problem, we have to cover the unit interval [0,1] by
intervals whose sizes are negative powers of q. The endpoints of
an interval of side length q^{k} are restricted
to fall on multiples of q^{k}. For this class of
problems, we consider a kind of simple online algorithm, the socalled
"method of the nth segment", for some integer n>1. We give
performance guarantees for these algorithms, and show that the cases n=q+1,
n=q+2, and n=q+1 give the best results, depending
on q. For q=2^{d} these methods carry over
to the covering problem for ddimensional cubes whose side lengths
are powers of 2.
Mathematische Semesterberichte 43 (1996), 94100.
Abstract
This paper contains a different proof of a special case of the main result
of the above paper, complemented by a lowerbound construction.
Previous ← → Next
1. Oswin Aichholzer, Franz Aurenhammer, SiuWing Cheng, Naoki Katoh,
Michael
Taschwer, Günter Rote, and YinFeng Xu:
Discrete and Computational Geometry 16 (1996), 339359, (Zbl
857.68110). doi:10.1007/BF02712872
2. Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and
Michael Taschwer:
In: Proceedings of the Eleventh Annual Symposium on Computational
Geometry,
Vancouver, June 57, 1995. Association for Computing Machinery, 1995;
pp.
220229. doi:10.1145/220279.220303.
This is an extended abstract of a preliminary version of 1.
Abstract
Given two triangulations of a point set in the plane, there is always a
matching between their edge sets which matches each edge in one
triangulation
with the identical edge or with a crossing edge in the other
triangulation.
A similar result holds for the triangles (instead of the edges) of a
triangulation.
This matching lemma can be formulated in the general setting of
independence
systems, and it is easy to prove.
As an application, it is possible to compute in polynomial time
lower
bounds for the minimum weight triangulation by solving an assignment
problem
or more general network flow problems. We exhibit an
easytorecognize
class of point sets where the minimumweight triangulation coincides
with
the greedy triangulation. These are the sets for which the
"light"
edges, which are crossed by no shorter segments, form a triangulation.
Previous ← → Next
Robert L. Scot Drysdale, Günter Rote, and Oswin Aichholzer:
A simple linear time greedy triangulation algorithm for uniformly distributed
points.
Bericht IIG408, February 1995, Technische Universität Graz, Institute
für Informationsverarbeitung, February 1995, 16 pages.
Previous ← → Next
Mordecai J. Golin and Günter Rote:
 Extended abstract in: "Automata, Languages and Programming".
Proceedings
of the 22nd International Colloquium on Automata, Languages, and
Programming
(ICALP 95), Szeged, Hungary, July 1995. Editor: F. Gécseg.
Lecture
Notes in Computer Science 944, SpringerVerlag, 1995, pp. 256267.
 IEEE Transactions on Information Theory 44
(1998),
17701781.
Abstract
We consider the problem of constructing minimum cost prefixfree codes
when the encoding alphabet contains letters of unequal length. The
complexity
of this problem has been unclear for thirty years. The only algorithm
known
for its solution involves a reduction to integer linear programming,
due
to Karp (1961).
In this paper we introduce a dynamic programming solution to the
problem.
It optimally encodes n words in O(n^{C}+2)
time,
if the costs of the letters are integers between 1 and C. While
still leaving open the question of whether the general problem is
solvable
in polynomial time our algorithm seems to be the first one that runs in
polynomial time for fixed letter costs.
Some numerical results are reported, including solutions using
Karp's
integer programming formulations, which was solved using AMPL and
CPLEX.
The AMPL model is included in the appendix and in the PostScriptfile.
Previous ← → Next
Rainer E. Burkard, Eranda Çela, Günter Rote, and Gerhard J.
Woeginger:
 Extended abstract in: "Integer Programming and Combinatorial Optimization".
Proceedings of the 5th International IPCO Conference, Vancouver, Canada,
June 1996. Editors: W. H. Cunningham, S. T. McCormick, and M. Queyranne.
Lecture Notes in Computer Science 1084, SpringerVerlag, 1996, pp. 204–218.
doi:10.1007/3540613102_16

Mathematical Programming 82 (1998), 125–158. doi:10.1007/BF01585868
Abstract
We investigate a restricted version of the Quadratic Assignment Problem
(QAP), where one of the coefficient matrices is an AntiMonge matrix with
nondecreasing rows and columns and the other coefficient matrix is a symmetric
Toeplitz matrix. This restricted version is called the AntiMongeToeplitz
QAP. There are three wellknown combinatorial problems that can be modeled
via the AntiMongeToeplitz QAP:

(P1) The Turbine Problem, i. e., the assignment of given masses
to the vertices of a regular polygon such that the distance of the center
of gravity of the resulting system to the center of the polygon is minimized.

(P2) The Traveling Salesman Problem on symmetric Monge distance matrices.

(P3) The arrangement of data records with given access probabilities in
a linear storage medium in order to minimize the average access time.
We identify conditions on the Toeplitz matrix that lead to a simple solution
for the AntiMonge–Toeplitz QAP: The optimal permutation can be given in
advance without regarding the numerical values of the data. The resulting
theorems generalize and unify several known results on problems (P1), (P2),
and (P3). We also show that the Turbine Problem is NPhard and consequently,
that the AntiMonge–Toeplitz QAP is NPhard in general.
Previous ← → Next
Helmut Alt, Oswin Aichholzer, and Günter Rote:
 Extended abstract in: Proceedings of the
Tenth Annual Symposium on Computational
Geometry, Stony Brook, New York, June 68, 1994. Association
for Computing Machinery, 1994, pp. 8592. doi:10.1145/177424.177555
 International Journal on Computational Geometry and
Applications
7 (1997), pp. 349363, (Zbl 883.68118). doi:10.1142/S0218195997000211
Abstract
For two given point sets, we present a very simple (almost trivial)
algorithm
to translate one set so that the Hausdorff distance between the two
sets is
not larger than a constant factor times the minimum Hausdorff distance
which
can be achieved in this way. The algorithm just matches the socalled
Steiner
points of the two sets. The focus of our paper is the general study of
reference points (like the Steiner point) and their properties with
respect to
shape matching. For more general transformations than just
translations, our
method eliminates several degrees of freedom from the problem and thus
yields
good matchings with improved time bounds.
Previous ← → Next
Günter Rote:
Theoretical Computer Science 172 (1997), 303–308. doi:10.1016/S03043975(96)001855
Abstract
We find the shortest nonzero vector in the lattice of all integer multiples
of the vector (a,b) modulo m, for given integers 0<a,b<m.
We reduce the problem to the computation of a Minkowskireduced basis for
a planar lattice and thereby show that the problem can be solved in O(log
m (log log m)^{2}) bit operations.
Previous ← → Next
János Aczél, Günter Rote, and Jens Schwaiger:
1a. In: “VIII. Mathematikertreffen ZagrebGraz”, Universität Graz,
9.11. 12. 1993. Editors: Detlef Gronau and Ludwig Reich. Grazer
Mathematische Berichte 323, 1994, pp. 1–20, (Zbl 816.39003).
1b. Quarterly of Applied Mathematics 54 (1996),
475–499, (Zbl 859.39010).
2a. In: “Actes 5eConférence Internationale/Proc. Fifth International
Conference IPMU, Traitement d'information et gestion d'incertitutes dans les
systèmes à base de connaissances/Information Processing and
Management of Incertainty in KnowledgeBased Systems, Paris, 4–8 juillet/July,
1994, Cité Internationale Universitaire”, Paris 1994, Vol. 1,
pp. 569–570.
2b. In: The Ordered Weighted Averaging Operators — Theory and Applications.
Editors: Ronald R. Yager and Janusz Kacprzyk, Elsevier, Dordrecht 1997,
pp. 36–38.
Abstract
YewKwang Ng (Quart. Appl. Math. 49 (1991), 289301) listed several
“reasonable properties” for equivalent changes of
probabilities and other proportions. He produced a family of
functions satisfying all properties and asked whether there exist
essentially different ones, conjecturing that the answer is negative.
We show that the answer is positive, by constructing uncountably many
families of functions satisfying all properties. We show also that
there are no other solutions. Our method establishes connections with
webs (nets) and iteration groups. This may be of interest both in
itself and for applications.
Previous ← → Next
Johannes Hagauer and Günter Rote:
1. Extended abstract in: "Algorithms  ESA '93", Proc. First Annual
European Symposium on Algorithms, Bad Honnef, Germany, September 30  October
2, 1993. Editor: Thomas Lengauer. Lecture Notes in Computer Science 726,
SpringerVerlag, 1993, pp. 192199.
2. Computational Geometry, Theory and Applications 8 (1997), pp.
8795.
Abstract
Given n points in the plane, we partition them into three classes
such that the maximum distance between two points in the same class is
minimized. The algorithm takes O(n^{2} log^{2}n)
time.
Previous ← → Next
Günter Rote and Robert Franz Tichy:
Mathematical and Computer Modelling 23 (1996), 923, (Zbl 855.11041).
Abstract
QuasiMonteCarlo methods are wellknown for solving different problems of
numerical analysis such as integration, optimization, etc. The error estimates
for global optimization depend on the dispersion of the point sequence with
respect to balls.
In general, the dispersion of a point set with respect to various classes of
range spaces, like balls, squares, triangles, axisparallel and arbitrary
rectangles, spherical caps and slices, is the area of the largest empty
range, and it is a measure for the distribution of the points. The main
purpose of our paper is to give a survey about this topic, including some
folklore results. Furthermore, we prove several properties of the dispersion,
generalizing investigations of Niederreiter and others concerning balls. For
several wellknown uniformly distributed point sets we estimate the dispersion
with respect to triangles, and we also compare them computationally. For the
dispersion with respect to spherical slices we mention an application to the
polygonal approximation of curves in space.
Previous ← → Next
Günter Rote and Robert Franz Tichy:
Anzeiger der Österreichischen Akademie der Wissenschaften,
Mathematischnaturwissenschaftliche Klasse, Abteilung II 132 (1995), 310, (Zbl
865.11054).
Abstract
We describe and analyze a procedure for the polygonal approximation of
spatial curves using “welldistributed” points on the sphere. Here the
dispersion of the point set with respect to spherical slices
(intersections of two halfspheres) plays a role.
Previous ← → Next
Günter Rote:
Mathematical Proceedings of the Cambridge Philosophical Society 115
(1994), 112, (Zbl 802.51023).
Abstract
A curve has increasing chords if AD ≥ BC for any four pointsA,B,C,D
lying on the curve in that order. The length of such a curve that connects
two points at distance 1 is at most 2*pi/3 in two dimensions, which is
the optimal bound, and less that 30 in three dimensions.
A related problem concerns the length of generalized
selfapproaching curves.
Previous ← → Next
Vladimir G. Deineko, René van Dal, and Günter Rote:
Information Processing Letters 51 (1994), 141148, (Zbl 806.90121).
Abstract
We solve the special case of the Euclidean Traveling Salesman Problem
where nm cities lie on the boundary of the convex hull of all n
cities, and the other m cities lie on a line segment inside this
convex hull by an algorithm which needs O(mn) time and O(n) space.
This generalizes and improves previous results of Cutler (1980) for the
3line Traveling Salesman Problem.
Previous ← → Next
Günter Rote, Christian Schwarz, and Jack Snoeyink:
In: Proceedings of the Fifth Canadian Conference on Computational
Geometry,
Waterloo, August 59, 1993. Editor: A. Lubiw,
J. Urrutia;
pp. 258263.
Abstract
The width of a set of n
points in the plane is the smallest distance between two parallel lines
that enclose the set. We maintain the set of points under insertions
and deletions of points and we are able to report an approximation of
the width of this dynamic point set. Our data structure takes linear
space and allows for reporting the approximation with relative accuracy
epsilon in O(sqrt(1/epsilon)
log n) time; and the update
time is O(log^{2} n). The method uses the
tentative
pruneandsearch strategy of Kirkpatrick and Snoeyink
Previous ← → Next
Alon Efrat, Günter Rote, and Micha Sharir:

In: Proceedings of the Fifth Canadian Conference on Computational Geometry,
Waterloo, August 5–9, 1993. Editor: A. Lubiw, J. Urrutia;
pp. 115–120.
→BibTeX

Computational Geometry: Theory and Applications 3
(1993), 277–288, (Zbl 801.68167). doi:10.1016/09257721(93)900182 →BibTeX
Abstract
We call a line l
a separator for a set S of objects
in the plane if l avoids all the objects and partitions S into
two nonempty subsets, one consisting of objects lying
above l and the other of objects lying below l. In
this paper we present an O(n log n)time
algorithm for finding a separator line for a set of n segments,
provided the ratio between the diameter of the set of segments and the
length of the smallest segment is bounded.
No subquadratic algorithms are known for the general case.
Our algorithm is based on the recent results of
Matousek, Pach, Sharir, Sifrony, and Welzl (1994)
concerning the union of “fat” triangles, but we also include an
analysis which improves the bounds obtained by
Matoušek, Pach, Sharir, Sifrony and Welzl.
Previous ← → Next
Günter Rote:
Journal of Number Theory 46 (1993), 196213, (Zbl 804.11023).
Abstract
We discuss infinite 01sequences which contain 2n different subwords
of length n, for every n.
We give a method which can in principle construct all such sequences,
using purely combinatorial tools. After giving some concrete examples of
sequences with different properties, we give alternate methods for constructing
special classes of sequences of complexity 2n.
The special class of sequences whose sets of subword are closed under
complementation (exchanging 0's and 1's) is closely related to Sturmian
sequences (sequences of complexity n+1), which are well understood.
Keywords: Lsystems, infinite words, iterated morphisms
Previous ← → Next
Günter Rote:
In: "Automata, Languages and Programming". Proceedings of the 19th International
Colloquium on Automata, Languages, and Programming (ICALP 92), Wien, Austria,
July 1992. Editor: W. Kuich. Lecture Notes in Computer Science 623, SpringerVerlag,
1992, pp. 404415.
Abstract
The bounded Lipschitz distance can be used as a distance measure between
polygons or between functions. It has several properties which make
it attractive to use from the viewpoint of applications like pattern matching
or quality control of woven fabrics. There are several alternative
definitions of the metric, some of which are interesting in their own right.
The bounded Lipschitz distance is related to the MongeKantorovich mass
transfer problem, whose history goes back to 18th century work of G. Monge
and to L. Kantorovitch.
We also give an algorithm for computing the metric, and we discuss possible
implementations.
Previous ← → Next
Günter Rote:
In: Proceedings of the Eighth Annual Symposium on Computational
Geometry, Berlin, June 10–12, 1992. Association for
Computing Machinery, 1992; pp. 26–32.
doi:10.1145/142675.142685
Abstract
We present an algorithm for enumerating the faces of the convex hull
of a given set P of n points in d dimensions.
The main features of the algorithm are that it uses little extra storage and
that it addresses degeneracy explicitly.
It is based on an idea that was recently introduced by Avis and Fukuda (1991)
for their convex hull algorithm: The idea is to take a pivoting rule from
linear programming and to “invert” the path that it takes to the optimal
solution in all possible ways, thereby visiting all feasible bases in a
depthfirst search manner.
Theoretical considerations and computational tests have established that the
method takes a long time for degenerate point sets.
The reason is that, in the case of degenerate polytopes, the number of
feasible bases may exceed the number of facets by far.
Therefore we propose a variation of the method that takes degeneracies into
account explicitly: Instead of visiting all feasible bases, the algorithm
visits all facets.
The manner of visiting facets is analogous to the convex hull algorithm of
Chand and Kapur (1970) as it is described and analyzed in Swart (1985).
We also propose a hybrid algorithm that saves time in nondegenerate cases,
thus becoming even more competitive with Avis and Fukuda's algorithm.
Previous ← → Next
Rainer E. Burkard, Bernd Fruhwirth, and Günter Rote:
Annals of Operations Research 57 (1995),
29–44, (Zbl 831.90053). doi:10.1007/BF02099689
Abstract
This study concerns the design of an operating system for vehicles in
an automated warehouse. The layout of the warehouse, and the number
and properties of the vehicles are given. The objective is to maximize
the throughput. Using a partial enumeration technique we simulate several
alternatives for the control and interplay of the vehicles within a reasonable
time horizon. A subproblem is solved by network flow techniques. The algorithm
is implemented as part of an automatic control system, and it has lead to a
satisfactory performance.
Previous ← → Next
David Eppstein, Mark Overmars, Günter Rote, and Gerhard
Woeginger:
Finding minimum area kgons.
Discrete and Computational Geometry 7 (1992), 45–58,
(Zbl 746.68038, MR #92k:52026). doi:10.1007/BF02187823
Previous ← → Next
Günter Rote:
Computing 48 (1992), 337–361, (Zbl 787.65006).
doi:10.1007/BF02238642
Abstract
The Sandwich algorithm approximates a convex function of one variable
over
an interval by evaluating the function and its derivative at a sequence
of
points. The connection of the obtained points is a piecewise linear
upper
approximation, and the tangents yield a piecewise linear lower
approximation.
Similarly, a planar convex figure can be approximated by convex
polygons.
Different versions of the Sandwich algorithm use different rules for
selecting the next evaluation point. We consider four natural rules
(interval bisection, slope bisection, maximum error rule, and chord
rule)
and show that the global approximation error with n evaluation points
decreases by the order of O(1/n^{2}), which is optimal.
By special examples we show that the actual performance of the four
rules can be very different from each other, and we report
computational
experiments which compare the performance of the rules for particular
functions.
Note: A different proof of the Sandwich algorithm for the two
bisection rules is given in the paper Sandwich
approximation of univariate convex functions with an application
to separable convex programming by
Rainer E. Burkard, Horst W.
Hamacher, and Günter Rote.
In: Proceedings of the Second Canadian Conference on Computational
Geometry, Ottawa, August 6–10, 1990. Editor: J. Urrutia;
pp. 287–290.
Abstract
This short paper applies the methods of the first paper to
approximating plane figures.
Previous ← → Next
Joseph S. B. Mitchell, Günter Rote, and Gerhard
Woeginger:
 Algorithmica 8 (1992), 431–459, (Zbl
788.68144).
doi:10.1007/BF01758855
 Extended Abstract in: Proceedings of the Sixth Annual
Symposium on
Computational Geometry,
Berkeley, California, June 6–8, 1990. Association for Computing
Machinery,
1990; pp. 63–72.
doi:10.1145/98524.98537
(This is a preliminary and shortened version of 1.)
Abstract
Given a set of nonintersecting polygonal obstacles in the plane, the
link
distance between two points s and t is the minimum
number
of edges
required
to form a polygonal path connecting s
to t that avoids all obstacles. We
present an algorithm that computes the link distance (and a
corresponding
minimumlink path) between two points in time O(Eα(n)log^{2}n)
and space
O(E),
where n is the total number of edges of the obstacles, E
is the size of
the visibility graph, and α(n) denotes the extremely slowly
growing
inverse of
Ackermann's function. We show how to extend our method to allow
computation
of a tree (rooted at s) of minimumlink paths from s to all
obstacle
vertices. This leads to a method of solving the query version of our
problem
(for query points t).
Previous ← → Next
Rudolf Fleischer, Kurt Mehlhorn, Günter Rote, Emo Welzl, and Chee
Yap:
In: Proceedings of the Sixth Annual Symposium on Computational
Geometry, Berkeley, California, June 6–8, 1990. Association
for Computing Machinery, 1990; pp. 216–224. doi:10.1145/98524.98572
Algorithmica 8 (1992), 365–389, (Zbl 760.68083). doi:10.1007/BF01758852
(This is a more detailed version of 1.)
Abstract
For compact Euclidean bodies P, Q, we define
λ(P,Q)
to be the smallest ratio r/s such
that P is contains a translated copy of Q scaled
by a positive factor s and is contained in a translated copy
of Q scaled by a positive factor r. This function
λ gives us a new distance function between bodies
which, unlike previously studied measures, is invariant under affine
transformations. If homothetic bodies are identified, the logarithm of this
function is a metric. (Two bodies are homothetic if one can be obtained from
the other by scaling and translation.)
For integer k≥3, we study λ(k),
the minimum value such that for each convex polygon P
there exists a convex kgon Q with
λ(P,Q)≤λ(k).
Among other
results, we prove that 2.118...≤λ(3)≤2.25 and
λ(k) = 1 + Θ(1/k^{2}).
We give an
O(n^{2}
log^{2}n)time algorithm which, for any input convex
ngon P, finds a triangle T that minimizes
λ(T,P) among triangles. However, in linear time we
can find a triangle T with
λ(T,P)≤2.25.
Our study is motivated by the attempt to reduce the complexity of the
polygon containment problem, and also the motionplanning problem. In each case
we describe algorithms which run faster when certain implicit slackness
parameters of the input are bounded away from 1. These algorithms illustrate
a new algorithmic paradigm in computational geometry for coping with
complexity.
Previous ← → Next
1. Günter Rote and Andreas Vogel:
ZOR — Methods and Models of Operations Research
38 (1993), 281–307, (Zbl 785.90069).
doi:10.1007/BF01416610
2. Günter Rote and Andreas Vogel:
Bericht 731990, Technische Universität Graz, 28 pages; (slightly extended version of 1.)
3. Günter Rote:
(Short and preliminary version of 1.)
ZAMM · Zeitschrift für angewandte Mathematik und Mechanik
69 (1989),
T29–T31.
doi:10.1002/zamm.19890690402
Abstract
With the timedivision multiple access (TDMA) technique in satellite
communication the problem arises to decompose a given n×n traffic matrix into
a weighted sum of a small number of permutation matrices such that the sum
of the weights becomes minimal. There are polynomial algorithms when the
number of permutation matrices in a decomposition is allowed to be as large
as n^{2}. When the number of matrices is restricted to n, the problem is
NPhard. In this paper we propose a heuristic based on a scaling technique
which for each number of allowed matrices in the range from n to n^{2} allows
to give a performance guarantee with respect to the total weight of the
solution. As a subroutine we use new heuristics methods for decomposing a
matrix of small integers into as few matrices as possible without exceeding
the lower bound on the total weight. Computational results indicate that the
method might also be practical.
Previous ← → Next
Christian Icking, Günter Rote, Emo Welzl, and Chee Yap:
Algorithmica 10 (1993), 182–200. (Zbl 781.68118). doi:10.1007/BF01891839
Abstract
We study the problem of shortest paths for a line segment in the plane. As
a measure of the distance traversed by a path, we take the average curve
length of the orbits of prescribed points on the line segment. This problem
is nontrivial even in free space (i. e., in the absence of obstacles).
We characterize all shortest paths of the line segment moving in free space
when we measure the average orbit length of the two endpoints.
This problem of optimal motion has been solved by Gurevich and also by
Dubovitskij, who calls it Ulam's problem. Unlike previous solutions, our basic
tool is Cauchy's surfacearea formula. This new approach is relatively
elementary, and yields new insights.
Previous ← → Next
1. Gerhard Woeginger, Günter Rote, Binhai Zhu, and Zhengyan
Wang :
Information Processing Letters 38 (1991), 149151,
(Zbl 737.68084,
MR #92i:68183).
2. Günter Rote and Gerhard Woeginger:
Information Processing Letters 41 (1992), 191194, (Zbl 751.68077,
MR #93c:68108).
3. Joseph S. B. Mitchell, Günter Rote, Gopalakrishnan
Sundaram, and
Gerhard Woeginger:
Information Processing Letters 56 (1995), 4549, (Zbl 875.68899).
Abstract
Given n points in the plane and an integer k,
between 4 and n, we want to compute the overall number of
convex kgons whose corners belong to the given point set.
The first paper
gives an O(n^{k2}) algorithm
for this problem, improving over the trivial O(n^{k})
algorithm.
In the second paper, a refinement of the technique improves
the complexity to O(n^{floor(k/2)}).
This time bound has been subsequently improved
to O(k n^{3}) in the third paper.
Previous ← → Next
Günter Rote:
Information Processing Letters
38 (1991), 123–127,
(Zbl 736.68078,
MR #92d:68114). doi:10.1016/00200190(91)902338
Abstract
Given two sets of points on a line, we want to translate one of them so
that their Hausdorff distance is minimized. (The Hausdorff distance
between two
sets the maximum of the distances from a point in any of the two sets
to
the nearest point in the other set.) We present an optimal O(n log n)
algorithm for this problem.
Previous ← → Next
Paul Hilfinger, Eugene L. Lawler, and Günter Rote:
In: “Applied Geometry and Discrete Mathematics.” The Victor Klee
Festschrift. Editors: Peter Gritzmann and Bernd Sturmfels. DIMACS series in
discrete mathematics and theoretical computer science, American Mathematical
Society and Association for Computing Machinery, 1991; pp. 335340,
(Zbl 733.68061, MR #92i:68122).
Abstract
The following is a graphtheoretic formulation of a problem arising in the
compilation of blockstructured programming languages. Let T=(V,E) be
a rooted tree and let A and C be sets of additional arcs with the
following properties:
 (1)
 If (v,w) belongs to A, then w is a proper ancestor
of v.
 (2)
 If (v,w) belongs to C, then w is a child of an
ancestor of v (allowing v to be an ancestor of itself).
It is desired to find a rooted tree T'=(V,E') in which the depth of each
node is as small as possible, subject to the conditions (1), (2), and
 (3)
 w is an ancestor of v in T' only if w is an ancestor
of v in T.
A simple, almost lineartime, algorithm for constructing an optimal
tree T' is described. The constructed tree T' has the property that
node w is an ancestor of node v in T' only if this is true in every tree
satisfying conditions (1)–(3). Hence the depth ever each node is
simultaneously minimized.
The running time of the algorithm is O(m α(m,n)), where n is
the number of nodes in T, m≥n is the total number of arcs
in C and T, and α(m,n) is an
extremely slowly growing function related to the functional inverse of
Ackermann's function.
Previous ← → Next
Rainer E. Burkard, Horst W. Hamacher, and Günter Rote:
Naval Research Logistics 38 (1991), 911–924, (Zbl 755.90066, MR
#92h:90098), doi:10.1002/nav.3800380609
Abstract
We develop an algorithm for computing upper and lower aproximations of
an explicitly or implicitly given convex function defined on an
interval
of length T. The algorithm requires no differentiability assumptions;
the
error decreases quadratically with the number of iterations. To reach
an
absolute accuracy of ε, the number of iterations is bounded by
sqrt(9DT/(8ε)),
where D is the total slope increase of the function. As an application,
we discuss separable convex programs.
Note: A more general treatment of the Sandwich algorithm (with
different
proofs) is given in the paper
The
convergence rate of the Sandwich algorithm for approximating convex
functions
by Günter Rote.
Previous ← → Next
Vasilis Capoyleas, Günter Rote, and Gerhard Woeginger:

Extended abstract in: Proceedings of the Second Canadian Conference
on Computational Geometry, Ottawa, August 610, 1990. Editor: J. Urrutia;
pp. 2831.

Journal of Algorithms 12 (1991), 341356, (Zbl 734.68092, MR #92d:52033).
Abstract
A kclustering of a given set of points in the plane is a partition
of the points into k subsets ("clusters"). For any fixed k,
we can find a kclustering which minimizes any monotone function
of the diameters or the radii of the clusters in polynomial time. The algorithm
is based on the fact that any two clusters in an optimal solution can be
separated by a line.
(For 3clustering, an improved algorithm was later given in the paper
Threeclustering
of points in the plane.)
Previous ← → Next
Rainer E. Burkard, Günter Rote, EnYu Yao, and ZhongLiang Yu:
Computing 45 (1990), 51–68, (Zbl. 722.68098,
MR #91g:68157).
doi:10.1007/BF02250584
Abstract
For a polygonal path in the plane or in space, we want to find an
inscribed path of shortest circumference. In the open case the path
can have different start and end point, whereas in the closed case
these two points must coincide. We show that finding such shortest paths can
be reduced to finding a shortest path in a planar channel. This
problem can be solved in linear time in the open as well in the closed
case. Finally, we deal with constrained problems where the wanted path has to
fulfill additional properties; in particular, if it has to pass straight
through a further point, we show that the length of such a constrained
polygonal path is a strictly convex function of some parameter angle, and
we derive an algorithm for determining such constrained polygonal paths
efficiently.
Previous ← → Next
Günter Rote:
In: Computational Graph Theory. Editors: G. Tinhofer, E. Mayr,
H. Noltemeier, and M. Syslo, in cooperation with R. Albrecht.
SpringerVerlag, 1990.
Computing Supplementum 7 (1990), pp. 155–189, (Zbl 699.68088,
MR #91m:05122).
→BibTeX
Abstract
A large variety of problems in computer science can be viewed from a common
viewpoint as instances of algebraic path problems. Among them are of
course path problems in graphs such as the shortest path problem or problems
of finding optimal paths with respect to more generally defined objective
functions; but also graph problems whose formulations do not directly involve
the concept of a path, such as finding all bridges and articulation points
of a graph; Moreover, there are even problems which seemingly have nothing to
do with graphs, such as the solution of systems of linear equations, partial
differentiation, or the determination of the regular expression describing the
language accepted by a finite automaton. We describe the relation among
these problems and their common algebraic foundation. We survey algorithms
for solving them: vertex elimination algorithms such as GaußJordan
elimination; and iterative algorithms such as the classical Jacobi and
GaußSeidel iteration.
Previous ← → Next
Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, and Emo Welzl:
 (Preliminary extended abstract)
In:
Proceedings of the 7th Annual Symposium on Theoretical
Aspects of Computer Science (STACS'90), Rouen, February 1990.
Lecture Notes in Computer Science 415, SpringerVerlag, 1990,
pp. 240–249, (Zbl 729.68087, MR #91e:68148). doi:10.1007/3540522824_47

(Improved and extended version)
Computational Geometry, Theory and
Applications 10 (1998), pp. 77–87. doi:10.1016/S09257721(96)000193
Abstract
We consider the problem of approximating a convex figure in the plane by
a pair (r,R) of homothetic (i. e., similar and parallel) rectangles with
r contained in C and R containing C. We show the existence of such pairs
where the sides of the outer rectangle have length at most double the length
of the inner rectangle, thereby solving a problem posed by Pólya
and Szegö. If the n vertices of a convex polygon C are given as a
sorted array, such an approximating pair of rectangles can be computed
in time O(log^{2}n).
Previous ← → Next
Richard Pollack, Micha Sharir, and Günter Rote:
Discrete and Computational Geometry 4 (1989), 611–626,
(Zbl 689.68067, MR #90g:68141).
doi:10.1007/BF02187751
Abstract
The geodesic center of a simple polygon is a point inside the polygon which
minimizes the maximum internal distance to any point in the polygon. We
present an algorithm which calculates the geodesic center of a simple
polygon
with n vertices in time O(n log n).
Previous ← → Next
Rainer E. Burkard, Günter Rote, Günther Ruhe, and Norbert
Sieber:
Wissenschaftliche Zeitschrift der Technischen Hochschule Leipzig 33 (1989),
333–341, (Zbl 706.90024).
Abstract
Finding optimal flows in networks is one of the most common tasks in
Operations Research. With few exceptions, this problem has so far been treated
with a single objective function only. Many practical problems involve,
however, several competing objectives.
In this paper we design and analyze algorithms for bicriteria minimumcost
flows. We present some complexity estimates, which lay the basis for
the development of algorithms. We present some general results about the
approximation of convex functions. We describe an exact algorithm and different
realizations of the Sandwich approximation scheme, and we give results of
numerical test calculations.
Previous ← → Next
Bernd Fruhwirth, Rainer E. Burkard, and Günter Rote:
European Journal of Operational Research
42 (1989), 326–338,
(MR #91e:90107).
Abstract
An approximation of an explicitly or implicitly given convex curve in the
plane is given by two piecewise linear “outer” and “inner” curves. To
compute these, three rules for choosing the supporting points are proposed and
it is shown for two of them that the projective distance between inner and
outer approximation decreases quadratically with the number of supporting
points. These two rules are variations of the Sandwich algorithm. The third
rule takes a more local approach. It is a compromise between the adaptive
global strategy of the Sandwich algorithm and the usual local lefttoright
parametric approach for computing the efficient point curve.
This method is applied to approximate the efficient point curve of the
bicriteria minimum cost flow problem, which is a piecewise linear convex curve
that may have an exponential number of breakpoints in the worst case.
It turns out that the lefttoright rule is better from a computational
viewpoint, since is tries to avoid large changes in the parameters when
solving successive minimum cost flow problems.
Previous ← → Next
Günter Rote:
Ph. D. thesis, Technische Universität Graz, May 1988, 55 pages.
(Supervisor: Prof. Dr. R. E.
Burkard).
This thesis
contains the
paper The Nline
traveling salesman problem
and an extension of the paper
Testing
the necklace condition for shortest tours and optimal factors in the
plane, written jointly with Herbert Edelsbrunner and Emo Welzl.
The improvement of the latter part has not been published elsewhere.
Abstract
In the Euclidean traveling salesman problem, a set of points in the
plane is given,
and we look for a shortest closed curve through these lines (a "tour").
We treat two special cases of this problem which are solvable in
polynomial time.
The first solvable case is the
Nline traveling salesman problem, where the points lie on a
small number (N) of
parallel lines.
Such problems arise for example in the fabrication of printed circuit
boards,
where the distance traveled by a laser which drills holes in certain
places of
the board should be minimized.
By a dynamic programming algorithm, we can solve
the Nline traveling salesman problem for n points in
time n^{N},
for fixed N, i. e.,
in polynomial time. This extends a result of Cutler (1980) for
3 lines.
The parallelity condition can be relaxed to point sets which
lie on N "almost parallel" line segments.
The other solvable case concerns the necklace
condition: A tour is a necklace tour if we can draw
disks with the given points as centers such that two
disks intersect if and only if the corresponding points are adjacent on
the
tour.
If a necklace tour exists, it is the unique optimal tour.
We give an algorithm which tests in
O(n^{3/2})
time
whether a given tour is a necklace tour,
improving an algorithm of Edelsbrunner,
Rote, and Welzl
(1988) which takes O(n^{2})
time. It is based on solving a system of
linear inequalities by the generalized nested dissection
procedure of
Lipton,
Rose, and Tarjan (1979). We describe how this method can be implemented
with only linear storage.
We give another algorithm which tests in O(n^{2} log n)
time and linear
space, whether a necklace tour exists
for a given point set, by
transforming
the problem to a fractional 2factor problem on a sparse bipartite
graph.
Both algorithms also compute radii for the disks realizing the necklace
tour.
Previous ← → Next
Günter Rote:
Networks 22 (1992), 91–108, (Zbl 783.90118,
MR #92k:90045). doi:10.1002/net.3230220106
Abstract
We consider the special case of the Euclidean Traveling Salesman
Problem where
the given points lie on a
small number (N) of
parallel lines.
Such problems arise for example in the fabrication of printed circuit
boards,
where the distance traveled by a laser which drills holes in certain
places of
the board should be minimized.
By a dynamic programming algorithm, we can solve
the Nline traveling salesman problem for n points in
time n^{N},
for fixed N, i. e.,
in polynomial time. This extends a result of Cutler (1980) for
3 lines.
The parallelity condition can be relaxed to point sets which
lie on N "almost parallel" line segments. We give a
characterization of the allowed segment configurations by a set of
forbidden subconfigurations.
See Erratum
Previous ← → Next
Herbert Edelsbrunner, Günter Rote, and Emo Welzl:
1. Theoretical Computer Science 66 (1989), 157180, (MR #90i:90042).
2. In: "Automata, Languages, and Programming". Proceedings of the
14th International Colloquium on Automata, Languages, and Programming (ICALP),
Karlsruhe, Juli 1987. Editor: T. Ottmann. Lecture Notes in Computer Science
266, SpringerVerlag, 1987, pp. 364375, (Zbl 636.68042, MR #88k:90065).
(This is a shortened and slightly modified version.)
Abstract
A traveling salesman tour is a necklace tour if we can draw
disks with the given points as centers such that two
disks intersect if and only if the corresponding points are adjacent on the
tour.
If a necklace tour exists, it is the unique optimal tour.
We give an algorithm which tests in
O(n^{2}) time
whether a given tour is a necklace tour.
We give another algorithm which tests
in O(n^{2} log n) time and linear
space whether a necklace tour exists
for a given point set, by
transforming
the problem to a fractional 2factor problem on a sparse bipartite graph.
Both algorithms can be generalized to mfactors of
point sets in the plane.
Note. In his dissertation,
Two
solvable cases of the traveling salesman problem, Günter Rote has
improved the
time complexity of the algorithm for testing a given tour to
O(n^{3/2}). The new algorithm is based on solving a system of
linear inequalities by the generalized nested dissection procedure of
Lipton, Rose, and Tarjan (1979).
Previous ← → Next
Günter Rote:
In: "Parallel Algorithms & Architectures". Proceedings of the International
Workshop on Parallel Algorithms and Architectures, Centre National de
Rencontres Mathématiques, Luminy, France, April 14–18, 1986.
Editors: M. Cosnard, Y. Robert, P. Quinton, and M. Tchuente.
NorthHolland, 1986, pp. 99–108, (Zbl 639.68031).
Abstract
We consider the problem of scheduling n jobs with different
processing times on one machine subject to a common release date and
different duedates, in order to maximize the number of jobs that are
finished on time. The wellknown MooreHodgson algorithm from 1968 is the most
efficient sequential algorithm and runs in O(n log n)
time. We present a parallelization of this algorithm with takes
O(log^{2}n) time on n^{2} processors in the single
instruction stream, multiple data stream (SIMD) shared memory model without
write conflicts but with read conflicts allowed.
Our approach is based on the
binary tree method of Dekel and Sahni (Binary trees and parallel scheduling
algorithms, IEEE Transactions on Computers C32, 1983). It requires a
thorough analysis of the behavior of the sequential algorithm. We show that a
parallel algorithm of Dekel and Sahni for the same scheduling problem relies
on an erroneous assumption.
Previous ← → Next
Günter Rote:
In: "VLSI Algorithms and Architectures  Aegean Workshop on Computing.
Loutraki, Greece, July 1986". Proceedings of AWOC'86. Editors: F. Makedon,
K. Mehlhorn, T. Papatheodorou, P. Spirakis. Lecture Notes in
Computer Science 227, SpringerVerlag, 1986, pp. 7083.
Abstract
We define a simple transformation between systolic algorithms with hexagonal
and with rectangular processor arrays. Using this transformation we can
establish a direct correspondence between two independently developed systolic
arrays for solving the algebraic
path problem (matrix inversion, shortest paths in a network, transitive
closure of a relation).
The two systolic arrays are a
hexagonal one due to the author
and a rectangular one due to Yves Robert and Denis Trystram,
"An orthogonal systolic array for the algebraic path problem",
Computing 39, 187199.
Then we derive a new hexagonal array for solving a certain type of dynamic
programming recursion that arises for example in contextfree language
recognition, in the construction of optimal binary search trees , or in the
computation of an optimal sequence of multiplication for the evaluation of a
product of matrices.
A rectangular array for this problem is due to L. J. Guibas, H. T. Kung, and
C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms",
Proc. CalTech Conference on VLSI. January 1979, pp.756763.
In general, the type of transformation used here allows arbitrary systolic
arrays to be transformed into unidirectional ones, which are preferable from
the points of view of fault tolerance, twolevel pipelining, and algorithm
partitioning.
Previous ← → Next
Günter Rote and Franz Rendl:
Operations Research Letters 5 (1986),
111118, (Zbl 626.90069, MR #87k:90103). doi:10.1016/01676377(86)900830
Abstract
We present a lineartime solution to the problem of assigning each of
n given entry terminals positioned at the upper row of a channel to
one of m given exit terminals positioned at the lower row, so as to
minimize the density of the resulting channel routing problem.
Previous ← → Next
Günter Rote:
Rechenzentrum Graz, Bericht 104, 1985, 58 pages.
Abstract
The solution set of a system of equations where the + operation is replaced
by max, has in general a unique maximum element but many minimal elements.
The characterization of these minimal elements leads to a generalized set
covering problem. The difference to the classical set covering problem is
that, instead of taking a given set or not, one can select a set from a
given chain of nested sets. We give several algorithms for enumerating
the minimal solutions of the generalized set covering problem, all of
them exponential in the worst case. When specialized to the set covering
problem, the problem of enumerating the minimal solutions is also known as
hypergraph dualization.
For the case of maxmin equations, we derive upper bounds on the number of
solutions by using network flow techniques. We also disprove a
conjecture of
Czogala,
Drewniak and Pedrycz (1982) that an n×n system of maxmin
equations has less than 2^{n} minimal solutions.
Previous ←
Günter Rote:

A systolic array algorithm for the algebraic path problem (shortest paths;
matrix inversion).
Computing 34 (1985), 191–219,
(Zentralblatt für Mathematik 546.68047
(562.68056); Mathematical Reviews #86k:68046). doi:10.1007/BF02253318
This is a shortened and extended version of the report 3 below.

A systolic array algorithm for the algebraic path problem.
Diplomarbeit (Master's thesis), February 1985. Supervisor: Prof.
Dr. R. E. Burkard.
This is a corrected version of 3.

A systolic array for the algebraic path problem (which includes the
inverse of a matrix and shortest distances in a graph).
Rechenzentrum Graz, Bericht 101, 1984, 69 pages.
Abstract
It is shown how the GaußJordan elimination algorithm for
the Algebraic Path Problem can be implemented on a hexagonal systolic array
of a quadratic number of simple processors in linear time.
Special instances of this general algorithm include parallelizations of the
WarshallFloyd algorithm, which computes shortest distances in a graph or the
transitive closure of a relation, and of the
GaußJordan elimination algorithm for computing the inverse of a real
matrix.