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 up-to-date information, including the on-line original versions by the publishers, and a link to a BibTeX entry which you can copy directly.


→ Next
Previous ← → Next

Jean-Philippe Labbé, Günter Rote, and Günter M. Ziegler:

Area difference bounds for dissections of a square into an odd number of triangles

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 semi-algebraic geometry to a polynomial area difference measure and thus get a lower bound for the area differences that decreases doubly-exponentially 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.

  pdf file (gzipped)   Video of a talk from the Discrete Geometry Fest in Budapest, May 2017, slides of the talk

Previous ← → Next

Boris Klemz and Günter Rote:

Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

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, maximum-cardinality 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 maximum-cardinality induced matching or a minimum chain cover had a running time of O(n2).


Previous ← → Next

Boris Klemz and Günter Rote:

Ordered level planarity, geodesic planarity and bi-monotonicity

  1. 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.
  2. 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 Kwan-Liu Ma, Lecture Notes in Computer Science, Springer-Verlag, 2017, 14 pages.
  3. 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 y-monotone 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 NP-completeness 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 T-Level 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.

  pdf file (gzipped)

Previous ← → Next

Pavle V. M. Blagojević, Günter Rote, Johanna K. Steinmeyer, and Günter M. Ziegler:

Convex equipartitions of colored point sets

Manuscript, May 2017, 7 pages, arXiv:1705.03953 [math.CO].

Abstract

We show that any d-colored 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 d-space 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.

  pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber:

Packing short plane spanning trees in complete geometric graphs

In: 27th International Symposium on Algorithms and Computation (ISAAC 2016), Editor: Seok-Hee Hong. Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum 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.

  pdf file (gzipped)

Previous ← → Next

Felix Herter and Günter Rote:

Loopless Gray code enumeration and the Tower of Bucharest

  1. 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 Dagstuhl-Leibniz-Zentrum für Informatik, 2016, Vol. 49, pp. 19:1–19:18. doi:10.4230/LIPIcs.FUN.2016.19.
  2. Preprint arXiv:1604.06707, April 2016. [cs.DM].
  3. Revised and extended version, to appear in Theoretical Computer Science, special issue for FUN'2016.

Abstract

We give new algorithms for generating all n-tuples 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.

  pdf file (gzipped)

Previous ← → Next

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno:

Approximation and hardness for token swapping

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 Dagstuhl-Leibniz-Zentrum 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 {T1,…,Tn} 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 Ti 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 2o(n) algorithms under the Exponential Time Hypothesis (ETH). This is matched with a simple 2O(n log n) algorithm based on exploring the state space. We give a general 4-approximation algorithm and show APX-hardness. Thus, there is a constant δ>1 such that every polynomial-time 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.

  pdf file (gzipped)

Previous ← → Next

Heuna Kim and Günter Rote:

1. Congruence testing of point sets in 4-space

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 Dagstuhl-Leibniz-Zentrum für Informatik, 2016. pp. 48:1–48:15. doi:10.4230/LIPIcs.SOCG.2016.48
  pdf file (gzipped)

2. Congruence testing of point sets in 4 dimensions

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 n-point sets in 4-dimensional 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 d-space so far are are a deterministic algorithm by Brass and Knauer (2000) and a randomized Monte Carlo algorithm by Akutsu (1998). In 4-space, they take time O(n2log n) and O(n3/2log n), respectively.

Our algorithm exploits the geometric structure and the properties of 4-dimensional space, such as angles between planes, packing numbers, Hopf fibrations, Plücker coordinates, the classification of Coxeter groups, and rotations in 4-space.

  pdf file (gzipped)
  Video of a talk from the conference The Mathematics of Jiří Matoušek in Prague, July 2017 (including slides)
slides of a lecture at the CALDAM 2017 Pre-Conference School on Algorithms and Combinatorics in Goa, India, February 2017

Previous ← → Next

Günter Rote:

Congruence testing of point sets in three and four dimensions—Results and techniques

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, Springer-Verlag, 2016, pp. 50–59. doi:10.1007/978-3-319-32859-1_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 three-dimensional version of the problem, and indicate how they lead for the first time to an algorithm for four dimensions with near-linear running time (joint work with Heuna Kim). On the way, we will encounter some beautiful and symmetric mathematical structures, like the regular polytopes, and Hopf-fibrations of the three-dimensional sphere in four dimensions.

  pdf file (gzipped)

Previous ← → Next

Dror Atariah, Günter Rote, and Mathijs Wintraecken:

Optimal triangulation of saddle surfaces

To appear in Beiträge zur Algebra und Geometrie—Contributions to Algebra and Geometry (2017), 14 pages, doi:10.1007/s13366-017-0351-9, arXiv:1511.01361 [math.MG].

Abstract

We consider the piecewise linear approximation of saddle functions of the form f(x,y) = ax2-by2 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.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, and Ignaz Rutter:

Windrose planarity: embedding graphs with direction-constrained edges

In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA16), San Francisco, January 2016, pp. 985–996. doi:10.1137/1.9781611974331.ch70, arXiv:1510.02659 [cs.CG].

Abstract

Windrose planarity asks for planar drawings of a graph, where every edge is monotone both in in the x and the y-direction. Moreover, for each edge uv it is specified in which quadrant (NE, NW, SW, or SE) v lies relative to u. While the well-known 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 windrose-planar drawing is NP-hard in the general case. We give a polynomial-time 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 windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an O(nO(n) grid. This contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

  pdf file (gzipped)

Previous ← → Next

Péter Hajnal, Alexander Igamberdiev, Günter Rote, and André Schulz:

Saturated simple and 2-simple topological graphs with few edges

In: 41st International Workshop on Graph-Theoretic Concepts in Computer Science—WG 2015, Garching, Germany, June 2015, Revised Papers. Editor: Ernst Mayr, Lecture Notes in Computer Science, 9224, Springer-Verlag, 2016, pp. 391–405. doi:10.1007/978-3-662-53174-7_28, arXiv:1503.01386 [cs.CG].

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 k-simple topological graph, every pair of edges has at most k common points of this kind. We construct saturated simple and 2-simple graphs with few edges. These are k-simple graphs in which no further edge can be added. We improve the previous bounds of Kyncl, Pach, Radoicic, and Tóth (2013) and show that there are saturated simple graphs on n vertices with 7n edges and saturated 2-simple graphs on n vertices with 14.5n edges. As a consequence, 14.5n edges is also a new upper bound for k-simple graphs (considering all values of k). We also construct saturated simple and 2-simple graphs that have some vertices with low degree.

  pdf file (gzipped)
Last update: December 8, 2016.
Previous ← → Next

Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie:

Shortest path to a segment and quickest visibility queries

  1. 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
  2. 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–Leibniz-Zentrum für Informatik, 2015, pp. 658–673. doi:10.4230/LIPIcs.SOCG.2015.658
  3. Christian Knauer, Günter Rote, and Lena Schlipf: Shortest inspection-path 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 (gzipped)

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 well-known shortest-path-to-a-point 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 shortest-path-to-a-point 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.

  pdf file (gzipped)

Previous ← → Next

Andrei Asinowski and Günter Rote:

Point sets with many non-crossing matchings

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 non-crossing straight-line perfect matchings that a set of n points in the plane can have is known to be O(10.0438n) and Ω*(3n), 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 Θ(3n/nΘ(1)) such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free 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) non-crossing perfect matchings with λ≈3.0532. Next we analyze further generalizations of double zigzag chains: double r-chains. The best choice of parameters leads to a construction that has Θ*n) non-crossing perfect matchings with μ≈3.0930. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors.

Moral: Don't count your boobies until they are hatched matched.

  pdf file (gzipped)

Previous ← → Next

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Günter Rote, and Gábor Wiener:

Search for the end of a path in the d-dimensional grid and in other graphs

Ars Mathematica Contemporanea 12 (no. 2) (2017), 301–314.

Abstract

We consider the worst-case query complexity of some variants of certain PPAD-complete 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 vertex-disjoint 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.

  pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Michael Hoffmann, Marc van Kreveld, and Günter Rote:

Graph drawings with relative edge length specifications

In: Proceedings of the 26th Canadian Conference on Computational Geometry, (CCCG'2014), Halifax, August 2014, 7 pages.

Abstract

We study plane straight-line 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.

  pdf file

Previous ← → Next

Michael Hoffmann, Marc van Kreveld, Vincent Kusters, and Günter Rote:

Quality ratios of measures for graph drawing styles

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 straight-line drawings with fixed and free embeddings, planar circular arc drawings, and non-planar straight-line drawings, and consider the quality measures angular resolution, area requirement, edge length ratio, and feature resolution.

  pdf file

Previous ← → Next

Gill Barequet, Günter Rote, and Mira Shalah:

λ>4: An improved lower bound on the growth constant of polyominoes

  1. Extended abstract in: Abstracts of the 30th European Workshop on Computational Geometry (EuroCG'14), Ein-Gedi, Israel, March 2014, Editors: Paz Carmi, Matthew Katz, and Shakhar Smorodinsky, 4 pages.
  2. 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, Springer-Verlag, 2015, pp. 83–94. doi:10.1007/978-3-662-48350-3_8
  3. 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 edge-connected set of squares on the two-dimensional 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 long-standing problem: proving that the leading digit of λ is 4.

  pdf file (gzipped)   free PDF @ACM

Previous ← → Next

Günter Rote:

Lexicographic Fréchet matchings (extended abstract)

In: Abstracts of the 30th European Workshop on Computational Geometry (EuroCG'14), Ein-Gedi, 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.

Slides of the talk   pdf file

Previous ← → Next

Rafel Jaume and Günter Rote:

Recursively-regular subdivisions and applications

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 recursively-regular subdivisions. Informally, a recursively-regular 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 recursively-regular subdivisions are not necessarily connected by flips and that they are acyclic with respect to the in-front 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 graph-embedding problems.

  pdf file (gzipped)

Previous ← → Next

Dror Atariah, Sunayana Ghosh, and Günter Rote:

On the parameterization and the geometry of the configuration space of a single planar robot

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 differential-geometric properties of the various elements which constitute this boundary.

  pdf file (gzipped)

Previous ← → Next

Tristram Bogart, Christian Haase, Milena Hering, Benjamin Lorenz, Benjamin Nill, Andreas Paffenholz, Günter Rote, Francisco Santos, and Hal Schenck:

Finitely many smooth d-polytopes with n lattice points

Israel Journal of Mathematics 207 (2015), 301–329. doi:10.1007/s11856-015-1175-7, arXiv:1010.3887 [math.CO].

Abstract

We prove that for fixed d and n, there are only finitely many smooth d-dimensional 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 Q-factorial toric varieties into n-dimensional projective space Pn that are induced by a complete linear system. We also enumerate all smooth 3-polytopes with at most 12 lattice points.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Michael Hoffmann, Vincent Kusters, Günter Rote, Maria Saumell, and Rodrigo I. Silveira:

Convex hull alignment through translation

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 NP-hard 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.

  pdf file (gzipped)

Previous ← → Next

Dániel Gerbner, Viola Mészáros, Dömötör Pálvölgyi, Alexey Pokrovskiy, and Günter Rote:

Advantage in the discrete Voronoi game

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 bounded-degree 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 one-round game on the same graph.

  pdf file (gzipped)

Previous ← → Next

N. V. Abrosimov, E. Makai, jr., A. D. Mednykh, Yu. G. Nikonorov, and Günter Rote:

The infimum of the volumes of convex polytopes of any given facet areas is 0

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 n-polytope 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 well-defined 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.

  pdf file (gzipped)

Previous ← → Next

Andrei Asinowski, Tillmann Miltzow, and Günter Rote:

Quasi-parallel segments and characterization of unique bichromatic matchings

  1. Extended abstract. In: Abstracts of the 29th European Workshop on Computational Geometry (EuroCG'13), Braunschweig, March 2013, Editor: Sándor Fekete, pp. 225–228.
  2. 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 well-known that there is a perfect matching formed by non-crossing line segments. We characterize the bichromatic point sets which admit exactly one non-crossing 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.

  pdf file (gzipped)

Previous ← → Next

Günter Rote:

The degree of convexity

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(n9) closed-form expressions.

Note after publication (2017)

A region of a polygon in which the visible vertices are a fixed set of vertices is called a Sichtregion (viewing region) in the textbook of Rolf Klein, Algorithmische Geometrie (1996), Section 4.3.2. A polygon is partitioned into at most O(n3) viewing regions, according to Theorem 4.19 of the book. This is an improvement over the trivial bound O(n4) in my paper, and it holds also for the complexity of the partition Z, of which the viewing regions are a refinement: nZ=O(n3). This improves the overall bound of the paper from O(n9) to O(n7) closed-form expressions.

Moral: It can be worth while to read textbooks.

  pdf file (gzipped)

Previous ← → Next

Sarit Buzaglo, Rom Pinchasi, and Günter Rote:

Topological hypergraphs

In: Thirty Essays on Geometric Graph Theory. Editor: János Pach, Springer-Verlag, 2013, pp. 71–81. doi:10.1007/978-1-4614-0110-0_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 pseudo-circles.


Previous ← → Next

Ivan Izmestiev, Robert B. Kusner, Günter Rote, Boris Springborn, and John M. Sullivan:

There is no triangulation of the torus with vertex degrees 5,6,…,6,7 and related results: geometric proofs for combinatorial theorems

Geometriae Dedicata 166 (2013), 15–29. doi:10.1007/s10711-012-9782-5, arXiv:1207.3605 [math.CO].

Abstract

There is no 5,7-triangulation of the torus, that is, no triangulation with exactly two exceptional vertices, of degree 5 and 7. Similarly, there is no 3,5-quadrangulation. The vertices of a 2,4-hexangulation of the torus cannot be bicolored. Similar statements hold for 4,8-triangulations and 2,6-quadrangulations. 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 non-existence results for torus decompositions provide infinite families of graphs which cannot be embedded in the torus.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Darius Geiß, Rolf Klein, Rainer Penninger, and Günter Rote:

Optimally solving a transportation problem using Voronoi diagrams

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 Monge-Kantorovich transportation problem. Let S be a finite set of point sites in d dimensions. A bounded set C in d-dimensional space is to be distributed among the sites p in S such that (i) each p receives a subset Cp 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 dp(z). Under quite liberal technical assumptions on C and on the functions dp 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 dp 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.

  pdf file (gzipped)

Previous ← → Next

Dror Atariah and Günter Rote:

Configuration space visualization (video)

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.

  pdf file (gzipped)   free PDF @ACM

Previous ← → Next

Herbert Edelsbrunner, Brittany Terese Fasy, and Günter Rote:

Add isotropic Gaussian kernels at own risk: more and more resilient modes in higher dimensions

  1. 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.2261265free PDF @ACM
  2. Revised version, Discrete and Computational Geometry 49 (2013), 797–822. doi:10.1007/s00454-013-9517-x

Abstract

The fact that the sum of isotropic Gaussian kernels (Gaussian distributions) can have more modes (local maxima) than kernels is surprising. In 2003, Carreira-Perpiñá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.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

1. Jean Cardinal, Nathann Cohen, Sébastien Collette, Michael Hoffmann, Stefan Langerman, and Günter Rote:

Coloring dynamic point sets on a line

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:

Coloring hypergraphs induced by dynamic point sets and bottomless rectangles

to appear in: Algorithms and Data Structures Symposium-WADS 2013, August 2013, Editors: Frank Dehne, Jörg-Rüdiger Sack, and Roberto Solis-Oba, Lecture Notes in Computer Science, Springer-Verlag, 2013. arXiv:1302.2426 [cs.CG].

Abstract

We consider a coloring problem on dynamic, one-dimensional 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)=3k-2. This can be interpreted as coloring point sets in the plane with k colors such that any bottomless rectangle containing at least 3k-2 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 axis-aligned rectangles. Our result also complements recent contributions of Keszegh and Pálvölgyi on cover-decomposability of octants (2011,2012).

  slides of a talk in Prague (July 2012)   pdf file (gzipped)
subject Last update: July 19, 2013.
Previous ← → Next

Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz:

Memory-constrained algorithms for simple polygons

  1. Abstracts of the 28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, March 2012, pp. 49–52, Editors: Walter Didimo and Giuseppe Liotta.
  2. 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 constant-workspace algorithm has read-only 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 straight-line graph with n vertices in O(n2) time. We also consider preprocessing a simple n-gon, 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(n2) time, we are able to solve shortest path queries between any two points inside the polygon in O(n2/s) time.

  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Realizing planar graphs as convex polytopes

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, Springer-Verlag, 2011, pp. 238–241.doi:10.1007/978-3-642-25878-7_23

Abstract

This invited talk is a survey on methods to construct a three-dimensional convex polytope with a given combinatorial structure, that is, with the edges forming a given 3-connected planar graph, focusing on efforts to achieve small integer coordinates.

  slides of the talk   pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Katerina Čech Dobiášová, Bert Jüttler, and Günter Rote:

Triangulations with circular arcs

  1. 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, Springer-Verlag, 2012, pp. 296–307. doi:10.1007/978-3-642-25878-7_29
  2. 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 straight-line 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 graph-theoretic methods.

  slides of the talk   pdf file (gzipped)

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:

Convexifying polygons without losing visibilities

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 n-vertex 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 co-incident.

We also show how to modify the method so that vertices become very close but not co-incident.

The proof involves a new visibility property of polygons, namely that every simple polygon has a visibility-increasing edge where, as a point travels from one endpoint of the edge to the other, the visibility region of the point increases.

  pdf file (gzipped)

Previous ← → Next

Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Günter Rote, and Ryuhei Uehara:

Common developments of several different orthogonal boxes

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 non-orthogonal 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.

  pdf file (gzipped)

Previous ← → Next

1. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:

Monotone paths in planar convex subdivisions and polytopes

In: Discrete Geometry and Optimization, Editors: Károly Bezdek, Antoine Deza, and Yinyu Ye, Fields Institute Communications, Vol. 69, Springer-Verlag, 2013, pp. 79–104. doi:10.1007/978-3-319-00200-2_6

2. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:

Monotone paths in planar convex subdivisions

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, Springer-Verlag, 2012, pp. 240–251. doi:10.1007/978-3-642-32241-9_21

3. Günter Rote:

Long monotone paths in convex subdivisions

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 Ω(logdn) 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 3-space, 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 1-skeleton has at most O(log2n) edges. We also construct a polytope with n vertices, and triangular faces, (with unbounded degree however), such that every monotone path on its 1-skeleton has at most O(log n) edges.

  slides of a talk in Lausanne (2012)   pdf file (gzipped)

Previous ← → Next

Andrei Asinowski, Ronnie Barequet, Gill Barequet, and Günter Rote:

Proper n-cell polycubes in n−3 dimensions

  1. In: "Computing and Combinatorics". Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), Dallas, Texas, August 2011. Editors: Bin Fu and Ding-Zhu Du. Lecture Notes in Computer Science 6842, Springer-Verlag, 2011, pp. 181–191. doi:10.1007/978-3-642-22685-4_16
  2. Journal of Integer Sequences 15 (2012), Article 12.8.4, 16 pages.

Abstract

A d-dimensional 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 d-dimensional. We prove a formula for the number of polycubes of size n that are proper in n−3 dimensions.

  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Zitate zählen (Proper citation counting; in German)

Internat. Math. Nachrichten 213 (2010), 1–5.

Abstract

This is a critical discussion of a certain methodological-mathematical 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.

  pdf file (gzipped)

Previous ← → Next

Günter Rote and Uri Zwick:

Collapse

In: Proceedings of the 22nd Annual ACM-SIAM 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 rigid-body 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.

  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Partial least-squares point matching under translations

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.

  slides of the talk   pdf file (gzipped)

Previous ← → Next

Boris Aronov, Otfried Cheong, Xavier Goaoc, and Günter Rote:

Lines pinning lines

Discrete and Computational Geometry 45 (2011), 230–260. doi:10.1007/s00454-010-9288-6, arXiv:1002.3294 [math.MG].

Abstract

A line g is a transversal to a family F of convex polytopes in 3-dimensional 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.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke:

1. Integer point sets minimizing average pairwise l1 distance: What is the optimal shape of a town?

In: Proceedings of the 21st Annual Canadian Conference on Computational Geometry, Vancouver, August 17–19, 2009, pp. 145–148.

2. Integer point sets minimizing average pairwise L1 distance: What is the optimal shape of a town?

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 n-town, for a natural number n, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town 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 closed-form solution is known. We show that optimal n-towns can be computed in O(n7.5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.

  PostScript file (gzipped)   pdf file (gzipped)

Python programs

Numeric results


Previous ← → Next

1. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang:

Constant-work-space algorithms for geometric problems

Journal of Computational Geometry 2 (2011), 46–68.
pdf file (gzipped)

2. Tetsuo Asano and Günter Rote:

Constant-working-space algorithms for geometric problems

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

Constant-work-space algorithms may use only constantly many cells of storage in addition to their input, which is provided as a read-only array. We show how to construct several geometric structures efficiently in the constant-work-space model. Traditional algorithms process the input into a suitable data structure (like a doubly-connected edge list) that allows efficient traversal of the structure at hand. In the constant-work-space setting, however, we cannot afford to do this. Instead, we provide a zero-space 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 work-space. 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 work-space.

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 NL-complete, this constrained problem can be solved in quadratic time using only constant work-space.

pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Thomas Hackl, Davíd Orden, Pedro Ramos, Günter Rote, André Schulz, and Bettina Speckmann:

Flip graphs of bounded-degree triangulations

  1. 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
  2. Graphs and Combinatorics 29 (2013), 1577–1593. doi:10.1007/s00373-012-1229-0 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(n2). We also show that for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k<10, and flip graphs of triangulations can be disconnected for any k.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Günter Rote and André Schulz:

Resolving loads with positive interior stresses

In: Algorithms and Data Structures Symposium-WADS 2009, Banff, August 2009, Editors: Frank Dehne, Ian Munro, Jörg-Rüdiger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, 5664, Springer-Verlag, 2009, pp. 530–541. doi:10.1007/978-3-642-03367-4_46

Abstract

We consider the pair (pi, fi) as a force with two-dimensional direction vector fi applied at the point pi in the plane. For a given set of forces we ask for a non-crossing geometric graph on the points pi that has the following property: there exists a weight assignment to the edges of the graph, such that for every pi the sum of the weighted edges (seen as vectors) around pi yields −fi. As additional constraint we restrict ourselves to weights that are non-negative 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 pseudo-triangulation that fulfils the desired properties. Our results will be obtained by linear programming duality over the PPT-polytope. For the case where the forces appear only at convex hull vertices we show that the pseudo-triangulation that resolves the load can be computed as weighted Delaunay triangulation. Our observations lead to a new characterization of pointed pseudo-triangulations, 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 pseudo-triangulation of a simple polygon mentioned below.

Our studies are motivated by the construction of discrete Laplace-Beltrami operators.

  pdf file (gzipped)

Günter Rote and André Schulz:

A pointed Delaunay pseudo-triangulation of a simple polygon

In: Abstracts of the 21st European Workshop on Computational Geometry, Eindhoven, March 2005, pp. 77-80.
  pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber:

Plane graphs with party constraints

  1. In: Algorithms and Data Structures Symposium—WADS 2009, Banff, August 2009, Editors: Frank Dehne, Ian Munro, Jörg-Rüdiger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, 5664, Springer-Verlag, 2009, pp. 13–24. doi:10.1007/978-3-642-03367-4_2
  2. Graphs and Combinatorics 30 (2014), 47–69. doi:10.1007/s00373-012-1247-y

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 two-connected 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 NP-complete to decide whether it has a triangulation that satisfies all parity constraints on the vertices.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Panos Giannopoulos, Christian Knauer, and Günter Rote:

The parameterized complexity of some geometric problems in unbounded dimension

In: Proc. 4th Int. Workshop on Parameterized and Exact Computation-IWPEC 2009, Copenhagen, September 2009, Editors: Jianer Chen and Fedor V. Fomin, Lecture Notes in Computer Science, Vol. 5917, Springer-Verlag, 2009, pp. 198–209. doi:10.1007/978-3-642-11269-0_16, arXiv:0906.3469 [cs.CG].

Abstract

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension d:

  1. Given n points in d, compute their minimum enclosing cylinder.
  2. Given two n-point sets in d dimensions, decide whether they can be separated by two hyperplanes.
  3. Given a system of n linear inequalities with d variables, find a maximum-size 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)nc) 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:

Formulae and growth rates of high-dimensional polycubes

  1. 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
  2. Combinatorica 30 (2010), 257–275. doi:10.1007/s00493-010-2448-8

Abstract

A d-dimensional polycube is a facet-connected set of cubes in d dimensions. Fixed polycubes are considered distinct if they differ in their shape or orientation. A proper d-dimensional polycube spans all the d dimensions, that is, the convex hull of the centers of its cubes is d-dimensional. In this paper we prove rigorously some (previously conjectured) closed formulae for fixed (proper and improper) polycubes, and show that the growth-rate limit of the number of polycubes in d dimensions is 2edo(d). We conjecture that it is asymptotically equal to (2d−3)e + O(1/d).

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Günter Rote:

Two applications of point matching

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 minimum-weight 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 m-gon 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.

Note. Problem (a) has already been solved in the same way by V. Galperin and G. Galperin, Osveshchenije ploskosti prozhektorami (Illuminating a plane with spotlights). Kvant 11, no. 11 (1981), 28-30 (in Russian).

  pdf file (gzipped)

Previous ← → Next

Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner:

Fixed-parameter tractability and lower bounds for stabbing problems

  1. In: Abstracts of the 25th European Workshop on Computational Geometry (EuroCG'09), Brussels, March 2009, pp. 281–284.
  2. 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 axis-parallel unit squares with k axis-parallel lines is W[1]-hard with respect to k, and thus, not fixed-parameter 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 axis-parallel lines, we show that the problem is fixed-parameter 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.

  pdf file (gzipped)

Previous ← → Next

Dania El-Khechen, 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.
  BibTeX  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Curve intersection by the Subdivision-Supercomposition Method

Technical report ACS-TR-361503-01, 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 super-composition technique, which considers unions of adjacent parameter intervals that are not siblings in the subdivision tree. This approach addresses the common difficulty of non-termination 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günter Rote, Rodrigo I. Silveira, Bettina Speckmann, and Thomas Wolle:

1. Detecting hotspots in geographic networks

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, Springer-Verlag, 2009, pp. 217–231. (Best paper award). doi:10.1007/978-3-642-00318-9_11

2. Finding the most relevant fragments in networks

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 self-intersections at vertices, or a tree. We give polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.

  pdf file (gzipped)

Previous ← → Next

1. Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Bernhard Kornberger, Simon Plantinga, Günter Rote, Astrid Sturm, and Gert Vegter:

Seed polytopes for incremental approximation

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:

Recovering structure from r-sampled objects

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 3-space 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 r-sample 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.

  PostScript file, 5MB (gzipped, 2MB)   pdf file, 600KB (gzipped)

Previous ← → Next

Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension

1. Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter Rote:

In: Proceedings of the 19th Annual ACM-SIAM 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 axis-aligned cubes that cover a given n-point set in d dimensions in O(6ddn log (dn)) time. This shows that the problem is fixed-parameter 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 k-center problem in the Euclidean metric, for any k>1. In particular, we prove that deciding whether a given d-dimensional set of n points can be covered by the union of 2 balls of given radius, or by 4 axis-aligned cubes of given side length, is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1].

  not the final revision: pdf file (gzipped)   free PDF @ACM

Previous ← → Next

Rom Pinchasi and Günter Rote:

On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs

Israel Journal of Mathematics 172 (2009), 337–348. doi:10.1007/s11856-009-0076-z, arXiv:0707.0311 [math.MG].

Abstract

We show that the maximum cardinality of an anti-chain composed of intersections of a given set of n points in the plane with half-planes is close to n2. 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 pseudo-discs 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.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Oswin Aichholzer, Günter Rote, André Schulz, and Birgit Vogtenhuber:

Pointed drawings of planar graphs

  1. In: Proceedings of the 19th Canadian Conference on Computational Geometry, Ottawa, August 20–22, 2007, Editor: Prosenjit Bose, pp. 237–240.
  2. 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 straight-line embedding can not guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line embedding of the graph. Moreover, the graph can be embedded with circular arcs if the vertices can be placed arbitrarily.

  pdf file (gzipped)

Previous ← → Next

Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote:

1. New upper bounds on the quality of PCA bounding boxes in R2 and R3

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

2. New upper bounds on the quality of PCA bounding boxes in R2 and R3

In: Abstracts of the 23rd European Workshop on Computational Geometry, Graz, March 2007, pp. 122–125.

3. Bounds on the quality of the PCA bounding boxes

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 Rd. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes approximate the minimum-volume 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 R2 and R3.

  pdf file (gzipped)

Previous ← → Next

Ares Ribó Mor, Günter Rote, and André Schulz:

1. Embedding 3-polytopes on a small grid

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

2. Small grid embeddings of 3-polytopes

Discrete and Computational Geometry 45 (2011), 65–87. doi:10.1007/s00454-010-9301-0, arXiv:0908.0488 [cs.CG].

Abstract

We present a constructive method for embedding a 3-connected planar graph with n vertices as a 3-polytope with small integer coordinates. The embedding will need no coordinate greater than O(27.55n)=O(188n). 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.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote:

There are not too many magic configurations

  1. In: Proceedings of the 23rd Annual Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007. Association for Computing Machinery, 2007, pp. 142-149. doi:10.1145/1247069.1247098
  2. Discrete and Computational Geometry 39 (2008), pp. 3-16. doi:10.1007/s00454-007-9023-0

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.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF @ACM
  free PDF view@Springer
Previous ← → Next

Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and Carola Wenk:

How difficult is it to walk the dog?

In: Abstracts of the 23rd European Workshop on Computational Geometry, Graz, March 2007, pp. 170-173.

Abstract

We study the complexity of computing the Fréchet distance (also called dog-leash 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(n2) 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 linear-time algorithm to compute their weak Fréchet distance.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, and Gert Vegter:

Convex approximation by spherical patches

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 NP-hard.

  pdf file (gzipped)

Previous ← → Next

Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote, and Gerard Tel:

Wooden geometric puzzles: design and hardness proofs

  1. 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, Springer-Verlag, 2007, pp. 16–29. doi:10.1007/978-3-540-72914-3_4
  2. Theory of Computing Systems 44 (2009), 160–174. doi:10.1007/s00224-008-9104-3

Abstract

We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness 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(nk+1), for fixed k.
  pdf file (gzipped)

Previous ← → Next

Günter Rote, Francisco Santos, and Ileana Streinu:

Pseudo-triangulations — a survey

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 pseudo-triangle is a simple polygon with three convex vertices, and a pseudo-triangulation is a tiling of a planar region into pseudo-triangles. Pseudo-triangulations appear as data structures in computational geometry, as planar bar-and-joint 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, straight-line drawings from abstract versions called combinatorial pseudo-triangulations, algorithms and applications of pseudo-triangulations.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote and Gert Vegter:

Computational topology: an introduction

In: Effective Computational Geometry for Curves and Surfaces. Editors: Jean-Daniel Boissonnat and Monique Teillaud, Chapter 5. Mathematics and Visualization, Springer-Verlag, 2006, pp. 277–312. doi:10.1007/978-3-540-33259-6_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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Jean-Daniel Boissonnat, David Cohen-Steiner, Bernard Mourrain, Günter Rote, and Gert Vegter:

Meshing of surfaces

In: Effective Computational Geometry for Curves and Surfaces. Editors: Jean-Daniel Boissonnat and Monique Teillaud, Chapter 5. Mathematics and Visualization, Springer-Verlag, 2006, pp. 181–229. doi:10.1007/978-3-540-33259-6_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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote and Martin Zachariasen:

Matrix scaling by network flow

In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, January 2007, pp. 848-854.

Abstract

A given nonnegative n×n matrix A=(aij) is to be scaled, by multiplying its rows and columns by unknown positive multipliers λi and μj, such that the resulting matrix (aijλiμj) has specified row and column sums ri and sj. We give an algorithm that achieves the desired row and column sums with a maximum absolute error ε in O(n4(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 minimum-cost network flow problems with convex piecewise linear costs. These discretizations are interesting in their own right because they arise in proportional elections.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

R. L. Scot Drysdale, Günter Rote, and Astrid Sturm:

1. Approximation of an open polygonal curve with a minimum number of circular arcs

In: Abstracts of the 22nd European Workshop on Computational Geometry, Delphi, March 2006, pp. 25–28. (preliminary version with partial results)

2. Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

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 computer-aided 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(n2 log n) time for an original polygonal chain with n vertices.

Using a similar approach, we design an algorithm with a runtime of O(n2 log n), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.

  pdf file (gzipped)

Previous ← → Next

Sergio Cabello and Günter Rote:

Obnoxious centers in graphs

  1. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, January 2007, pp. 98–107. doi:10.1145/1283383.1283395
  2. 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 log2n + m log n) expected time. For planar graphs, we give algorithms with O(n log n) expected time and O(n log3n) worst-case time. For graphs with bounded treewidth, we give an algorithm taking O(n log n) worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote:

1. On the bounding boxes obtained by principal component analysis

In: Abstracts of the 22nd European Workshop on Computational Geometry, Delphi, March 2006, pp. 193-196. (preliminary version with partial results)

2. Upper and lower bounds on the quality of the PCA bounding boxes

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. 185-192.

Abstract

Principal component analysis (PCA) is commonly used to compute a bounding box of a point set in Rd. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes approximate the minimum-volume 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 R2.
  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Piecewise linear Morse theory

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 Mh={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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Eyal Ackerman, Kevin Buchin, Christiane Knauer, and Günter Rote:

Acyclic orientation of drawings

  1. 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, Springer-Verlag, 2006, pp. 266–277. doi:10.1007/11785293_26
  2. In: Abstracts of the 22nd European Workshop on Computational Geometry, Delphi, March 2006, pp. 207–210.
  3. 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.

  pdf file (gzipped)

Previous ← → Next

Wolfgang Mulzer and Günter Rote:

Minimum-weight triangulation is NP-hard

  1. 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
  2. Technical report B-05-23-revised, February 2008, 45 pages, arXiv:cs/0601002 [cs.CG], complete version with extra appendices.
  3. 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 straight-line graph whose vertex set is the given set. In the minimum-weight 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 NP-hard. We use a reduction from PLANAR 1-IN-3-SAT. 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 minimum-weight triangulation.

Note. NP-hardness of the POSITIVE PLANAR 1-IN-3-SAT problem has apparently been shown already by P. Laroche, Planar 1-in-3 satisfiability is NP-complete, ASMICS Workshop on Tilings, Deuxièmes journées polyominos et pavages, Ecole Normale Supérieure de Lyon, 1992, according to a reference in C. Moore and J. M. Robson, Hard tiling problems with simple tiles, Discrete & Computational Geometry 26 (2001), 573–590, DOI:10.1007/s00454-001-0047-6.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF @ACM

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:

The number of spanning trees in a planar graph

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.53n spanning trees. If it is 3-connected planar and without a face cycle of length three or four it has at most 2.848n spanning trees. These bound are obtained with a probabilistic method. They are applied to the construction of 3-dimensional polytopes with a given combinatorial structure and with small integral vertex coordinates. 

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter Rote:

Matching point sets with respect to the earth mover's distance

  1. In: Abstracts of the 21st European Workshop on Computational Geometry, Eindhoven, March 2005, pp. 57-60.
  2. 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, Springer-Verlag, 2005, pp. 520-531. doi:10.1007/11561071_47
  3. Computational Geometry, Theory and Applications 39 (2008), pp. 118-133. 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 color-based 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 polynomial-time (2+ε)-approximation algorithms for the minimum Euclidean EMD between A and B under translations and rigid motions.
  pdf file (gzipped)

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:

Locked and unlocked chains of planar shapes

  1. 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.
  2. Discrete and Computational Geometry 44 (2010), 439–462. doi:10.1007/s00454-010-9262-3, arXiv:cs/0604022 [cs.CG].

Abstract

We extend linkage unfolding results from the well-studied 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 self-intersection, 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 inward-normal property no longer holds.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Gill Barequet, Micha Moffie, Ares Ribó, and Günter Rote:

Counting polyominoes on twisted cylinders

  1. Discrete Mathematics and Theoretical Computer Science AE (2005), 369-374.
  2. 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.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote and André Schulz:

Threshold arrangements and the knapsack problem

Applied Mathematics Letters 19 (2006), 108-112. 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 well-studied combinatorial objects, and we correct an error in the analysis given in that paper.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Imre Bárány and Günter Rote:

Strictly convex drawings of planar graphs

Documenta Mathematica 11 (2006), 369–391.

Abstract

Every three-connected planar graph with n vertices has a drawing on an O(n2O(n2) grid in which all faces are strictly convex polygons. More generally, there is a drawing on an O(nw) ×O(n3/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.

Erratum:

The paper gives incorrect authors for reference [1]: On the maximal number of edges of convex digital polygons included into a square grid. The correct authors are Klaus Voss and Reinhard Klette, and the paper is in Russian. The authors of [2] are correctly stated as D. M. Acketa and J. D. Zunić.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

1. Adrian Dumitrescu, Ansgar Grüne, and Günter Rote:

Improved lower bound on the geometric dilation of point sets

In: Abstracts of the 21st European Workshop on Computational Geometry, Eindhoven, March 2005, pp. 37-40.

2. Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, and Günter Rote:

On geometric dilation and halving chords

In: Proceedings of the Workshop on Algorithms and Data Structures (WADS 2005), Waterloo, Canada, August 2005, Editors: Alexandro López-Ortiz, Frank Dehne, and Jörg-Rüdiger Sack. Lecture Notes in Computer Science, 3608, Springer-Verlag, 2005, pp. 244-255. doi:10.1007/11534273_22

3. Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, and Günter Rote:

On the geometric dilation of closed curves, graphs, and point sets

Computational Geometry, Theory and Applications 36 (2006), 16-38. 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. Ebbers-Baumann, 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Joe S. B. Mitchell, Günter Rote, and Lutz Kettner (editors):

Proceedings of the Twenty-First 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:

On the Fréchet distance of a set of curves

In: Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), Montreal, August 9-11, 2004, pp. 162-165.

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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Sergio Cabello, Erik D. Demaine, and Günter Rote:

Planar embeddings of graphs with specified edge lengths

  1. 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, Springer-Verlag, 2004, pp. 283–294. doi:10.1007/978-3-540-24595-7_26
  2. 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 NP-hard. In contrast, we show that the problem is tractable-indeed, solvable in linear time on a real RAM-for planar embeddings of planar 3-connected triangulations, even if the outer face is not a triangle. This result is essentially tight: the problem becomes NP-hard if we consider instead planar embeddings of planar 3-connected infinitesimally rigid graphs, a natural relaxation of triangulations in this context.
  pdf file (gzipped)

Previous ← → Next

Günter Rote:

Computing the Fréchet distance between piecewise smooth curves

  1. In: Abstracts of the 20th European Workshop on Computational Geometry, Seville, March 2004, pp. 147-150.
  2. Computational Geometry, Theory and Applications 37 (2007), 162-174. (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 well-behaved, 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.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Yi-Jen Chiang, Tobias Lenz, Xiang Lu, and Günter Rote:

1. Simple and output-sensitive construction of contour trees using monotone paths

Technical report ECG-TR-244300-01, May 2003, 21 pages.

2. Simple and optimal output-sensitive construction of contour trees using monotone paths

Computational Geometry, Theory and Applications 30 (2005), 165-195. doi:10.1016/j.comgeo.2004.05.002

Abstract

Contour trees are used when high-dimensional data are preprocessed for efficient extraction of iso-contours 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 component-critical 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Oswin Aichholzer, Günter Rote, Bettina Speckmann, and Ileana Streinu:

The zigzag path of a pseudo-triangulation

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örg-Rüdiger Sack, and Michiel Smid. Lecture Notes in Computer Science 2748, Springer-Verlag, 2003, pp. 377–388. doi:10.1007/978-3-540-45078-8_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 divide-and-conquer style. We present an algorithm that enumerates all zigzag paths of a given point set with respect to a given line in O(n2) time per path and O(n2) space.

  PostScript file (gzipped)

Previous ← → Next

David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, and Walter Whiteley:

Non-crossing frameworks with non-crossing reciprocals

Discrete and Computational Geometry 32 (2004), 567–600. (Special issue in honor of Lou Billera), doi:10.1007/s00454-004-1139-x, arXiv:math/0309156 [math.MG].

Abstract

We study non-crossing frameworks in the plane for which the classical reciprocal on the dual graph is also non-crossing. We give a complete description of the self-stresses on non-crossing frameworks G whose reciprocals are non-crossing, in terms of: the types of faces (only pseudo-triangles and pseudo-quadrangles 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 non-crossingness and rigidity of straight-line plane graphs is studied, pseudo-triangulations show up as objects of special interest. For example, it is known that all planar Laman circuits can be embedded as a pseudo-triangulation with one non-pointed vertex. We show that for such pseudo-triangulation embeddings of planar Laman circuits which are sufficiently generic, the reciprocal is non-crossing and again a pseudo-triangulation embedding of a planar Laman circuit. For a singular (non-generic) pseudo-triangulation embedding of a planar Laman circuit, the reciprocal is still non-crossing and a pseudo-triangulation, but its underlying graph may not be a Laman circuit. Moreover, all the pseudo-triangulations which admit a non-crossing reciprocal arise as the reciprocals of such, possibly singular, stresses on pseudo-triangulation Laman circuits.

All self-stresses on a planar graph correspond to liftings to piece-wise linear surfaces in 3-space. We prove characteristic geometric properties of the lifts of such non-crossing reciprocal pairs.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter Whiteley:

Planar minimally rigid graphs and pseudo-triangulations

  1. 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
  2. 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 pseudo-triangulations 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 pseudo-triangulations, 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.
  pdf file (gzipped)

Previous ← → Next

Helmut Alt, Christian Knauer, Günter Rote, and Sue Whitesides:

1. The complexity of (un)folding

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

2. On the complexity of the linkage reconfiguration problem

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 PSPACE-complete.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Nina Amenta, Sunghee Choi, and Günter Rote:

Incremental constructions con BRIO

in: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego, June 8-10, 2003. Association for Computing Machinery, 2003, pp. 211-219. 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 worst-case behavior.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF @ACM

Previous ← → Next

Günter Rote:

Crossing the bridge at night

EATCS Bulletin (Bulletin of the European Association for Theoretical Computer Science), No. 78, October 2002, 241-246.

Abstract

We solve the general case of the bridge-crossing 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 graph-theoretic model.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote:

Pursuit-evasion with imprecise target location.

In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, January 12–14, 2003. pp. 747–753.
http://dl.acm.org/citation.cfm?id=644108.644231
  BibTeX  pdf file (gzipped)

Previous ← → Next

Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk:

1. Matching planar maps

In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, January 12–14, 2003, pp. 589–598.

2. Matching planar maps

Journal of Algorithms 49 (2003), 262–283. doi:10.1016/S0196-6774(03)00085-3

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.
  PostScript file (gzipped)

3. Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, and Günter Rote:

Finding a curve in a map (Video)

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
  free PDF @ACM

Previous ← → Next

Günter Rote, Cao An Wang, Lusheng Wang, and Yinfeng Xu:

On constrained minimum pseudotriangulations

to appear in: "Computing and Combinatorics". Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, USA, July 2003. Editors: Tandy Warnow and Binhai Zhu. Lecture Notes in Computer Science, Springer-Verlag, 2003.

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 linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation, and we study the minimum pseudotriangulation containing a given set of non-crossing line segments.

  PostScript file (gzipped)   pdf file (gzipped)

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
  BibTeX  free PDF @ACM

Previous ← → Next

Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, and Carola Wenk:

1. Covering shapes by ellipses

In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, January 2002, pp. 453–454. doi:10.1145/545381.545441

2. Covering with ellipses

Algorithmica 38 (2003), 145–160. doi:10.1007/s00453-003-1047-0

Abstract

We address the problem of how to cover a set of required points by a small number of axis-parallel 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 ellipse-shaped protein spots in two-dimensional electrophoresis images.

  free PDF view@Springer

Previous ← → Next

Robert Elsässer, Burkhard Monien, Günter Rote, and Stefan Schamberger:

Toward optimal diffusion matrices.

Technical report ALCOMFT-TR-02-98, 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
  BibTeX  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote:

Binary trees having a given number of nodes with 0, 1, and 2 children

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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Robert Connelly, Erik D. Demaine, and Günter Rote:

Infinitesimally locked self-touching linkages with applications to locked trees

in: "Physical Knots: Knotting, Linking, and Folding Geometric Objects in R3." Editors: Jorge Alberto Calvo, Kenneth C. Millett, and Eric J. Rawdon. Contemporary Mathematics 304, American Mathematical Society 2002, pp. 287-311,

Abstract

We propose a new algorithmic approach for analyzing whether planar linkages are locked in many cases of interest.  The idea is to examine self-touching 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 first-order rigidity and equilibrium stresses. Then we show how to relate locked self-touching frameworks to locked frameworks that closely approximate the self-touching frameworks.
Our motivation is that most existing approaches to locked linkages are based on approximations to self-touching 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 degree-3 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.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote, Francisco Santos, and Ileana Streinu:

Expansive motions and the polytope of pointed pseudo-triangulations

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/978-3-642-55566-4_33, arXiv:math/0206027 [math.CO].

Abstract

We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the increase of their distances. Its 1-skeleton is the graph whose vertices are the pointed pseudo-triangulations of the point set and whose edges are flips of interior pseudo-triangulation 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 n-gon, 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 1-dimensional 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 by-product 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).

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Dana Randall, Günter Rote, Francisco Santos, and Jack Snoeyink:

Counting triangulations and pseudo-triangulations of wheels

In: Proceedings of the 13th Canadian Conference on Computational Geometry, Waterloo, August 6-10, 2001. Editor: T. Biedl; pp. 149-152.

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 pseudo-triangulations 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 <= 3i#T for the numbers of minimum pseudo-triangulations and triangulations of any point configuration with i interior points.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Peter Braß, Günter Rote, and Konrad J. Swanepoel:

Triangles of extremal area or perimeter in a finite planar point set

Discrete and Computational Geometry 26 (2001), 51–58. doi:10.1007/s00454-001-0010-6

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 Θ(n2).

  free PDF view@Springer

Previous ← → Next

Friedrich Eisenbrand and Günter Rote:

Fast 2-variable integer programming

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, Springer-Verlag, 2001, pp. 78–89. doi:10.1007/3-540-45535-3_7

Abstract

We show that a 2-variable 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 s-bit 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.

  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

Friedrich Eisenbrand and Günter Rote:

Fast reduction of ternary quadratic forms

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, Springer-Verlag, 2001, pp. 32–44. doi:10.1007/3-540-44670-2_4

Abstract

We show that a positive definite integral ternary form can be reduced with O(M(s)log2s) bit operations, where s is the binary encoding length of the form and M(s) is the bit-complexity of s-bit 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 binary-form 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)logd-1s) bit-operations.

  PostScript file (gzipped)   pdf file (gzippedTeX .dvi file (gzipped)

Previous ← → Next

Robert Connelly, Erik D. Demaine, and Günter Rote:

Straightening polygonal arcs and convexifying polygonal cycles

  1. Every polygon can be untangled
    In: Proceedings of the 16th European Workshop on Computational Geometry, Ben-Gurion University of the Negev, Israel, January 2000, pp. 62–65.
  2. 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
  3. Discrete and Computational Geometry 30 (2003), 205–239. doi:10.1007/s00454-003-0006-7 (This is a more detailed version of 2.)
  4. Technical report B02-02, 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 piecewise-differentiable, 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.

  pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Günter Rote:

Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches

In: "Computational Discrete Mathematics." Editor: Helmut Alt. Lecture Notes in Computer Science 2122, Springer-Verlag, 2001, pp. 119–135. doi:10.1007/3-540-45506-X_9

Abstract

The most common algorithm for computing the determinant of an n×n-matrix is Gaussian elimination and needs O(n3) 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(n4) 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 skew-symmetric 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.
  PostScript file (gzipped)
TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote and Gerhard J. Woeginger:

Minimizing the number of tardy jobs on a single machine with batch setup times

Acta Cybernetica 13 (1998), 423-429.

Abstract

This paper investigates a single-machine 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 due-dates, 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 NP-complete [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 tree-structured constraint system, which can be solved to optimality in polynomial time.

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)

Previous ← → Next

Tamás Fleiner, Volker Kaibel, and Günter Rote:

Upper bounds on the maximal number of facets of 0/1-polytopes

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 d-dimensional 0/1-polytope (a polytope whose vertices have coordinates 0 and 1) can have. The first one is 2(d-1)!+2(d-1), which is the best one currently known for small dimensions, while the second one, O((d-2)!), 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.6d 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Rainer E. Burkard, Yixun Lin, Helidon Dollani, and Günter Rote:

The obnoxious center problem on a tree

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.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Martin Gavalec and Günter Rote:

Reachability of fuzzy matrix period

Tatra Mountains Mathematical Publications 16 (1999), 61–79.

Abstract

Given an n×n matrix A, the problem is to decide whether there is an n-vector x such that the sequence of matrix powers A, A2, A3, ... has the same period length as the sequence Ax, A2x, A3x, ... of iterates of x. In these matrix-matrix and matrix-vector multiplications, the usual operations + and * are replaced by max and min, respectively.

In general, this problem is NP-complete. Two conditions are described, which both together imply that it can be solved in O(n2) time. If only one of the conditions is satisfied, the problem remains NP-complete.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote and Gerhard J. Woeginger:

Time complexity and linear-time approximation of the ancient two machine flow shop

Journal of Scheduling 1 (1998), 149–155. doi:10.1002/(SICI)1099-1425(1998100)1:3<149::AID-JOS10>3.0.CO;2-4

Abstract

We consider the scheduling problems F2|.|Cmax and F2|no-wait|Cmax, 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, and Günter Rote:

Generalized self-approaching curves

  1. In: "Algorithms and Computation—Ninth Annual International Symposium on Algorithms and Computation. Taejon, Korea, December 1998". Proceedings of ISAAC'98. Editors: Kyung-Yong Chwa and Oscar H. Ibarra. Lecture Notes in Computer Science 1533, Springer-Verlag, 1998, pp. 317–327. doi:10.1007/3-540-49381-6_34
  2. Discrete Applied Mathematics 109 (2001), 3–24. doi:10.1016/S0166-218X(00)00233-X

Abstract

For an angle φ between 0 and 180o, we consider the class of oriented curves which are φ-self-approaching 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 self-approaching curves which are 90o-self-approaching. We prove a tight upper bound on the length of a φ-self-approaching 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 on-line navigation strategies. A closely related problem concerns curves with increasing chords.

  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

Jerrold R. Griggs and Günter Rote:

On the distribution of sums of vectors in general position

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. 139-142.

Abstract

An analog of the Littlewood-Offord 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 Rd 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(2nn1-3d/2), which compares for d>1 to the previously known upper bound O(2nn-1-d/2).
  PostScript file (gzipped)   pdf file (gzipped)

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:

A visibility representation for graphs in three dimensions

Journal of Graph Algorithms and Applications 2, no. 3 (1998), 1–16. doi:10.7155/jgaa.00006

Abstract

We propose a 3-dimensional visibility representation of graphs in which vertices are mapped to horizontal axis-parallel rectangles floating in 3-space, with edges represented by vertical lines of sight. We apply an extension of the Erdös-Szekeres 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.
  PostScript file 2.15 MByte (gzipped, 238 kBytes) pdf file (gzipped)

Previous ← → Next

Imre Bárány, Günter Rote, William Steiger, and Cun-Hui Zhang:

A central limit theorem for convex chains in the square

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.
  PostScript file (gzippedpdf file (gzippedTeX .dvi file (some non-essential figures are missing.) (gzippedfree PDF view@Springer

Previous ← → Next

Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and Yin-Feng Xu:

Constant-level greedy triangulations approximate the MWT well

  1. In: Proceedings of the Second International Symposium on Operations Research and its Applications (ISORA'96), Guilin, China, December 11–13, 1996. Editors: Ding-Zhu Du, Xiang-Sun Zhang, and Kan Cheng. Lecture Notes in Operations Research 2, World Publishing Corporation, Beijing 1996, pp. 309–318.
  2. Journal of Combinatorial Optimization 2 (1999), 361–369.

Abstract

The well-known 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 so-called 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·2k+1 times the minimum-weight triangulation of the point set.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote and Guochuan Zhang:

Optimal logistics for expeditions - the jeep problem with complete refilling

SFB-Bericht 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Helmut Alt, Ulrich Fuchs, Günter Rote, and Gerald Weber:

Matching convex shapes with respect to the symmetric difference

  1. 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, Springer-Verlag, 1996, pp. 320–333. doi:10.1007/3-540-61680-2_65
  2. 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)   free PDF view@Springer

Previous ← → Next

Marek Lassak, Janusz Januszewski, Günter Rote, and Gerhard Woeginger:

1. On-line q-adic covering by the method of the n-th segment and its application to on-line covering by cubes

Beiträge zur Algebra und Geometrie - Contributions to Algebra and Geometry 37 (no. 1) (1996), 51-65, (Zbl 863.52010).

Abstract

In the on-line covering problem for covering the unit cube by cubes, we are given a sequence of smaller cubes of side lengths s1, s2,...,sn, and we have to place them in such a way that the whole unit cube in d-dimensional Euclidean space is covered if possible. The cubes are axis-parallel, they are allowed to overlap, but the algorithm must place the i-th cube before knowing the future cubes si+1, si+2,...

We describe algorithms which are guaranteed to find a covering on-line provided that the total volume (the sum of sid) is at least 2d+3. (The true bound is actually a little smaller.) This performance guarantee is quite strong, considering that the existence of an (off-line) covering can only be ensured if the total volume is at least 2d-1. The best previous on-line bound was 4d, due to Wlodek Kuperberg.

We reduce this problem to an online interval covering problem for q-adic 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 on-line algorithm, the so-called "method of the n-th 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=2d these methods carry over to the covering problem for d-dimensional cubes whose side lengths are powers of 2.
 
 

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)

2. Solution to problem 74

Mathematische Semesterberichte 43 (1996), 94-100.

Abstract

This paper contains a different proof of a special case of the main result of the above paper, complemented by a lower-bound construction.
  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

1. Oswin Aichholzer, Franz Aurenhammer, Siu-Wing Cheng, Naoki Katoh, Michael Taschwer, Günter Rote, and Yin-Feng Xu:

Triangulations intersect nicely

Discrete and Computational Geometry 16 (1996), 339-359, (Zbl 857.68110). doi:10.1007/BF02712872

2. Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and Michael Taschwer:

Triangulations intersect nicely

In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, Vancouver, June 5-7, 1995. Association for Computing Machinery, 1995; pp. 220-229. 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 easy-to-recognize class of point sets where the minimum-weight 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.

 PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)

Previous ← → Next

Robert L. Scot Drysdale, Günter Rote, and Oswin Aichholzer:

A simple linear time greedy triangulation algorithm for uniformly distributed points.

Bericht IIG-408, February 1995, Technische Universität Graz, Institute für Informationsverarbeitung, February 1995, 16 pages.
  BibTeX  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Mordecai J. Golin and Günter Rote:

A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs

  1. 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, Springer-Verlag, 1995, pp. 256-267.
  2. IEEE Transactions on Information Theory 44 (1998), 1770-1781.

Abstract

We consider the problem of constructing minimum cost prefix-free 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(nC+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 PostScript-file.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Rainer E. Burkard, Eranda Çela, Günter Rote, and Gerhard J. Woeginger:

The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

  1. 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, Springer-Verlag, 1996, pp. 204–218. doi:10.1007/3-540-61310-2_16
  2. 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 Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge-Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge-Toeplitz QAP: We identify conditions on the Toeplitz matrix that lead to a simple solution for the Anti-Monge–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 NP-hard and consequently, that the Anti-Monge–Toeplitz QAP is NP-hard in general.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)   free PDF view@Springer

Previous ← → Next

Helmut Alt, Oswin Aichholzer, and Günter Rote:

Matching shapes with a reference point

  1. Extended abstract in: Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, June 6-8, 1994. Association for Computing Machinery, 1994, pp. 85-92. doi:10.1145/177424.177555
  2. International Journal on Computational Geometry and Applications 7 (1997), pp. 349-363, (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 so-called 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote:

Finding a shortest vector in a two-dimensional lattice modulo m

Theoretical Computer Science 172 (1997), 303–308. doi:10.1016/S0304-3975(96)00185-5

Abstract

We find the shortest non-zero 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 Minkowski-reduced basis for a planar lattice and thereby show that the problem can be solved in O(log m (log log m)2) bit operations.
  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

János Aczél, Günter Rote, and Jens Schwaiger:

1. Webs, iteration groups, and equivalent changes in probabilities

1a. In: “VIII. Mathematikertreffen Zagreb-Graz”, 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).

2. Equivalence of changes in proportions at crossroads of mathematical theories

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 Knowledge-Based 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

Yew-Kwang Ng (Quart. Appl. Math. 49 (1991), 289--301) 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.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Johannes Hagauer and Günter Rote:

Three-clustering of points in the plane

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, Springer-Verlag, 1993, pp. 192-199.

2. Computational Geometry, Theory and Applications 8 (1997), pp. 87-95.

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(n2 log2n) time.
  PostScript file (gzippedpdf file (gzipped) TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote and Robert Franz Tichy:

Quasi-Monte-Carlo methods and the dispersion of point sequences

Mathematical and Computer Modelling 23 (1996), 9-23, (Zbl 855.11041).

Abstract

Quasi-Monte-Carlo methods are well-known 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, axis-parallel 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 well-known 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote and Robert Franz Tichy:

Spherical dispersion with an application to polygonal approximation of curves

Anzeiger der Österreichischen Akademie der Wissenschaften, Mathematisch-naturwissenschaftliche Klasse, Abteilung II 132 (1995), 3-10, (Zbl 865.11054).

Abstract

We describe and analyze a procedure for the polygonal approximation of spatial curves using “well-distributed” points on the sphere. Here the dispersion of the point set with respect to spherical slices (intersections of two half-spheres) plays a role.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote:

Curves with increasing chords

Mathematical Proceedings of the Cambridge Philosophical Society 115 (1994), 1-12, (Zbl 802.51023).

Abstract

A curve has increasing chords if ADBC 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 self-approaching curves.
  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Vladimir G. Deineko, René van Dal, and Günter Rote:

The convex-hull-and-line traveling salesman problem: A solvable case

Information Processing Letters 51 (1994), 141-148, (Zbl 806.90121).

Abstract

We solve the special case of the Euclidean Traveling Salesman Problem where n-m 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 3-line Traveling Salesman Problem.

  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Günter Rote, Christian Schwarz, and Jack Snoeyink:

Maintaining the approximate width of a set of points in the plane (extended abstract)

In: Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, August 5-9, 1993. Editor: A. Lubiw, J. Urrutia; pp. 258-263.

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(log2 n). The method uses the tentative prune-and-search strategy of Kirkpatrick and Snoeyink
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Alon Efrat, Günter Rote, and Micha Sharir:

On the union of fat wedges and separating a collection of segments by a line

1. In: Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, August 5-9, 1993. Editor: A. Lubiw, J. Urrutia; pp. 115-120.
2. Computational Geometry: Theory and Applications 3 (1993), 277-288, (Zbl 801.68167).

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 Matousek et al.


Previous ← → Next

Günter Rote:

Sequences with subword complexity 2n

Journal of Number Theory 46 (1993), 196-213, (Zbl 804.11023).

Abstract

We discuss infinite 0-1-sequences 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: L-systems, infinite words, iterated morphisms

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (figures not complete) (gzipped)

Previous ← → Next

Günter Rote:

A new metric between polygons, and how to compute it (extended abstract)

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, Springer-Verlag, 1992, pp. 404-415.

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 Monge-Kantorovich 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.

  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

Günter Rote:

Degenerate convex hulls in high dimensions without extra storage (extended abstract)

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 depth-first 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.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF @ACM

Previous ← → Next

Rainer E. Burkard, Bernd Fruhwirth, and Günter Rote:

Vehicle routing in an automated warehouse: analysis and optimization

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 lay-out 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)   free PDF view@Springer

Previous ← → Next

David Eppstein, Mark Overmars, Günter Rote, and Gerhard Woeginger:

Finding minimum area k-gons.

Discrete and Computational Geometry 7 (1992), 45–58, (Zbl 746.68038, MR #92k:52026). doi:
10.1007/BF02187823
  BibTeX  free PDF view@Springer

Previous ← → Next

Günter Rote:

1. The convergence rate of the Sandwich algorithm for approximating convex functions

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/n2), 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzippedfree PDF view@Springer

2. The convergence rate of the Sandwich algorithm for approximating convex figures in the plane (extended abstract)

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:

Minimum-link paths among obstacles in the plane

  1. Algorithmica 8 (1992), 431–459, (Zbl 788.68144). doi:10.1007/BF01758855
  2. 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 minimum-link path) between two points in time O(Eα(n)log2n) 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 minimum-link paths from s to all obstacle vertices. This leads to a method of solving the query version of our problem (for query points t).
  PostScript file (gzipped)   pdf file (gzipped)   free PDF view@Springer

Previous ← → Next

Rudolf Fleischer, Kurt Mehlhorn, Günter Rote, Emo Welzl, and Chee Yap:

1. On spontaneous inner and outer approximation of shapes

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

2. Simultaneous inner and outer approximation of shapes

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 k-gon Q with λ(P,Q)≤λ(k). Among other results, we prove that 2.118...≤λ(3)≤2.25 and λ(k) = 1 + Θ(1/k2). We give an O(n2 log2n)-time algorithm which, for any input convex n-gon 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 motion-planning 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.

  free PDF view@Springer

Previous ← → Next

1. Günter Rote and Andreas Vogel:

A heuristic for decomposing traffic matrices in TDMA satellite communication

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:

A heuristic for decomposing traffic matrices in TDMA satellite communication

Bericht 73-1990, Technische Universität Graz, 28 pages; (slightly extended version of 1.)

3. Günter Rote:

Eine Heuristik für ein Matrizenzerlegungsproblem, das in der Telekommunikation via Satelliten auftritt (Kurzfassung)

(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 time-division 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 n2. When the number of matrices is restricted to n, the problem is NP-hard. 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 n2 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.

  pdf file (gzipped)

Previous ← → Next

Christian Icking, Günter Rote, Emo Welzl, and Chee Yap:

Shortest paths for line segments

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 surface-area formula. This new approach is relatively elementary, and yields new insights.

  free PDF view@Springer

Previous ← → Next

1. Gerhard Woeginger, Günter Rote, Binhai Zhu, and Zhengyan Wang :

Counting k-subsets and convex k-gons in the plane

Information Processing Letters 38 (1991), 149-151, (Zbl 737.68084, MR #92i:68183).

2. Günter Rote and Gerhard Woeginger:

Counting convex k-gons in planar point sets

Information Processing Letters 41 (1992), 191-194, (Zbl 751.68077, MR #93c:68108).

3. Joseph S. B. Mitchell, Günter Rote, Gopalakrishnan Sundaram, and Gerhard Woeginger:

Counting convex polygons in planar point sets

Information Processing Letters 56 (1995), 45-49, (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 k-gons whose corners belong to the given point set. The first paper gives an O(nk-2) algorithm for this problem, improving over the trivial O(nk) algorithm. In the second paper, a refinement of the technique improves the complexity to O(nfloor(k/2)). This time bound has been subsequently improved to O(k n3) in the third paper.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Günter Rote:

Computing the minimum Hausdorff distance between two point sets on a line under translation

Information Processing Letters 38 (1991), 123–127, (Zbl 736.68078, MR #92d:68114). doi:10.1016/0020-0190(91)90233-8

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.
  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Paul Hilfinger, Eugene L. Lawler, and Günter Rote:

Flattening a rooted tree

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. 335-340, (Zbl 733.68061, MR #92i:68122).

Abstract

The following is a graph-theoretic formulation of a problem arising in the compilation of block-structured 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 linear-time, 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, mn 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:

Sandwich approximation of univariate convex functions with an application to separable convex programming

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:

Geometric clusterings

  1. Extended abstract in: Proceedings of the Second Canadian Conference on Computational Geometry, Ottawa, August 6-10, 1990. Editor: J. Urrutia; pp. 28-31.
  2. Journal of Algorithms 12 (1991), 341-356, (Zbl 734.68092, MR #92d:52033).

Abstract

A k-clustering 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 k-clustering 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 3-clustering, an improved algorithm was later given in the paper Three-clustering of points in the plane.)

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)

Previous ← → Next

Rainer E. Burkard, Günter Rote, En-Yu Yao, and Zhong-Liang Yu:

Shortest polygonal paths in space

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.

  free PDF view@Springer

Previous ← → Next

Günter Rote:

Path problems in graphs

In: "Computational Graph Theory". Editors: G. Tinhofer, E. Mayr, H. Noltemeier, and M. Syslo, in cooperation with R. Albrecht. Springer-Verlag, 1990. Computing Supplementum 7 (1990), pp. 155–189, (Zbl 699.68088, MR #91m:05122).

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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)

Previous ← → Next

Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, and Emo Welzl:

Approximation of convex figures by pairs of rectangles

  1. (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, Springer-Verlag, 1990, pp. 240–249, (Zbl 729.68087, MR #91e:68148). doi:10.1007/3-540-52282-4_47
  2. (Improved and extended version)
    Computational Geometry, Theory and Applications 10 (1998), pp. 77–87. doi:10.1016/S0925-7721(96)00019-3

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(log2n).
  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

Richard Pollack, Micha Sharir, and Günter Rote:

Computing the geodesic center of a simple polygon

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).

  free PDF view@Springer

Previous ← → Next

Rainer E. Burkard, Günter Rote, Günther Ruhe, and Norbert Sieber:

Algorithmische Untersuchungen zu bikriteriellen kostenminimalen Flüssen in Netzwerken

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 minimum-cost 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.

  pdf file (gzipped)

Previous ← → Next

Bernd Fruhwirth, Rainer E. Burkard, and Günter Rote:

Approximation of convex curves with application to the bicriterial minimum cost flow problem

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 left-to-right 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 left-to-right 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:

Two solvable cases of the traveling salesman problem

Ph. D. thesis, Technische Universität Graz, May 1988, 55 pages. (Supervisor: Prof. Dr. R. E. Burkard).

This thesis contains the paper The N-line 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 N-line 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 N-line traveling salesman problem for n points in time nN, 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(n3/2) time whether a given tour is a necklace tour, improving an algorithm of Edelsbrunner, Rote, and Welzl (1988) which takes O(n2) 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(n2 log n) time and linear space, whether a necklace tour exists for a given point set, by transforming the problem to a fractional 2-factor problem on a sparse bipartite graph. Both algorithms also compute radii for the disks realizing the necklace tour.

  PostScript file (gzippedpdf file (gzipped)

Previous ← → Next

Günter Rote:

The N-line traveling salesman problem

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 N-line traveling salesman problem for n points in time nN, 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.
  PostScript file (gzipped)   pdf file (gzipped)

Previous ← → Next

Herbert Edelsbrunner, Günter Rote, and Emo Welzl:

Testing the necklace condition for shortest tours and optimal factors in the plane

1. Theoretical Computer Science 66 (1989), 157-180, (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, Springer-Verlag, 1987, pp. 364-375, (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(n2) time whether a given tour is a necklace tour. We give another algorithm which tests in O(n2 log n) time and linear space whether a necklace tour exists for a given point set, by transforming the problem to a fractional 2-factor problem on a sparse bipartite graph. Both algorithms can be generalized to m-factors 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(n3/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:

A parallel scheduling algorithm for minimizing the number of unscheduled jobs

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. North-Holland, 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 due-dates, in order to maximize the number of jobs that are finished on time. The well-known Moore-Hodgson 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(log2n) time on n2 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 C-32, 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.

  pdf file (gzipped)

Previous ← → Next

Günter Rote:

On the connection between hexagonal and unidirectional rectangular systolic arrays

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, Springer-Verlag, 1986, pp. 70-83.

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, 187-199.

Then we derive a new hexagonal array for solving a certain type of dynamic programming recursion that arises for example in context-free 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.756-763. 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, two-level pipelining, and algorithm partitioning.


Previous ← → Next

Günter Rote and Franz Rendl:

Minimizing the density of terminal assignments in layout design

Operations Research Letters 5 (1986), 111-118, (Zbl 626.90069, MR #87k:90103). doi:10.1016/0167-6377(86)90083-0

Abstract

We present a linear-time 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:

The solution sets of extremal equations

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 2n minimal solutions.

  pdf file (gzipped)

Previous ←

Günter Rote:

A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)

  1. 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.
  2. 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.
  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 Warshall-Floyd 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.

  scanned TIFF file   Postscript file gzipped   pdf file (gzipped)   free PDF view@Springer