@comment{for the raw BibTeX file, see rote.bib}
%%% 1:
@techreport{r-saapp-84
, author = {G{\"u}nter Rote}
, title = {A systolic array for the algebraic path problem (which includes the inverse of a matrix and shortest distances in a graph)}
, year = {1984}
, number = {Bericht 101}
, institution = {Rechenzentrum Graz}
, pages = {69 pages}
, publisher = {Rechenzentrum Graz}
}
%%% 1a:
@mastersthesis{r-saaap-85m
, author = {G{\"u}nter Rote}
, title = {A systolic array algorithm for the algebraic path problem}
, year = {1985}
, month = feb
, school = {Technische Universit{\"a}t Graz, Institut f{\"u}r Mathematik}
}
%%% 2:
@article{r-saaap-85
, author = {G{\"u}nter Rote}
, title = {A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)}
, journal = {Computing}
, year = {1985}
, volume = {34}
, pages = {191--219}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/A+systolic+array+algorithm+for+the+algebraic+path+problem+(shortest+paths;+matrix+inversion).pdf}
, doi = {10.1007/BF02253318}
}
%%% 3:
@techreport{r-ssee-85
, author = {G{\"u}nter Rote}
, title = {The solution sets of extremal equations}
, year = {1985}
, number = {Bericht 104}
, institution = {Rechenzentrum Graz}
, pages = {58 pages}
, publisher = {Rechenzentrum Graz}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+solution+sets+of+extremal+equations.pdf}
, 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\times n$ system of maxmin equations has less than $2^n$ minimal solutions. }
}
%%% 4:
@article{rr-mdtal-86
, author = {G{\"u}nter Rote and Franz Rendl}
, title = {Minimizing the density of terminal assignments in layout design}
, journal = {Operations Research Letters}
, year = {1986}
, volume = {5}
, pages = {111--118}
, 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.}
}
%%% 5:
@inproceedings{r-cbhur-86
, author = {G{\"u}nter Rote}
, title = {On the connection between hexagonal and unidirectional rectangular systolic arrays}
, year = {1986}
, volume = {227}
, pages = {70--83}
, booktitle = {VLSI Algorithms and Architectures---Aegean Workshop on Computing. Loutraki, Greece, July 1986}
, editor = {F. Makedon and K. Mehlhorn and T. Papatheodorou and P. Spirakis}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-16766-8_7}
, 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 multiplications for the evaluation of an associative product. 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.}
}
%%% 6:
@inproceedings{r-psamn-86
, author = {G{\"u}nter Rote}
, title = {A parallel scheduling algorithm for minimizing the number of unscheduled jobs}
, year = {1986}
, pages = {99--108}
, booktitle = {Parallel Algorithms \& Architectures. Proceedings of the International Workshop on Parallel Algorithms and Architectures, Centre National de Rencontres Math{\'e}matiques, Luminy, France, April 14--18, 1986}
, editor = {M. Cosnard and Y. Robert and P. Quinton and M. Tchuente}
, publisher = {North-Holland}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/A+parallel+scheduling+algorithm+for+minimizing+the+number+of+unscheduled+jobs.pdf}
, 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(\log ^2 n)$ time on $n^2$ processors in the single instruction stream, multiple data stream (SIMD) shared memory model without write conflicts but with read conflicts allowed. Our approach is based on the binary tree method of Dekel and Sahni (Binary trees and parallel scheduling algorithms, {\it 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.}
}
%%% 7:
@article{erw-tncst-89
, author = {Herbert Edelsbrunner and G{\"u}nter Rote and Emo Welzl}
, title = {Testing the necklace condition for shortest tours and optimal factors in the plane}
, journal = {Theoretical Computer Science}
, year = {1989}
, volume = {66}
, pages = {157--180}
, doi = {10.1016/0304-3975(89)90133-3}
}
%%% 7a:
@inproceedings{erw-tncst-87
, author = {Herbert Edelsbrunner and G{\"u}nter Rote and Emo Welzl}
, title = {Testing the necklace condition for shortest tours and optimal factors in the plane}
, year = {1987}
, volume = {267}
, pages = {364--375}
, booktitle = {Automata, Languages, and Programming. Proceedings of the 14th International Colloquium on Automata, Languages, and Programming (ICALP), Karlsruhe, Juli 1987}
, editor = {T. Ottmann}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-18088-5_31}
}
%%% 8:
@article{r-nltsp-92
, author = {G{\"u}nter Rote}
, title = {The ${N}\!$-line traveling salesman problem}
, journal = {Networks}
, year = {1992}
, volume = {22}
, pages = {91--108}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+N-line+traveling+salesman+problem.ps}
, doi = {10.1002/net.3230220106}
}
%%% 9:
@phdthesis{r-tscts-88
, author = {G{\"u}nter Rote}
, title = {Two solvable cases of the traveling salesman problem}
, year = {1988}
, month = may
, school = {Technische Universit{\"a}t Graz, Institut f{\"u}r Mathematik}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Two+solvable+cases+of+the+traveling+salesman+problem.ps}
}
%%% 10:
@article{fbr-accab-89
, author = {Bernd Fruhwirth and Rainer E. Burkard and G{\"u}nter Rote}
, title = {Approximation of convex curves with application to the bicriterial minimum cost flow problem}
, journal = {European Journal of Operational Research}
, year = {1989}
, volume = {42}
, pages = {326--338}
, doi = {10.1016/0377-2217(89)90443-8}
, 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.}
}
%%% 11:
@article{brrs-auzbk-89
, author = {Rainer E. Burkard and G{\"u}nter Rote and G{\"u}nther Ruhe and Norbert Sieber}
, title = {Algorithmische {Untersuchungen} zu bikriteriellen kostenminimalen {Fl{\"u}ssen} in {Netzwerken}}
, journal = {Wissenschaftliche Zeitschrift der Technischen Hochschule Leipzig}
, year = {1989}
, volume = {33}
, pages = {333--341}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Algorithmische+Untersuchungen+zu+bikriteriellen+kostenminimalen+Fluessen+in+Netzwerken.pdf}
, 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.}
}
%%% 12:
@article{psr-cgcsp-89
, author = {Richard Pollack and Micha Sharir and G{\"u}nter Rote}
, title = {Computing the geodesic center of a simple polygon}
, journal = {Discrete and Computational Geometry}
, year = {1989}
, volume = {4}
, pages = {611--626}
, 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)$.}
}
%%% 13:
@inproceedings{sfrw-acfpr-90
, author = {Otfried Schwarzkopf and Ulrich Fuchs and G{\"u}nter Rote and Emo Welzl}
, title = {Approximation of convex figures by pairs of rectangles}
, year = {1990}
, volume = {415}
, pages = {240--249}
, booktitle = {Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS'90)}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-52282-4_47}
}
%%% 13a:
@article{sfrw-acfph-98
, author = {Otfried Schwarzkopf and Ulrich Fuchs and G{\"u}nter Rote and Emo Welzl}
, title = {Approximating a convex figure by a pair of homothetic rectangles}
, journal = {Computational Geometry, Theory and Applications}
, year = {1998}
, volume = {10}
, pages = {77--87}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Approximation+of+convex+figures+by+pairs+of+rectangles.ps}
, doi = {10.1016/S0925-7721(96)00019-3}
}
%%% 14:
@article{r-ppg-90
, author = {G{\"u}nter Rote}
, title = {Path problems in graphs}
, journal = {Computing Supplementum}
, year = {1990}
, volume = {7}
, pages = {155--189}
, booktitle = {Computational Graph Theory}
, editor = {G. Tinhofer and E. Mayr and H. Noltemeier and M. Sys{\l }o}
, publisher = {Springer-Verlag}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Path+problems+in+graphs.ps}
, abstract = {A large variety of problems in computer science can be viewed from a common viewpoint as instances of {\it 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\ss{}-Jordan elimination; and iterative algorithms such as the {\it classical\/} Jacobi and Gau\ss{}-Seidel iteration. }
}
%%% 15:
@article{bryy-spps-90
, author = {Rainer E. Burkard and G{\"u}nter Rote and En-Yu Yao and Zhong-Liang Yu}
, title = {Shortest polygonal paths in space}
, journal = {Computing}
, year = {1990}
, volume = {45}
, pages = {51--68}
, 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 {\it open\/} case the path can have different start and end point, whereas in the {\it 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 {\it 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.}
}
%%% 16:
@article{crw-gc-91
, author = {Vasilis Capoyleas and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Geometric clusterings}
, journal = {Journal of Algorithms}
, year = {1991}
, volume = {12}
, pages = {341--356}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Geometric+clusterings.ps}
, doi = {10.1016/0196-6774(91)90007-L}
, 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.}
}
%%% 16a:
@inproceedings{crw-gcea-90
, author = {Vasilis Capoyleas and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Geometric clusterings (extended abstract)}
, year = {1990}
, pages = {28--31}
, booktitle = {Proceedings of the Second Canadian Conference on Computational Geometry, Ottawa}
, editor = {J. Urrutia}
}
%%% 17:
@article{bhr-saucf-91
, author = {Rainer E. Burkard and Horst W. Hamacher and G{\"u}nter Rote}
, title = {Sandwich approximation of univariate convex functions with an application to separable convex programming}
, journal = {Naval Research Logistics}
, year = {1991}
, volume = {38}
, pages = {911--924}
, doi = {10.1002/nav.3800380609}
}
%%% 18:
@inproceedings{hlr-frt-91
, author = {Paul Hilfinger and Eugene L. Lawler and G{\"u}nter Rote}
, title = {Flattening a rooted tree}
, year = {1991}
, pages = {335--340}
, booktitle = {Applied Geometry and Discrete Mathematics. The Victor Klee Festschrift}
, editor = {Peter Gritzmann and Bernd Sturmfels}
, publisher = {American Mathematical Society and Association for Computing Machinery}
, series = {DIMACS series in discrete mathematics and theoretical computer science}
}
%%% 19:
@article{r-cmhdb-91
, author = {G{\"u}nter Rote}
, title = {Computing the minimum {Hausdorff} distance between two point sets on a line under translation}
, journal = {Information Processing Letters}
, year = {1991}
, volume = {38}
, pages = {123--127}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Computing+the+minimum+Hausdorff+distance+between+two+point+sets+on+a+line+under+translation.ps}
, 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.}
}
%%% 20a:
@article{wrzw-cksck-91
, author = {Gerhard Woeginger and G{\"u}nter Rote and Binhai Zhu and Zhengyan Wang}
, title = {Counting $k$-subsets and convex $k$-gons in the plane}
, journal = {Information Processing Letters}
, year = {1991}
, volume = {38}
, pages = {149--151}
, doi = {10.1016/0020-0190(91)90237-C}
}
%%% 20b:
@article{rw-cckgp-92
, author = {G{\"u}nter Rote and Gerhard Woeginger}
, title = {Counting convex $k$-gons in planar point sets}
, journal = {Information Processing Letters}
, year = {1992}
, volume = {41}
, pages = {191--194}
, doi = {10.1016/0020-0190(92)90178-X}
}
%%% 20c:
@article{mrsw-ccppp-95
, author = {Joseph S. B. Mitchell and G{\"u}nter Rote and Gopalakrishnan Sundaram and Gerhard Woeginger}
, title = {Counting convex polygons in planar point sets}
, journal = {Information Processing Letters}
, year = {1995}
, volume = {56}
, pages = {45--49}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Counting+convex+polygons+in+planar+point+sets.ps}
, doi = {10.1016/0020-0190(95)00130-5}
}
%%% 21:
@article{irwy-spls-93
, author = {Christian Icking and G{\"u}nter Rote and Emo Welzl and Chee Yap}
, title = {Shortest paths for line segments}
, journal = {Algorithmica}
, year = {1993}
, volume = {10}
, pages = {182--200}
, 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.}
}
%%% 22:
@article{rv-hdtmt-93
, author = {G{\"u}nter Rote and Andreas Vogel}
, title = {A heuristic for decomposing traffic matrices in {TDMA} satellite communication}
, journal = {ZOR---Methods and Models of Operations Research}
, year = {1993}
, volume = {38}
, pages = {281--307}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/A+heuristic+for+decomposing+traffic+matrices+in+TDMA+satellite+communication.pdf}
, doi = {10.1007/BF01416610}
, abstract = {With the time-division multiple access (TDMA) technique in satellite communication the problem arises to decompose a given $n\times n$ traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large as $n^2$. When the number of matrices is restricted to $n$, the problem is 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 $n^2$ allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristics methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.}
}
%%% 22a:
@techreport{rv-hdtmt-90
, author = {G{\"u}nter Rote and Andreas Vogel}
, title = {A heuristic for decomposing traffic matrices in {TDMA} satellite communication}
, year = {1990}
, number = {Bericht 73}
, institution = {Technische Universit{\"a}t Graz}
, pages = {28 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/A+heuristic+for+decomposing+traffic+matrices+in+TDMA+satellite+communication.pdf}
}
%%% 22b:
@article{r-ehfem-89
, author = {G{\"u}nter Rote}
, title = {Eine Heuristik f{\"u}r ein Matrizenzerlegungsproblem, das in der Telekommunikation via Satelliten auf\-tritt (Kurz\-fassung)}
, journal = {ZAMM --- Zeitschrift f{\"u}r angewandte Mathematik und Mechanik}
, year = {1989}
, volume = {69}
, pages = {T29--T31}
, doi = {10.1002/zamm.19890690402}
}
%%% 23:
@inproceedings{fmrwy-sioas-90
, author = {Rudolf Fleischer and Kurt Mehlhorn and G{\"u}nter Rote and Emo Welzl and Chee Yap}
, title = {On simultaneous inner and outer approximation of shapes}
, year = {1990}
, pages = {216--224}
, booktitle = {Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/98524.98572}
}
%%% 23a:
@article{fmrwy-sioas-92
, author = {Rudolf Fleischer and Kurt Mehlhorn and G{\"u}nter Rote and Emo Welzl and Chee Yap}
, title = {Simultaneous inner and outer approximation of shapes}
, journal = {Algorithmica}
, year = {1992}
, volume = {8}
, pages = {365--389}
, doi = {10.1007/BF01758852}
, abstract = {For compact Euclidean bodies $P, Q$, we define $\lambda (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 $\lambda $ 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 \ge 3$, we study $\lambda (k)$, the minimum value such that for each convex polygon $P$ there exists a convex $k$-gon $Q$ with $\lambda (P, Q)\le \lambda (k)$. Among other results, we prove that $2.118\ldots \le \lambda (3) \le 2.25$ and $\lambda (k) = 1 + \Theta (1/k^2)$ We give an $O(n^2 \log ^2 n)$-time algorithm which, for any input convex $n$-gon $P$, finds a triangle $T$ that minimizes $\lambda (T, P)$ among triangles. However, in linear time we can find a triangle $T$ with $\lambda (T, P) \le 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.}
}
%%% 24:
@article{mrw-mlpop-92
, author = {Joseph S. B. Mitchell and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Minimum-link paths among obstacles in the plane}
, journal = {Algorithmica}
, year = {1992}
, volume = {8}
, pages = {431--459}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Minimum-link+paths+among+obstacles+in+the+plane.ps}
, doi = {10.1007/BF01758855}
, 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 \alpha (n) \log ^2 n)$ and space $O(E)$, where $n$ is the total number of edges of the obstacles, $E$ is the size of the visibility graph, and $\alpha (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$).}
}
%%% 24a:
@inproceedings{mrw-mlpop-90
, author = {Joseph S. B. Mitchell and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Minimum-link paths among obstacles in the plane (extended abstract)}
, year = {1990}
, pages = {63--72}
, booktitle = {Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/98524.98537}
}
%%% 25:
@article{r-crsaa-92
, author = {G{\"u}nter Rote}
, title = {The convergence rate of the {Sandwich} algorithm for approximating convex functions}
, journal = {Computing}
, year = {1992}
, volume = {48}
, pages = {337--361}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+convergence+rate+of+the+Sandwich+algorithm+for+approximating+convex+functions.ps}
, doi = {10.1007/BF02238642}
}
%%% 25a:
@inproceedings{r-crsaa-90
, author = {G{\"u}nter Rote}
, title = {The convergence rate of the {Sandwich} algorithm for approximating convex figures in the plane (extended abstract)}
, year = {1990}
, pages = {287--290}
, booktitle = {Proceedings of the Second Canadian Conference on Computational Geometry, Ottawa}
, editor = {J. Urrutia}
}
%%% 26:
@article{eorw-fmakg-92
, author = {David Eppstein and Mark Overmars and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Finding minimum area $k$-gons}
, journal = {Discrete and Computational Geometry}
, year = {1992}
, volume = {7}
, pages = {45--58}
, doi = {10.1007/BF02187823}
}
%%% 27:
@article{bfr-vrawa-95
, author = {Rainer E. Burkard and Bernd Fruhwirth and G{\"u}nter Rote}
, title = {Vehicle routing in an automated warehouse: analysis and optimization}
, journal = {Annals of Operations Research}
, year = {1995}
, volume = {57}
, pages = {29--44}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Vehicle+routing+in+an+automated+warehouse:+analysis+and+optimization.ps}
, 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.}
}
%%% 28:
@inproceedings{r-dchhd-92
, author = {G{\"u}nter Rote}
, title = {Degenerate convex hulls in high dimensions without extra storage (extended abstract)}
, year = {1992}
, pages = {26--32}
, booktitle = {Proceedings of the Eighth Annual Symposium on Computational Geometry, Berlin}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Degenerate+convex+hulls+in+high+dimensions+without+extra+storage.ps}
, doi = {10.1145/142675.142685}
}
%%% 29:
@inproceedings{r-nmbph-92
, author = {G{\"u}nter Rote}
, title = {A new metric between polygons, and how to compute it (extended abstract)}
, year = {1992}
, volume = {623}
, pages = {404--415}
, booktitle = {Automata, Languages and Programming. Proceedings of the 19th International Colloquium on Automata, Languages, and Programming (ICALP 92), Wien}
, editor = {W. Kuich}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/A+new+metric+between+polygons,+and+how+to+compute+it.ps}
, doi = {10.1007/3-540-55719-9_92}
}
%%% 30:
@article{r-ssc2-93
, author = {G{\"u}nter Rote}
, title = {Sequences with subword complexity $2n$}
, journal = {Journal of Number Theory}
, year = {1993}
, volume = {46}
, pages = {196--213}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Sequences+with+subword+complexity+2n.ps}
, doi = {10.1006/jnth.1994.1012}
}
%%% 31:
@article{ers-ufwsc-93
, author = {Alon Efrat and G{\"u}nter Rote and Micha Sharir}
, title = {On the union of fat wedges and separating a collection of segments by a line}
, journal = {Computational Geometry: Theory and Applications}
, year = {1993}
, volume = {3}
, pages = {277--288}
, doi = {10.1016/0925-7721(93)90018-2}
}
%%% 31a:
@inproceedings{ers-ufwsc-93p
, author = {Alon Efrat and G{\"u}nter Rote and Micha Sharir}
, title = {On the union of fat wedges and separating a collection of segments by a line}
, year = {1993}
, pages = {115--120}
, booktitle = {Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo}
, editor = {A. Lubiw and J. Urrutia}
}
%%% 32:
@inproceedings{rss-mawsp-93
, author = {G{\"u}nter Rote and Christian Schwarz and Jack Snoeyink}
, title = {Maintaining the approximate width of a set of points in the plane (extended abstract)}
, year = {1993}
, pages = {258--263}
, booktitle = {Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo}
, editor = {A. Lubiw and J. Urrutia}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Maintaining+the+approximate+width+of+a+set+of+points+in+the+plane.ps}
}
%%% 33:
@article{ddr-chlts-94
, author = {Vladimir G. Deineko and Ren{\'e} van Dal and G{\"u}nter Rote}
, title = {The convex-hull-and-line traveling salesman problem: A solvable case}
, journal = {Information Processing Letters}
, year = {1994}
, volume = {51}
, pages = {141--148}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+convex-hull-and-line+traveling+salesman+problem:+A+solvable+case.ps}
, doi = {10.1016/0020-0190(94)00071-9}
}
%%% 34:
@article{r-cic-94
, author = {G{\"u}nter Rote}
, title = {Curves with increasing chords}
, journal = {Mathematical Proceedings of the Cambridge Philosophical Society}
, year = {1994}
, volume = {115}
, pages = {1--12}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Curves+with+increasing+chords.ps}
, doi = {10.1017/S0305004100071875}
}
%%% 35:
@article{rt-sdapa-95
, author = {G{\"u}nter Rote and Robert Franz Tichy}
, title = {Spherical dispersion with an application to polygonal approximation of curves}
, journal = {Anzeiger der {\"{O}}sterreichischen Akademie der Wissenschaften, Mathematisch-naturwissenschaftliche Klasse, Abteilung II}
, year = {1995}
, volume = {132}
, pages = {3--10}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Spherical+dispersion+with+an+application+to+polygonal+approximation+of+curves.ps}
, abstract = {We describe and analyze a procedure for the polygonal approximation of spatial curves using ``well-distributed'' points on the sphere. Here the {\it dispersion\/} of the point set with respect to spherical slices (intersections of two half-spheres) plays a role.}
}
%%% 36:
@article{rt-qmcmd-96
, author = {G{\"u}nter Rote and Robert Franz Tichy}
, title = {{Quasi-Monte-Carlo} methods and the dispersion of point sequences}
, journal = {Mathematical and Computer Modelling}
, year = {1996}
, volume = {23}
, pages = {9--23}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Quasi-Monte-Carlo+methods+and+the+dispersion+of+point+sequences.ps}
, doi = {10.1016/0895-7177(96)00036-2}
, 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.}
}
%%% 37:
@inproceedings{hr-tcpp-93
, author = {Johannes Hagauer and G{\"u}nter Rote}
, title = {Three-clustering of points in the plane}
, year = {1993}
, volume = {726}
, pages = {192--199}
, booktitle = {Algorithms --- ESA '93. Proc. First Annual European Symposium on Algorithms, Bad Honnef, Germany}
, editor = {Thomas Lengauer}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-57273-2_55}
}
%%% 37a:
@article{hr-tcpp-97
, author = {Johannes Hagauer and G{\"u}nter Rote}
, title = {Three-clustering of points in the plane}
, journal = {Computational Geometry, Theory and Applications}
, year = {1997}
, volume = {8}
, pages = {87--95}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Three-clustering+of+points+in+the+plane.ps}
, doi = {10.1016/S0925-7721(96)00022-3}
}
%%% 38:
@article{ars-wigec-96
, author = {J{\'a}nos Acz{\'e}l and G{\"u}nter Rote and Jens Schwaiger}
, title = {Webs, iteration groups, and equivalent changes in probabilities}
, journal = {Quarterly of Applied Mathematics}
, year = {1996}
, volume = {54}
, pages = {475--499}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Webs,+iteration+groups,+and+equivalent+changes+in+probabilities.ps}
, 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.}
}
%%% 38a:
@inproceedings{ars-wigec-94
, author = {J{\'a}nos Acz{\'e}l and G{\"u}nter Rote and Jens Schwaiger}
, title = {Webs, iteration groups, and equivalent changes in probabilities}
, year = {1994}
, volume = {323}
, pages = {1--20}
, booktitle = {VIII. Mathematikertreffen Zagreb-Graz}
, editor = {Detlef Gronau and Ludwig Reich}
, series = {Grazer Mathematische Berichte}
}
%%% 38b:
@inproceedings{ars-ecpcm-94
, author = {J{\'a}nos Acz{\'e}l and G{\"u}nter Rote and Jens Schwaiger}
, title = {Equivalence of changes in proportions at crossroads of mathematical theories}
, year = {1994}
, pages = {569--570}
, booktitle = {Actes 5$^{\rm e}$ Conf\'{e}rence Internationale/Proc.\ Fifth International Conference IPMU, Traitement d'information et gestion d'incertitutes dans les syst{\`e}mes {\`a} base de connaissances/Information Processing and Management of Incertainty in Knowledge-Based Systems, Paris, 4--8 juillet/July, 1994, Cit\'{e} Internationale Universitaire}
}
%%% 38c:
@incollection{ars-ecpcm-97
, author = {J{\'a}nos Acz{\'e}l and G{\"u}nter Rote and Jens Schwaiger}
, title = {Equivalence of changes in proportions at crossroads of mathematical theories}
, year = {1997}
, pages = {36--38}
, booktitle = {The Ordered Weighted Averaging Operators---Theory and Applications}
, editor = {Ronald R. Yager and Janusz Kacprzyk}
, publisher = {Elsevier}
}
%%% 39:
@article{r-fsvtd-97
, author = {G{\"u}nter Rote}
, title = {Finding a shortest vector in a two-dimensional lattice modulo $m$}
, journal = {Theoretical Computer Science}
, year = {1997}
, volume = {172}
, pages = {303--308}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Finding+a+shortest+vector+in+a+two-dimensional+lattice+modulo+m.ps}
, doi = {10.1016/S0304-3975(96)00185-5}
}
%%% 40:
@inproceedings{aar-msrp-94
, author = {Helmut Alt and Oswin Aichholzer and G{\"u}nter Rote}
, title = {Matching shapes with a reference point}
, year = {1994}
, pages = {85--92}
, booktitle = {Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/177424.177555}
}
%%% 40a:
@article{aar-msrp-97
, author = {Oswin Aichholzer and Helmut Alt and G{\"u}nter Rote}
, title = {Matching shapes with a reference point}
, journal = {International Journal on Computational Geometry and Applications}
, year = {1997}
, volume = {7}
, pages = {349--363}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Matching+shapes+with+a+reference+point.ps}
, 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.}
}
%%% 41:
@article{bcrw-qapma-98
, author = {Rainer E. Burkard and Eranda {\c C}ela and G{\"u}nter Rote and Gerhard J. Woeginger}
, title = {The quadratic assignment problem with a monotone Anti-{Monge} and a symmetric {Toeplitz} matrix: Easy and hard cases}
, journal = {Mathematical Programming}
, year = {1998}
, volume = {82}
, pages = {125--158}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+quadratic+assignment+problem+with+a+monotone+Anti-Monge+and+a+symmetric+Toeplitz+matrix:+Easy+and+hard+cases.ps}
, 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: (P1) The ``Turbine Problem'', i. e., the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time.
We identify conditions on the Toeplitz matrix that lead to a simple solution for the 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.}
}
%%% 41a:
@inproceedings{bcrw-qapma-96
, author = {Rainer E. Burkard and Eranda {\c C}ela and G{\"u}nter Rote and Gerhard J. Woeginger}
, title = {The quadratic assignment problem with a monotone {Anti-Monge} and a symmetric {Toeplitz} matrix: Easy and hard cases}
, year = {1996}
, volume = {1084}
, pages = {204--218}
, booktitle = {Integer Programming and Combinatorial Optimization. Proceedings of the 5th International IPCO Conference, Vancouver, Canada}
, editor = {W. H. Cunningham and S. T. McCormick and M. Queyranne}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-61310-2_16}
}
%%% 42:
@article{gr-dpaco-98
, author = {Mordecai J. Golin and G{\"u}nter Rote}
, title = {A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs}
, journal = {IEEE Transactions on Information Theory}
, year = {1998}
, volume = {44}
, pages = {1770--1781}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.ps}
, doi = {10.1109/18.705558}
, 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(n^{C+2})$ time, if the costs of the letters are integers between 1 and $C$. While still leaving open the question of whether the general problem is solvable in polynomial time our algorithm seems to be the first one that runs in polynomial time for fixed letter costs.
Some numerical results are reported, including solutions using Karp's integer programming formulations, which was solved using AMPL and CPLEX. The AMPL model is included in the appendix and in the PostScript-file.}
}
%%% 42a:
@inproceedings{gr-dpaco-95
, author = {Mordecai J. Golin and G{\"u}nter Rote}
, title = {A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs}
, year = {1995}
, volume = {944}
, pages = {256--267}
, booktitle = {Automata, Languages and Programming. Proceedings of the 22nd International Colloquium on Automata, Languages, and Programming (ICALP 95), Szeged, Hungary}
, editor = {F. G{\'e}cseg}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-60084-1_79}
}
%%% 43:
@techreport{dra-sltgt-95
, author = {Robert L. Scot Drysdale and G{\"u}nter Rote and Oswin Aichholzer}
, title = {A simple linear time greedy triangulation algorithm for uniformly distributed points}
, year = {1995}
, month = feb
, number = {Bericht IIG-408}
, institution = {Technische Universit{\"a}t Graz, Institute f{"u}r Informationsverarbeitung}
, pages = {16 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/A+simple+linear+time+greedy+triangulation+algorithm+for+uniformly+distributed+points.ps}
}
%%% 44:
@article{aacktrx-tin-96
, author = {Oswin Aichholzer and Franz Aurenhammer and Siu-Wing Cheng and Naoki Katoh and Michael Taschwer and G{\"u}nter Rote and Yin-Feng Xu}
, title = {Triangulations intersect nicely}
, journal = {Discrete and Computational Geometry}
, year = {1996}
, volume = {16}
, pages = {339--359}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Triangulations+intersect+nicely.ps}
, doi = {10.1007/BF02712872}
}
%%% 44a:
@inproceedings{aart-tin-95
, author = {Oswin Aichholzer and Franz Aurenhammer and G{\"u}nter Rote and Michael Taschwer}
, title = {Triangulations intersect nicely}
, year = {1995}
, pages = {220--229}
, booktitle = {Proceedings of the Eleventh Annual Symposium on Computational Geometry, Vancouver}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/220279.220303}
}
%%% 45:
@article{ljrw-olqac-96
, author = {Marek Lassak and Janusz Januszewski and G{\"u}nter Rote and Gerhard Woeginger}
, title = {On-line $q$-adic covering by the method of the $n$-th segment and its application to on-line covering by cubes}
, journal = {Beitr{\"a}ge zur Algebra und Geometrie---Contributions to Algebra and Geometry}
, year = {1996}
, volume = {37}
, issue = {1}
, pages = {51--65}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On-line+q-adic+covering+by+the+method+of+the+n-th+segment+and+its+application+to+on-line+covering+by+cubes.ps}
}
%%% 45a:
@article{ljrw-sp74-96
, author = {Marek Lassak and Janusz Januszewski and G{\"u}nter Rote and Gerhard Woeginger}
, title = {Solution to problem 74}
, journal = {Mathematische Semesterberichte}
, year = {1996}
, volume = {43}
, pages = {94--100}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Solution+to+problem+74.ps}
}
%%% 46:
@inproceedings{afrw-mcsrs-96
, author = {Helmut Alt and Ulrich Fuchs and G{\"u}nter Rote and Gerald Weber}
, title = {Matching convex shapes with respect to the symmetric difference}
, year = {1996}
, volume = {1136}
, pages = {320--333}
, booktitle = {Algorithms --- ESA '96. Proc. Fourth Annual European Symposium on Algorithms, Barcelona}
, editor = {Josep D{\'\i{}}az and Mar{\'\i{}}a Serna}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-61680-2_65}
}
%%% 46a:
@article{afrw-mcsrs-98
, author = {Helmut Alt and Ulrich Fuchs and G{\"u}nter Rote and Gerald Weber}
, title = {Matching convex shapes with respect to the symmetric difference}
, journal = {Algorithmica}
, year = {1998}
, volume = {21}
, pages = {89--103}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Matching+convex+shapes+with+respect+to+the+symmetric+difference.ps}
, 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. }
}
%%% 47:
@techreport{rz-olejp-96
, author = {G{\"u}nter Rote and Guochuan Zhang}
, title = {Optimal logistics for expeditions---the jeep problem with complete refilling}
, year = {1996}
, month = jun
, number = {SFB-Bericht Nr.\ 71}
, institution = {Technische Universit{\"a}t Graz, Spezialforschungsbereich Optimierung und Kontrolle}
, pages = {34 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Optimal+logistics+for+expeditions+-+the+jeep+problem+with+complete+refilling.ps}
, 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.}
}
%%% 48:
@article{aarx-clgta-99
, author = {Oswin Aichholzer and Franz Aurenhammer and G{\"u}nter Rote and Yin-Feng Xu}
, title = {Constant-level greedy triangulations approximate the {MWT} well}
, journal = {Journal of Combinatorial Optimization}
, year = {1999}
, volume = {2}
, pages = {361--369}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Constant-level+greedy+triangulations+approximate+the+MWT+well.ps}
, doi = {10.1023/A:1009776619164}
, 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 {\it 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\cdot 2^{k+1}$ times the minimum-weight triangulation of the point set. }
}
%%% 48a:
@inproceedings{aarx-clgta-96
, author = {Oswin Aichholzer and Franz Aurenhammer and G{\"u}nter Rote and Yin-Feng Xu}
, title = {Constant-level greedy triangulations approximate the {MWT} well}
, year = {1996}
, volume = {2}
, pages = {309--318}
, booktitle = {Proceedings of the Second International Symposium on Operations Research and its Applications (ISORA'96)}
, editor = {Ding-Zhu Du and Xiang-Sun Zhang and Kan Cheng}
, publisher = {World Publishing Corporation}
, pubaddr = {Beijing}
, series = {Lecture Notes in Operations Research}
}
%%% 49:
@article{brsz-cltcc-00
, author = {Imre B{\'a}r{\'a}ny and G{\"u}nter Rote and William Steiger and Cun-Hui Zhang}
, title = {A central limit theorem for convex chains in the square}
, journal = {Discrete and Computational Geometry}
, year = {2000}
, volume = {23}
, pages = {35--50}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/A+central+limit+theorem+for+convex+chains+in+the+square.ps}
, doi = {10.1007/PL00009490}
}
%%% 50:
@article{befhlmrrswz-vrgtd-98
, author = {Prosenjit Bose and Hazel Everett and S{\'a}ndor Fekete and Michael E. Houle and Anna Lubiw and Henk Meijer and Kathleen Romanik and G{\"u}nter Rote and Tom Shermer and Sue Whitesides and Christian Zelle}
, title = {A visibility representation for graphs in three dimensions}
, journal = {Journal of Graph Algorithms and Applications}
, year = {1998}
, volume = {2}
, pages = {1--16}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/A+visibility+representation+for+graphs+in+three+dimensions.ps}
, 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^^c3^^b6s-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.}
}
%%% 51:
@inproceedings{gr-dsvgp-99
, author = {Jerrold R. Griggs and G{\"u}nter Rote}
, title = {On the distribution of sums of vectors in general position}
, year = {1999}
, pages = {139--142}
, booktitle = {Contemporary Trends in Discrete Mathematics}
, editor = {Ronald L. Graham and Jan Kratochv{\'\i{}}l and Jaroslav Ne{\v{s}}et{\v{r}}il and Fred S. Roberts}
, publisher = {American Mathematical Society}
, series = {DIMACS series in discrete mathematics and theoretical computer science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+the+distribution+of+sums+of+vectors+in+general+position.ps}
, 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 $R^h$ in general position. This note reviews past progress and motivation for this problem, and presents a construction that gives a respectable new lower bound, $\Omega (2^n n^{1-{3h/2}})$, which compares for $h\ge 2$ to the previously known upper bound $O(2^n n^{-1-{h/2}})$.}
}
%%% 52:
@inproceedings{aaiklr-gsac-98
, author = {Oswin Aichholzer and Franz Aurenhammer and Christian Icking and Rolf Klein and Elmar Langetepe and G{\"u}nter Rote}
, title = {Generalized self-approaching curves}
, year = {1998}
, volume = {1533}
, pages = {317--327}
, booktitle = {Algorithms and Computation---Ninth Annual International Symposium on Algorithms and Computation. Taejon, Korea}
, editor = {Kyung-Yong Chwa and Oscar H. Ibarra}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/3-540-49381-6_34}
}
%%% 52a:
@article{aaiklr-gsac-01
, author = {Oswin Aichholzer and Franz Aurenhammer and Christian Icking and Rolf Klein and Elmar Langetepe and G{\"u}nter Rote}
, title = {Generalized self-approaching curves}
, journal = {Discrete Applied Mathematics}
, year = {2001}
, volume = {109}
, pages = {3--24}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Generalized+self-approaching+curves.ps}
, doi = {10.1016/S0166-218X(00)00233-X}
, abstract = {For an angle $\phi $ between 0 and $180^\circ $, we consider the class of oriented curves which are $\phi $-{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 $\phi $ at $a$. This is a direct generalization of {self-approaching curves} which are $90^\circ $-{self-approaching}. We prove a tight upper bound on the length of a $\phi $-self-approaching curve in terms of the distance between its endpoints. The upper bound only depends on the angle $\phi $.
This problem arises in the performance analysis of certain on-line navigation strategies.}
}
%%% 53:
@article{rw-tclta-98
, author = {G{\"u}nter Rote and Gerhard J. Woeginger}
, title = {Time complexity and linear-time approximation of the ancient two machine flow shop}
, journal = {Journal of Scheduling}
, year = {1998}
, volume = {1}
, pages = {149--155}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Time+complexity+and+linear-time+approximation+of+the+ancient+two+machine+flow+shop.ps}
, doi = {10.1002/(SICI)1099-1425(1998100)1:3<149::AID-JOS10>3.0.CO;2-4}
}
%%% 54:
@article{gr-rfmp-99
, author = {Martin Gavalec and G{\"u}nter Rote}
, title = {Reachability of fuzzy matrix period}
, journal = {Tatra Mountains Mathematical Publications}
, year = {1999}
, volume = {16}
, pages = {61--79}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Reachability+of+fuzzy+matrix+period.ps}
, abstract = {Given an $n\times n$ matrix $A$, the problem is to decide whether there is an $n$-vector $x$ such that the sequence of matrix powers $A, A^2, A^3, \ldots $ has the same period length as the sequence $Ax, A^2x, A^3x, \ldots $ of iterates of $x$. In these 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(n^2)$ time. If only one of the conditions is satisfied, the problem remains NP-complete.}
}
%%% 55:
@article{bdlr-ocpt-01
, author = {Rainer E. Burkard and Helidon Dollani and Yixun Lin and G{\"u}nter Rote}
, title = {The obnoxious center problem on a tree}
, journal = {SIAM Journal on Discrete Mathematics}
, year = {2001}
, volume = {14}
, pages = {498--509}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+obnoxious+center+problem+on+a+tree.ps}
, 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.}
}
%%% 56:
@article{fkr-ubmnf-00
, author = {Tam{\'a}s Fleiner and Volker Kaibel and G{\"u}nter Rote}
, title = {Upper bounds on the maximal number of facets of 0/1-polytopes}
, journal = {European Journal of Combinatorics}
, year = {2000}
, volume = {21}
, pages = {121--130}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Upper+bounds+on+the+maximal+number+of+facets+of+0-1-polytopes.ps}
, 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\"unter 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\'ar\'any. The known lower bounds are exponential, the current record being $3.6^d$ for large enough $d$. (Thomas Christof and Gerhard Reinelt 1997). They follow from explicit polytopes in low dimensions. (Since the paper was published, superexponential lower bounds were proved by B\'ar\'any 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$.}
}
%%% 57:
@article{rw-mntjs-98
, author = {G{\"u}nter Rote and Gerhard J. Woeginger}
, title = {Minimizing the number of tardy jobs on a single machine with batch setup times}
, journal = {Acta Cybernetica}
, year = {1998}
, volume = {13}
, pages = {423--429}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Minimizing+the+number+of+tardy+jobs+on+a+single+machine+with+batch+setup+times.ps}
}
%%% 58:
@inproceedings{r-dfadp-01
, author = {G{\"u}nter Rote}
, title = {Division-free algorithms for the determinant and the {Pfaffian:} algebraic and combinatorial approaches}
, year = {2001}
, volume = {2122}
, pages = {119--135}
, booktitle = {Computational Discrete Mathematics}
, editor = {Helmut Alt}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Division-free+algorithms+for+the+determinant+and+the+Pfaffian:+algebraic+and+combinatorial+approaches.ps}
, doi = {10.1007/3-540-45506-X_9}
}
%%% 59:
@inproceedings{cdr-epcbu-00
, author = {Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}
, title = {Every polygon can be untangled}
, year = {2000}
, pages = {62--65}
, booktitle = {Proceedings of the 16th European Workshop on Computational Geometry}
, pubaddr = {Ben-Gurion University of the Negev, Israel}
}
%%% {59}a:
@inproceedings{cdr-spacp-00
, author = {Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}
, title = {Straightening polygonal arcs and convexifying polygonal cycles}
, year = {2000}
, pages = {432--442}
, booktitle = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, California}
, publisher = {IEEE Computer Society Press}
, doi = {10.1109/SFCS.2000.892131}
}
%%% 59b:
@article{cdr-spacp-03
, author = {Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}
, title = {Straightening polygonal arcs and convexifying polygonal cycles}
, journal = {Discrete and Computational Geometry}
, year = {2003}
, volume = {30}
, pages = {205--239}
, doi = {10.1007/s00454-003-0006-7}
}
%%% 59c:
@techreport{cdr-spacp-02
, author = {Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}
, title = {Straightening polygonal arcs and convexifying polygonal cycles}
, year = {2002}
, month = feb
, number = {Bericht B 02-02}
, institution = {Freie Universit{\"a}t Berlin, Institut f\"ur Informatik}
, pages = {49 pages}
, url = {http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001941}
}
%%% 60:
@inproceedings{er-frtqf-01
, author = {Friedrich Eisenbrand and G{\"u}nter Rote}
, title = {Fast reduction of ternary quadratic forms}
, year = {2001}
, volume = {2146}
, pages = {32--44}
, booktitle = {Cryptography and Lattices---International Conference, CaLC 2001}
, editor = {Joseph H. Silverman}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Fast+reduction+of+ternary+quadratic+forms.ps}
, 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) \log ^2 s)$ 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)\log ^{d-1} s)$ bit-operations. }
}
%%% 61:
@inproceedings{er-f2vip-01
, author = {Friedrich Eisenbrand and G{\"u}nter Rote}
, title = {Fast 2-variable integer programming}
, year = {2001}
, volume = {2081}
, pages = {78--89}
, booktitle = {IPCO 2001---Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, Utrecht}
, editor = {K. Aardal and B. Gerards}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Fast+2-variable+integer+programming.ps}
, 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 + s\log m)$ arithmetic operations or with $O(m + \log m \log s) 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. }
}
%%% 62:
@article{brs-teapf-01
, author = {Peter Bra{\ss{}} and G{\"u}nter Rote and Konrad J. Swanepoel}
, title = {Triangles of extremal area or perimeter in a finite planar point set}
, journal = {Discrete and Computational Geometry}
, year = {2001}
, volume = {26}
, pages = {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\H os 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 $\Theta (n^2)$.}
}
%%% 63:
@inproceedings{rrss-ctptw-01
, author = {Dana Randall and G{\"u}nter Rote and Francisco Santos and Jack Snoeyink}
, title = {Counting triangulations and pseudo-triangulations of wheels}
, year = {2001}
, pages = {149--152}
, booktitle = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), Waterloo}
, editor = {T. Biedl}
, url = {http://www.cccg.ca/proceedings/2001/snoeyink-77218.ps.gz}
}
%%% 64:
@incollection{rss-emppp-03
, author = {G{\"u}nter Rote and Francisco Santos and Ileana Streinu}
, title = {Expansive motions and the polytope of pointed pseudo-triangulations}
, year = {2003}
, volume = {25}
, pages = {699--736}
, booktitle = {Discrete and Computational Geometry---The Goodman-Pollack Festschrift}
, editor = {Boris Aronov and Saugata Basu and J\'anos Pach and Micha Sharir}
, publisher = {Springer Verlag}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Expansive+motions+and+the+polytope+of+pointed+pseudo-triangulations.ps}
, eprint = {math/0206027}
, doi = {10.1007/978-3-642-55566-4_33}
, 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). }
}
%%% 65:
@inproceedings{cdr-ilstl-02
, author = {Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}
, title = {Infinitesimally locked self-touching linkages with applications to locked trees}
, year = {2002}
, volume = {304}
, pages = {287--311}
, booktitle = {Physical Knots: Knotting, Linking, and Folding Geometric Objects in $\mathbb {R}^3$.}
, editor = {Jorge Alberto Calvo and Kenneth C. Millett and Eric J. Rawdon}
, publisher = {American Mathematical Society}
, series = {Contemporary Mathematics}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Infinitesimally+locked+self-touching+linkages+with+applications+to+locked+trees.ps}
}
%%% 66:
@article{r-bthgn-97
, author = {G{\"u}nter Rote}
, title = {Binary trees having a given number of nodes with 0, 1, and 2 children}
, journal = {S\'eminaire Lotharingien de Combinatoire}
, year = {1997}
, volume = {B38b}
, pages = {6 pages}
, url = {http://www.emis.de/journals/SLC/wpapers/s38proding.html}
, 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.}
}
%%% 67:
@inproceedings{emrs-todm-02
, author = {Robert Els{\"a}sser and Burkhard Monien and G{\"u}nter Rote and Stefan Schamberger}
, title = {Toward optimal diffusion matrices}
, year = {2002}
, pages = {0067b, 8 pages}
, booktitle = {International Parallel and Distributed Processing Symposium. IPDPS 2002, Proceedings.}
, publisher = {IEEE Computer Society Press}
, url = {http://www.brics.dk/~alcomft/TR/ALCOMFT-TR-02-98.ps}
, doi = {10.1109/IPDPS.2002.1015569}
}
%%% 67a:
@techreport{emrs-todm-02t
, author = {Robert Els{\"a}sser and Burkhard Monien and G{\"u}nter Rote and Stefan Schamberger}
, title = {Toward optimal diffusion matrices}
, year = {2002}
, month = may
, number = {Technical report ALCOMFT-TR-02-98}
, institution = {Universit{\"at} Paderborn}
, pages = {8 pages}
, url = {http://www.brics.dk/~alcomft/TR/ALCOMFT-TR-02-98.ps}
}
%%% 68:
@inproceedings{ehkkrw-cse-02
, author = {Alon Efrat and Frank Hoffmann and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote and Carola Wenk}
, title = {Covering shapes by ellipses}
, year = {2002}
, pages = {453--454}
, booktitle = {Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco}
, publisher = {SIAM}
, doi = {10.1145/545381.545441}
}
%%% 68a:
@article{ehkkrw-ce-03
, author = {Alon Efrat and Frank Hoffmann and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote and Carola Wenk}
, title = {Covering with ellipses}
, journal = {Algorithmica}
, year = {2003}
, volume = {38}
, pages = {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.}
}
%%% 69:
@inproceedings{r-pphel-02
, author = {G{\"u}nter Rote}
, title = {Pseudotriangulations, polytopes, and how to expand linkages (invited talk)}
, year = {2002}
, pages = {133--134}
, booktitle = {Proceedings of the Eighteenth Annual Symposium on Computational Geometry, Barcelona}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/513400.513442}
, abstract = {This is an abstract of an invited talk in which I have surveyed some recent results about unfolding of linkages and connections to pseudotriangulations.}
}
%%% 70:
@inproceedings{rwwx-cmp-03
, author = {G{\"u}nter Rote and Cao An Wang and Lusheng Wang and Yinfeng Xu}
, title = {On constrained minimum pseudotriangulations}
, year = {2003}
, volume = {2697}
, pages = {445--454}
, booktitle = {Computing and Combinatorics. Proceedings of the 9th Annual International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, USA, July 2003}
, editor = {Tandy Warnow and Binhai Zhu}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+constrained+minimum+pseudotriangulations.ps}
, doi = {10.1007/3-540-45071-8_45}
, 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. }
}
%%% 71:
@inproceedings{aerw-mpm-03p
, author = {Helmut Alt and Alon Efrat and G{\"u}nter Rote and Carola Wenk}
, title = {Matching planar maps}
, year = {2003}
, pages = {589--598}
, booktitle = {Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore}
, publisher = {SIAM}
}
%%% 71a:
@article{aerw-mpm-03j
, author = {Helmut Alt and Alon Efrat and G{\"u}nter Rote and Carola Wenk}
, title = {Matching planar maps}
, journal = {Journal of Algorithms}
, year = {2003}
, volume = {49}
, pages = {262--283}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Matching+planar+maps.ps}
, doi = {10.1016/S0196-6774(03)00085-3}
, abstract = {We generalize the notion of the Fr\'echet distance from two curves to a curve and a graph and to two graphs, and we give efficient algorithms for computing the Fr\'echet distance in these cases.}
}
%%% 71b:
@inproceedings{waepr-fcmv-03
, author = {Carola Wenk and Helmut Alt and Alon Efrat and Lingeshwaran Palaniappan and G{\"u}nter Rote}
, title = {Finding a curve in a map (Video)}
, year = {2003}
, pages = {384--385}
, booktitle = {Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/777792.777855}
}
%%% 72:
@inproceedings{r-peitl-03
, author = {G{\"u}nter Rote}
, title = {Pursuit-evasion with imprecise target location}
, year = {2003}
, pages = {747--753}
, booktitle = {Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore}
, publisher = {SIAM}
, url = {http://dl.acm.org/citation.cfm?id=644108.644231}
}
%%% 73:
@article{r-cbn-02
, author = {G{\"u}nter Rote}
, title = {Crossing the bridge at night}
, journal = {EATCS Bulletin}
, year = {2002}
, month = oct
, volume = {78}
, pages = {241--246}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Crossing+the+bridge+at+night.ps}
, 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. }
}
%%% 74:
@inproceedings{acr-iccb-03
, author = {Nina Amenta and Sunghee Choi and G{\"u}nter Rote}
, title = {Incremental constructions con {BRIO}}
, year = {2003}
, pages = {211--219}
, booktitle = {Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Incremental+constructions+con+BRIO.ps}
, 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 {\it 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. }
}
%%% 75:
@inproceedings{akrw-cu-03
, author = {Helmut Alt and Christian Knauer and G{\"u}nter Rote and Sue Whitesides}
, title = {The complexity of (un)folding}
, year = {2003}
, pages = {164--170}
, booktitle = {Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+the+complexity+of+the+linkage+reconfiguration+problem.ps}
, doi = {10.1145/777792.777818}
}
%%% 75a:
@incollection{akrw-clrp-04
, author = {Helmut Alt and Christian Knauer and G{\"u}nter Rote and Sue Whitesides}
, title = {On the complexity of the linkage reconfiguration problem}
, year = {2004}
, volume = {342}
, pages = {1--13}
, booktitle = {Towards a Theory of Geometric Graphs}
, editor = {J{\'a}nos Pach}
, publisher = {American Mathematical Society}
, series = {Contemporary Mathematics}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+the+complexity+of+the+linkage+reconfiguration+problem.ps}
, 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.}
}
%%% 76:
@inproceedings{horsssssw-pmrgp-03
, author = {Ruth Haas and David Orden and G{\"u}nter Rote and Francisco Santos and Brigitte Servatius and Herman Servatius and Diane Souvaine and Ileana Streinu and Walter Whiteley}
, title = {Planar minimally rigid graphs and pseudo-triangulations}
, year = {2003}
, pages = {154--163}
, booktitle = {Proceedings of the Nineteenth Annual Symposium on Computational Geometry, San Diego}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/777792.777817}
}
%%% 76a:
@article{horsssssw-pmrgp-05
, author = {Ruth Haas and David Orden and G{\"u}nter Rote and Francisco Santos and Brigitte Servatius and Herman Servatius and Diane Souvaine and Ileana Streinu and Walter Whiteley}
, title = {Planar minimally rigid graphs and pseudo-triangulations}
, journal = {Computational Geometry, Theory and Applications}
, year = {2005}
, volume = {31}
, pages = {31--61}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Planar+minimally+rigid+graphs+and+pseudo-triangulations.pdf}
, eprint = {math/0307347}
, doi = {10.1016/j.comgeo.2004.07.003}
, abstract = {Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with {\it 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 {\it 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.}
}
%%% 77:
@article{orsssw-ncfnc-04
, author = {David Orden and G{\"u}nter Rote and Francisco Santos and Brigitte Servatius and Herman Servatius and Walter Whiteley}
, title = {Non-crossing frameworks with non-crossing reciprocals}
, journal = {Discrete and Computational Geometry}
, year = {2004}
, volume = {32}
, pages = {567--600}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Non-crossing+frameworks+with+non-crossing+reciprocals.ps}
, eprint = {math/0309156}
, doi = {10.1007/s00454-004-1139-x}
, 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.}
}
%%% 78:
@inproceedings{arss-zppt-03
, author = {Oswin Aichholzer and G{\"u}nter Rote and Bettina Speckmann and Ileana Streinu}
, title = {The zigzag path of a pseudo-triangulation}
, year = {2003}
, volume = {2748}
, pages = {377--388}
, booktitle = {Algorithms and Data Structures. Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS 2003), Ottawa, July 2003}
, editor = {Frank Dehne and J\"org-R\"udiger Sack and Michiel Smid}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+zigzag+path+of+a+pseudo-triangulation.ps}
, 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(n^2)$ time per path and $O(n^2)$ space.}
}
%%% 79:
@article{cllr-soosc-05
, author = {Yi-Jen Chiang and Tobias Lenz and Xiang Lu and G{\"u}nter Rote}
, title = {Simple and optimal output-sensitive construction of contour trees using monotone paths}
, journal = {Computational Geometry, Theory and Applications}
, year = {2005}
, volume = {30}
, pages = {165--195}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Simple+and+optimal+output-sensitive+construction+of+contour+trees+using+monotone+paths.ps}
, 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.}
}
%%% 80:
@inproceedings{r-cfdbp-04
, author = {G{\"u}nter Rote}
, title = {Computing the {Fr\'echet} distance between piecewise smooth curves}
, year = {2004}
, pages = {147--150}
, booktitle = {Abstracts of the 20th European Workshop on Computational Geometry}
}
%%% 80a:
@article{r-cfdbp-07
, author = {G{\"u}nter Rote}
, title = {Computing the {Fr\'echet} distance between piecewise smooth curves}
, journal = {Computational Geometry, Theory and Applications}
, year = {2007}
, volume = {37}
, pages = {162--174}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Computing+the+Frechet+distance+between+piecewise+smooth+curves.ps}
, doi = {10.1016/j.comgeo.2005.01.004}
, abstract = {We consider the Fr\'echet 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\'echet distance in $O(mn \log (mn))$ time. The decision version of the problem can be solved in $O(mn)$ time.}
}
%%% 81:
@inproceedings{cdr-pegse-04
, author = {Sergio Cabello and Erik D. Demaine and G{\"u}nter Rote}
, title = {Planar embeddings of graphs with specified edge lengths}
, year = {2004}
, volume = {2912}
, pages = {283--294}
, booktitle = {Graph Drawing. GD 2003, Proceedings of the 11th International Symposium on Graph Drawing, Perugia, September 2003, Revised Papers}
, editor = {Giuseppe Liotta}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/978-3-540-24595-7_26}
}
%%% 81a:
@article{cdr-pegse-07
, author = {Sergio Cabello and Erik D. Demaine and G{\"u}nter Rote}
, title = {Planar embeddings of graphs with specified edge lengths}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2007}
, volume = {11}
, pages = {259--276}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Planar+embeddings+of+graphs+with+specified+edge+lengths.pdf}
, 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. }
}
%%% 82:
@inproceedings{dr-fdsc-04
, author = {Adrian Dumitrescu and G{\"u}nter Rote}
, title = {On the {Fr\'echet} distance of a set of curves}
, year = {2004}
, pages = {162--165}
, booktitle = {Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), Montreal}
, url = {http://www.cccg.ca/proceedings/2004/39.pdf}
, abstract = {The Fr\'echet 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\'echet distance can be bounded in terms of pairwise Fr\'echet distances, and we provide an example which shows the tightness of this bound.}
}
%%% 83:
@proceedings{mrk-p21as-05
, title = {Proceedings of the Twenty-First Annual Symposium on Computational Geometry ({SCG'05})}
, year = {2005}
, pages = {x+387 pages}
, editor = {Joe S. B. Mitchell and G{\"u}nter Rote and Lutz Kettner}
, publisher = {Association for Computing Machinery}
}
%%% 84:
@inproceedings{dgr-ilbgd-05
, author = {Adrian Dumitrescu and Ansgar Gr\"une and G{\"u}nter Rote}
, title = {Improved lower bound on the geometric dilation of point sets}
, year = {2005}
, pages = {37--40}
, booktitle = {Abstracts of the 21st European Workshop on Computational Geometry}
}
%%% 84a:
@inproceedings{degkr-gdhc-05
, author = {Adrian Dumitrescu and Annette Ebbers-Baumann and Ansgar Gr\"une and Rolf Klein and G{\"u}nter Rote}
, title = {On geometric dilation and halving chords}
, year = {2005}
, volume = {3608}
, pages = {244--255}
, booktitle = {Proceedings of the Workshop on Algorithms and Data Structures (WADS 2005)}
, editor = {Alexandro L\'opez-Ortiz and Frank Dehne and J\"org-R\"udiger Sack}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/On+geometric+dilation+and+halving+chords.pdf}
, doi = {10.1007/11534273_22}
}
%%% 84b:
@article{degkr-gdccg-06
, author = {Adrian Dumitrescu and Annette Ebbers-Baumann and Ansgar Gr\"une and Rolf Klein and G{\"u}nter Rote}
, title = {On the geometric dilation of closed curves, graphs, and point sets}
, journal = {Computational Geometry, Theory and Applications}
, year = {2006}
, volume = {36}
, pages = {16--38}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+the+geometric+dilation+of+closed+curves,+graphs,+and+point+sets.ps}
, eprint = {math/0407135}
, doi = {10.1016/j.comgeo.2005.07.004}
, 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{\"u}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 $\ge \pi /2 = 1.57\ldots $. We prove a stronger lower bound of $1.00000000001*\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.}
}
%%% 85:
@inproceedings{r-scdpg-05
, author = {G{\"u}nter Rote}
, title = {Strictly convex drawings of planar graphs}
, year = {2005}
, pages = {728--734}
, booktitle = {Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver}
, publisher = {SIAM}
, abstract = {Every three-connected planar graph with $n$ vertices has a drawing on an $O(n^{7/3})\times O(n^{7/3})$ grid in which all faces are strictly convex polygons. More generally, there is a drawing on an $O(n^2s^2) \times O(n^{5/2}/s)$ grid, for any choice of a parameter $1\le s \le \root 6 \of n$, as well as on an $O(n) \times O(n^3)$ grid. These drawings are obtained by perturbing (not strictly) convex drawings, which are known to exist on $O(n)\times O(n)$ grids. The analysis of the perturbation leads to a number-theoretic question from the geometry of numbers whose solution would yield grid drawings on an $O(n^2)\times O(n^2)$ grid.}
}
%%% 86:
@article{br-scdpg-06
, author = {Imre B{\'a}r{\'a}ny and G{\"u}nter Rote}
, title = {Strictly convex drawings of planar graphs}
, journal = {Documenta Mathematica}
, year = {2006}
, volume = {11}
, pages = {369--391}
, url = {http://www.mathematik.uni-bielefeld.de/documenta/vol-11/13.pdf}
, abstract = {Every three-connected planar graph with $n$ vertices has a drawing on an $O(n^2) \times O(n^2)$ grid in which all faces are strictly convex polygons. More generally, there is a drawing on an $O(nw) \times O(n^3/w)$ grid, for any choice of a parameter $w$ in the range $1\le w \le n$. These drawings are obtained by perturbing (not strictly) convex drawings on $O(n) \times 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.}
}
%%% 87:
@article{rs-takp-06
, author = {G{\"u}nter Rote and Andr\'e Schulz}
, title = {Threshold arrangements and the knapsack problem}
, journal = {Applied Mathematics Letters}
, year = {2006}
, volume = {19}
, pages = {108--112}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Threshold+arrangements+and+the+knapsack+problem.ps}
, 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.}
}
%%% 88:
@article{bmrr-cptc-05
, author = {Gill Barequet and Micha Moffie and Ares Rib\'o and G{\"u}nter Rote}
, title = {Counting polyominoes on twisted cylinders}
, journal = {Discrete Mathematics and Theoretical Computer Science}
, year = {2005}
, volume = {AE}
, pages = {369--374}
}
%%% 88a:
@article{bmrr-cptc-06
, author = {Gill Barequet and Micha Moffie and Ares Rib\'o and G{\"u}nter Rote}
, title = {Counting polyominoes on twisted cylinders}
, journal = {INTEGERS: The Electronic Journal of Combinatorial Number Theory}
, year = {2006}
, month = sep
, volume = {6}
, number = {\#A22}
, pages = {37 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Counting+polyominoes+on+twisted+cylinders.ps}
, doi = {10.5281/zenodo.8275374}
, 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. }
}
%%% 89:
@inproceedings{cddflmrr-lucps-06
, author = {Robert Connelly and Erik D. Demaine and Martin L. Demaine and S\'andor P. Fekete and Stefan Langerman and Joseph S. B. Mitchell and Ares Rib\'o and G{\"u}nter Rote}
, title = {Locked and unlocked chains of planar shapes}
, year = {2006}
, pages = {61--70}
, booktitle = {Proceedings of the 22nd Annual Symposium on Computational Geometry, Sedona}
, publisher = {Association for Computing Machinery}
, eprint = {cs/0604022v2}
, doi = {10.1145/1137856.1137868}
}
%%% 89a:
@article{cddflmrr-lucps-10
, author = {Robert Connelly and Erik D. Demaine and Martin L. Demaine and S\'andor P. Fekete and Stefan Langerman and Joseph S. B. Mitchell and Ares Rib\'o and G{\"u}nter Rote}
, title = {Locked and unlocked chains of planar shapes}
, journal = {Discrete and Computational Geometry}
, year = {2010}
, volume = {44}
, pages = {439--462}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Locked+and+unlocked+chains+of+planar+shapes.pdf}
, eprint = {cs/0604022}
, doi = {10.1007/s00454-010-9262-3}
, 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.}
}
%%% 90:
@inproceedings{rs-pdpts-05
, author = {G{\"u}nter Rote and Andr\'e Schulz}
, title = {A pointed {Delaunay} pseudo-triangulation of a simple polygon}
, year = {2005}
, pages = {77--80}
, booktitle = {Abstracts of the 21st European Workshop on Computational Geometry}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/A+pointed+Delaunay+pseudo-triangulation+of+a+simple+polygon.pdf}
}
%%% 91:
@inproceedings{cgkr-mpsre-05w
, author = {Sergio Cabello and Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote}
, title = {Matching point sets with respect to the earth mover's distance}
, year = {2005}
, pages = {57--60}
, booktitle = {Abstracts of the 21st European Workshop on Computational Geometry}
}
%%% 91a:
@inproceedings{cgkr-mpsre-05
, author = {Sergio Cabello and Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote}
, title = {Matching point sets with respect to the earth mover's distance}
, year = {2005}
, volume = {3669}
, pages = {520--531}
, booktitle = {Algorithms --- ESA 2005. Proc. Thirteenth Annual European Symposium on Algorithms, Palma de Mallorca}
, editor = {Gerth St\o lting Brodal and Stefano Leonardi}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/11561071_47}
}
%%% 91b:
@article{cgkr-mpsre-08
, author = {Sergio Cabello and Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote}
, title = {Matching point sets with respect to the {Earth Mover's Distance}}
, journal = {Computational Geometry, Theory and Applications}
, year = {2008}
, volume = {39}
, pages = {118--133}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Matching+point+sets+with+respect+to+the+earth+movers+distance.pdf}
, 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 + \varepsilon )$-approximation algorithms for the minimum Euclidean EMD between $A$ and $B$ under translations and rigid motions.}
}
%%% 92:
@article{rry-ubnst-09
, author = {Ares {Rib\'o Mor} and G{\"u}nter Rote and Xuerong Yong}
, title = {Upper bounds for the number of spanning trees of a planar graph}
, year = {2009}
, month = mar
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+number+of+spanning+trees+in+a+planar+graph.ps}
, note = {in preparation}
}
%%% 92a:
@inproceedings{r-nstpg-05
, author = {G{\"u}nter Rote}
, title = {The number of spanning trees in a planar graph}
, year = {2005}
, volume = {2}
, pages = {969--973}
, booktitle = {Oberwolfach Reports}
, publisher = {European Mathematical Society - Publishing House}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/The+number+of+spanning+trees+in+a+planar+graph.ps}
, doi = {10.4171/OWR/2005/17}
, abstract = {A planar graph with $n$ vertices has at most $5.333\ldots ^n$ spanning trees. If it has no triangle, it has at most $3.53^n$ spanning trees. If it ha no face cycle of length three or four it has at most $2.848^n$ spanning trees. These bounds are obtained with a probabilistic method. They are motivated by to the construction of 3-dimensional polytopes with a given combinatorial structure and with small integral vertex coordinates.}
}
%%% 93:
@article{rr-lbmns-09
, author = {Ares {Rib\'o Mor} and G{\"u}nter Rote}
, title = {Lower bounds for the maximum number of spanning trees of a planar graph}
, year = {2009}
, month = mar
, note = {in preparation}
, abstract = {A planar graph with $n$ vertices can have as many as $5.029\ldots ^n$ spanning trees. If it has no triangle, it can still have $3.209^n$ spanning trees. If it has no triangle and quadrilateral face it can have as many as $2.561^n$ spanning trees. To get these bounds, we use the transfer matrix method and prove that periodic graphs with wrap-around edges, which can be embedded on a torus, have the same exponential growth rate as the corresponding planar graphs without wrap-around edges.}
}
%%% 94:
@techreport{mr-mwtnh-08t
, author = {Wolfgang Mulzer and G{\"u}nter Rote}
, title = {Minimum-weight triangulation is {NP}-hard}
, year = {2008}
, month = feb
, number = {Technical report B-05-23-revised}
, institution = {Freie Universit{\"a}t Berlin, Institut f\"ur Informatik}
, pages = {45 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Minimum-weight+triangulation+is+NP-hard.ps}
, eprint = {cs/0601002}
}
%%% 94a:
@inproceedings{mr-mwtnh-06
, author = {Wolfgang Mulzer and G{\"u}nter Rote}
, title = {Minimum-weight triangulation is {NP}-hard}
, year = {2006}
, pages = {1--10}
, booktitle = {Proceedings of the 22nd Annual Symposium on Computational Geometry, Sedona}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/1137856.1137859}
}
%%% 94b:
@article{mr-mwtnh-08
, author = {Wolfgang Mulzer and G{\"u}nter Rote}
, title = {Minimum-weight triangulation is {NP}-hard}
, journal = {Journal of the ACM}
, year = {2008}
, month = may
, volume = {55}
, issue = {2}
, pages = {Article 11, 29 pp.}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Minimum-weight+triangulation+is+NP-hard.ps}
, 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 {\it 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 $\beta $-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation. }
}
%%% 95:
@inproceedings{abkr-aod-06
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G{\"u}nter Rote}
, title = {Acyclic orientation of drawings}
, year = {2006}
, volume = {4059}
, pages = {266--277}
, booktitle = {Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT)}
, editor = {Lars Arge and Rusins Freivalds}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/11785293_26}
}
%%% 95a:
@inproceedings{abkr-aod-06w
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G{\"u}nter Rote}
, title = {Acyclic orientation of drawings}
, year = {2006}
, pages = {207--210}
, booktitle = {Abstracts of the 22nd European Workshop on Computational Geometry}
}
%%% 95b:
@article{abkr-aod-10
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G{\"u}nter Rote}
, title = {Acyclic orientation of drawings}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2010}
, volume = {14}
, pages = {367--384}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Acyclic+orientation+of+drawings.pdf}
, 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.}
}
%%% 96:
@inproceedings{r-plmt-06
, author = {G{\"u}nter Rote}
, title = {Piecewise linear {Morse} theory}
, year = {2006}
, volume = {3}
, pages = {696--698}
, booktitle = {Oberwolfach Reports}
, publisher = {European Mathematical Society - Publishing House}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Piecewise+linear+Morse+theory.ps}
, doi = {10.4171/OWR/2006/12}
, abstract = {Classical Morse theory considers the topological changes of the level sets $M_{h} = \{\,x\in M\mid f(x)=h\,\}$ of a smooth function $f$ defined on a manifold $M$ as the height $h$ varies. At {\it 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 {\it piecewise linear\/} functions in up to three variables: between critical values, all level sets are isotopic.}
}
%%% 97:
@inproceedings{dkkr-bbopc-06w
, author = {Darko Dimitrov and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote}
, title = {On the bounding boxes obtained by principal component analysis}
, year = {2006}
, pages = {193--196}
, booktitle = {Abstracts of the 22nd European Workshop on Computational Geometry}
, abstract = {Principle component analysis (PCA) is a commonly used to compute a bounding box of a point set in $\mathbb {R}^d$. In this paper we give bounds on the approximation factor of PCA bounding boxes of convex polygons in $\mathbb {R}^2$ (lower and upper bounds) and convex polyhedra in $\mathbb {R}^3$ (lower bound).}
}
%%% 97a:
@inproceedings{dkkr-ulbqp-07
, author = {Darko Dimitrov and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote}
, title = {Upper and lower bounds on the quality of the {PCA} bounding boxes}
, year = {2007}
, pages = {185--192}
, booktitle = {WSCG'2007, Prof. 15th Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision}
, editor = {Jarek Rossignac and Vaclav Skala}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Upper+and+lower+bounds+on+the+quality+of+the+PCA+bounding+boxes.pdf}
, abstract = {Principal component analysis (PCA) is commonly used to compute a bounding box of a point set in $\mathbb {R}^d$. 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 $\mathbb {R}^2$.}
}
%%% 98:
@inproceedings{cr-ocg-07
, author = {Sergio Cabello and G{\"u}nter Rote}
, title = {Obnoxious centers in graphs}
, year = {2007}
, pages = {98--107}
, booktitle = {Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans}
, publisher = {SIAM}
, doi = {10.1145/1283383.1283395}
}
%%% 98a:
@article{cr-ocg-10
, author = {Sergio Cabello and G{\"u}nter Rote}
, title = {Obnoxious centers in graphs}
, journal = {SIAM Journal on Discrete Mathematics}
, year = {2010}
, volume = {24}
, pages = {1713--1730}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Obnoxious+centers+in+graphs.ps}
, 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 $O(n\log ^2 n + m\log n)$ expected time. For planar graphs, we give algorithms with $O(n\log n)$ expected time and $O(n\log ^3 n)$ 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.}
}
%%% 99:
@article{drs-aopcm-08
, author = {R. L. Scot Drysdale and G{\"u}nter Rote and Astrid Sturm}
, title = {Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs}
, journal = {Computational Geometry, Theory and Applications}
, year = {2008}
, volume = {41}
, pages = {31--47}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Approximation+of+an+open+polygonal+curve+with+a+minimum+number+of+circular+arcs+and+biarcs.pdf}
, 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 (n^2 \log n)$ time for an original polygonal chain with $n$ vertices.
Using a similar approach, we design an algorithm with a runtime of $ O (n^2 \log n)$, for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.}
}
%%% 99a:
@inproceedings{drs-aopcm-06
, author = {R. L. Scot Drysdale and G{\"u}nter Rote and Astrid Sturm}
, title = {Approximation of an open polygonal curve with a minimum number of circular arcs}
, year = {2006}
, pages = {25--28}
, booktitle = {Abstracts of the 22nd European Workshop on Computational Geometry}
}
%%% 100:
@inproceedings{rz-msnf-07
, author = {G{\"u}nter Rote and Martin Zachariasen}
, title = {Matrix scaling by network flow}
, year = {2007}
, pages = {848--854}
, booktitle = {Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans}
, publisher = {SIAM}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Matrix+scaling+by+network+flow.ps}
, doi = {10.1145/1283383.1283474}
, abstract = {A given nonnegative $n\times n$ matrix $A=(a_{ij})$ is to be scaled, by multiplying its rows and columns by unknown positive multipliers $\lambda _i$ and $\mu _j$, such that the resulting matrix $(a_{ij}\lambda _i\mu _j)$ has specified row and column sums $r_i$ and $s_j$. We give an algorithm that achieves the desired row and column sums with a maximum absolute error $\varepsilon $ in $O(n^4(\log n + \log \frac h\varepsilon ))$ 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.}
}
%%% 101:
@incollection{bcmrv-ms-06
, author = {Jean-Daniel Boissonnat and David Cohen-Steiner and Bernard Mourrain and G{\"u}nter Rote and Gert Vegter}
, title = {Meshing of surfaces}
, year = {2006}
, chapter = {5}
, pages = {181--229}
, booktitle = {Effective Computational Geometry for Curves and Surfaces}
, editor = {Jean-Daniel Boissonnat and Monique Teillaud}
, publisher = {Springer-Verlag}
, series = {Mathematics and Visualization}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Meshing+of+surfaces.pdf}
, 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.}
}
%%% 102:
@incollection{rv-cti-06
, author = {G{\"u}nter Rote and Gert Vegter}
, title = {Computational topology: an introduction}
, year = {2006}
, chapter = {7}
, pages = {277--312}
, booktitle = {Effective Computational Geometry for Curves and Surfaces}
, editor = {Jean-Daniel Boissonnat and Monique Teillaud}
, publisher = {Springer-Verlag}
, series = {Mathematics and Visualization}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Computational+topology:+an+introduction.pdf}
, 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.}
}
%%% 103:
@incollection{rss-ptas-08
, author = {G{\"u}nter Rote and Francisco Santos and Ileana Streinu}
, title = {Pseudo-triangulations --- a survey}
, year = {2008}
, volume = {453}
, pages = {343--410}
, booktitle = {Surveys on Discrete and Computational Geometry---Twenty Years Later}
, editor = {Jacob E. Goodman and J\'anos Pach and Richard Pollack}
, publisher = {American Mathematical Society}
, series = {Contemporary Mathematics}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Pseudo-triangulations+-+a+survey.ps}
, eprint = {math/0612672}
, 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. }
}
%%% 104:
@inproceedings{abkrt-wgpdh-07
, author = {Helmut Alt and Hans Bodlaender and Marc van Kreveld and G{\"u}nter Rote and Gerard Tel}
, title = {Wooden geometric puzzles: design and hardness proofs}
, year = {2007}
, volume = {4475}
, pages = {16--29}
, booktitle = {Proceedings of the fourth conference on Fun with Algorithms (FUN 2007)}
, editor = {Pilu Crescenzi and Giuseppe Prencipe and Geppino Pucci}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/978-3-540-72914-3_4}
}
%%% 104a:
@article{abkrt-wgpdh-09
, author = {Helmut Alt and Hans Bodlaender and Marc van Kreveld and G{\"u}nter Rote and Gerard Tel}
, title = {Wooden geometric puzzles: design and hardness proofs}
, journal = {Theory of Computing Systems}
, year = {2009}
, volume = {44}
, pages = {160--174}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Wooden+geometric+puzzles:+design+and+hardness+proofs.pdf}
, 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(n^{k+1})$, for fixed $k$.}
}
%%% 105:
@inproceedings{bprsv-casp-07
, author = {Kevin Buchin and Simon Plantinga and G{\"u}nter Rote and Astrid Sturm and Gert Vegter}
, title = {Convex approximation by spherical patches}
, year = {2007}
, pages = {26--29}
, booktitle = {Abstracts of the 23rd European Workshop on Computational Geometry}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Convex+approximation+by+spherical+patches.pdf}
, 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.}
}
%%% 106:
@inproceedings{bbkrw-hdiwd-07
, author = {Kevin Buchin and Maike Buchin and Christian Knauer and G{\"u}nter Rote and Carola Wenk}
, title = {How difficult is it to walk the dog?}
, year = {2007}
, pages = {170--173}
, booktitle = {Abstracts of the 23rd European Workshop on Computational Geometry}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/How+difficult+is+it+to+walk+the+dog.ps}
, abstract = {We study the complexity of computing the Fr\'echet 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 $\Omega (n \log n)$ lower bound for the decision problem in the algebraic computation tree model allowing arithmetic operations and tests. Up to now only a $O(n^2)$ upper bound for the decision problem was known.
The lower bound extends to variants of the Fr\'echet distance such as the weak as well as the discrete Fr\'echet distance. For two polygonal curves in one dimension, we give a linear-time algorithm to compute their weak Fr\'echet distance.}
}
%%% 107:
@inproceedings{abkpr-tantm-07
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and Rom Pinchasi and G{\"u}nter Rote}
, title = {There are not too many magic configurations}
, year = {2007}
, pages = {142--149}
, booktitle = {Proceedings of the 23rd Annual Symposium on Computational Geometry, Gyeongju, South Korea}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/1247069.1247098}
}
%%% 107a:
@article{abkpr-tantm-08
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and Rom Pinchasi and G{\"u}nter Rote}
, title = {There are not too many magic configurations}
, journal = {Discrete and Computational Geometry}
, year = {2008}
, volume = {39}
, pages = {3--16}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/There+are+not+too+many+magic+configurations.ps}
, doi = {10.1007/s00454-007-9023-0}
}
%%% 107b:
@incollection{abkpr-tantm-08b
, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and Rom Pinchasi and G{\"u}nter Rote}
, title = {There are not too many magic configurations}
, year = {2008}
, pages = {1--14}
, booktitle = {Twentieth Anniversary Volume---Discrete \& Computational Geometry}
, editor = {Jacob E. Goodman and J\'anos Pach and Richard Pollack}
, publisher = {Springer-Verlag}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/There+are+not+too+many+magic+configurations.ps}
, doi = {10.1007/978-0-387-87363-3_1}
, 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.}
}
%%% 108:
@inproceedings{rrs-e3psg-07
, author = {Ares {Rib\'o Mor} and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Embedding 3-polytopes on a small grid}
, year = {2007}
, pages = {112--118}
, booktitle = {Proceedings of the 23rd Annual Symposium on Computational Geometry, Gyeongju, South Korea}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Small+grid+embeddings+of+3-polytopes.pdf}
, doi = {10.1145/1247069.1247086}
}
%%% 108a:
@article{rrs-sge3p-11
, author = {Ares {Rib\'o Mor} and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Small grid embeddings of 3-polytopes}
, journal = {Discrete and Computational Geometry}
, year = {2011}
, volume = {45}
, pages = {65--87}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Small+grid+embeddings+of+3-polytopes.pdf}
, eprint = {0908.0488}
, doi = {10.1007/s00454-010-9301-0}
, 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(2^{7.55n})=O(188^n)$. Finding a plane embedding which supports an equilibrium stress is the crucial part in the construction. In order to guarantee that the size of the coordinates and the stresses are small, we extend Tutte's spring embedding method. }
}
%%% 109:
@inproceedings{dkkr-nubqp-07
, author = {Darko Dimitrov and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote}
, title = {New upper bounds on the quality of {PCA} bounding boxes in {$R^2$} and {$R^3$}}
, year = {2007}
, pages = {275--283}
, booktitle = {Proceedings of the 23rd Annual Symposium on Computational Geometry, Gyeongju, South Korea}
, publisher = {Association for Computing Machinery}
, doi = {10.1145/1247069.1247119}
}
%%% 109a:
@inproceedings{dkkr-nubqp-07w
, author = {Darko Dimitrov and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote}
, title = {New upper bounds on the quality of {PCA} bounding boxes in {$R^2$} and {$R^3$}}
, year = {2007}
, pages = {122--125}
, booktitle = {Abstracts of the 23rd European Workshop on Computational Geometry}
}
%%% 109b:
@article{dkkr-bqpbb-09
, author = {Darko Dimitrov and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote}
, title = {Bounds on the quality of the {PCA} bounding boxes}
, journal = {Computational Geometry, Theory and Applications}
, year = {2009}
, volume = {42}
, pages = {772--789}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Bounds+on+the+quality+of+the+PCA+bounding+boxes.pdf}
, 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 $\mathbb {R}^d$. 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 $\mathbb {R}^2$ and $\mathbb {R}^3$.}
}
%%% 110:
@inproceedings{arsv-pdpg-07
, author = {Oswin Aichholzer and G{\"u}nter Rote and Andr{\'e} Schulz and Birgit Vogtenhuber}
, title = {Pointed drawings of planar graphs}
, year = {2007}
, pages = {237--240}
, booktitle = {Proceedings of the 19th Canadian Conference on Computational Geometry, Ottawa}
, editor = {Prosenjit Bose}
, url = {http://cccg.ca/proceedings/2007/09b5.pdf}
}
%%% 110a:
@article{arsv-pdpg-12
, author = {Oswin Aichholzer and G{\"u}nter Rote and Andr{\'e} Schulz and Birgit Vogtenhuber}
, title = {Pointed drawings of planar graphs}
, journal = {Computational Geometry, Theory and Applications}
, year = {2012}
, volume = {45}
, pages = {482--494}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Pointed+drawings+of+planar+graphs.pdf}
, doi = {10.1016/j.comgeo.2010.08.001}
, abstract = {We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than $\pi $. 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\'ezier 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.}
}
%%% 111:
@article{pr-msacl-09
, author = {Rom Pinchasi and G{\"u}nter Rote}
, title = {On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs}
, journal = {Israel Journal of Mathematics}
, year = {2009}
, volume = {172}
, pages = {337--348}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/On+the+maximum+size+of+an+anti-chain+of+linearly+separable+sets+and+convex+pseudo-discs.ps}
, eprint = {0707.0311}
, doi = {10.1007/s11856-009-0076-z}
, 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 $n^2$. We approach this problem by establishing the equivalence with the problem of the maximum monotone path in an arrangement of $n$ lines. For a related problem on antichains in families of convex 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.}
}
%%% 112:
@inproceedings{cgkr-gcfpt-08
, author = {Sergio Cabello and Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote}
, title = {Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension}
, year = {2008}
, pages = {836--843}
, booktitle = {Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco}
, publisher = {SIAM}
, doi = {10.1145/1347082.1347174}
, 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 that runs in $O(n\log n)$ time for any fixed dimension $d$. 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 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 is W[1]-hard with respect to $d$, and thus not fixed-parameter tractable unless FPT=W[1].}
}
%%% 112a:
@article{cgkmr-gcfpt-11
, author = {Sergio Cabello and Panos Giannopoulos and Christian Knauer and D\'aniel Marx and G{\"u}nter Rote}
, title = {Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension}
, journal = {ACM Transactions on Algorithms}
, year = {2011}
, month = sep
, volume = {7}
, number = {Article 43}
, pages = {27 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Geometric+clustering:+fixed-parameter+tractability+and+lower+bounds+with+respect+to+the+dimension.pdf}
, 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(6^ddn\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].}
}
%%% 113:
@inproceedings{aahkprsv-spia-08
, author = {Oswin Aichholzer and Franz Aurenhammer and Thomas Hackl and Bernhard Kornberger and Simon Plantinga and G{\"u}nter Rote and Astrid Sturm and Gert Vegter}
, title = {Seed polytopes for incremental approximation}
, year = {2008}
, pages = {13--16}
, booktitle = {Abstracts of the 24th European Workshop on Computational Geometry}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Recovering+structure+from+r-sampled+objects.ps}
}
%%% 113a:
@article{aakprsv-rsrso-09
, author = {Oswin Aichholzer and Franz Aurenhammer and Bernhard Kornberger and Simon Plantinga and G{\"u}nter Rote and Astrid Sturm and Gert Vegter}
, title = {Recovering structure from $r$-sampled objects}
, journal = {Computer Graphics Forum}
, year = {2009}
, volume = {28}
, pages = {1349--1360}
, booktitle = {Eurographics Symposium on Geometry Processing}
, editor = {Marc Alexa and Michael Kazhdan}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Recovering+structure+from+r-sampled+objects.ps}
, doi = {10.1111/j.1467-8659.2009.01512.x}
, 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 {\it 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\'ezier patches.
Our algorithm starts from an {\it $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 $\alpha $-shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large 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.}
}
%%% 114:
@inproceedings{bcgllrssw-dhgn-09
, author = {Kevin Buchin and Sergio Cabello and Joachim Gudmundsson and Maarten L\"offler and Jun Luo and G{\"u}nter Rote and Rodrigo I. Silveira and Bettina Speckmann and Thomas Wolle}
, title = {Detecting hotspots in geographic networks}
, year = {2009}
, pages = {217--231}
, booktitle = {Advances in GIScience. Proceedings of the 12th AGILE International Conference on Geographic Information Science}
, editor = {Monika Sester and Lars Bernard and Volker Paelke}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Geoinformation and Cartography}
, doi = {10.1007/978-3-642-00318-9_11}
, abstract = {We study a cluster-identification type problem on networks motivated by applications in geographical analysis. 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.}
}
%%% 114a:
@article{bcgllrssw-fmrfn-10
, author = {Kevin Buchin and Sergio Cabello and Joachim Gudmundsson and Maarten L\"offler and Jun Luo and G{\"u}nter Rote and Rodrigo I. Silveira and Bettina Speckmann and Thomas Wolle}
, title = {Finding the most relevant fragments in networks}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2010}
, volume = {14}
, pages = {307--336}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Finding+the+most+relevant+fragments+in+networks.pdf}
, 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.}
}
%%% 115:
@techreport{r-cissm-08
, author = {G{\"u}nter Rote}
, title = {Curve intersection by the {Subdivision}-{Supercomposition} {Method}}
, year = {2008}
, month = may
, number = {ACS-TR-361503-01}
, institution = {Freie Universit{\"a}t Berlin, Institut f\"ur Informatik}
, pages = {12 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Curve+intersection+by+the+Subdivision-Supercomposition+Method.ps}
, 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.}
}
%%% 116:
@inproceedings{efir-pptmc-08
, author = {Dania El-Khechen and Thomas Fevens and John Iacono and G{\"u}nter Rote}
, title = {Partitioning a polygon into two mirror congruent pieces}
, year = {2008}
, pages = {131--134}
, booktitle = {Proceedings of the 20th Canadian Conference on Computational Geometry, Montr\'eal}
, url = {http://cccg.ca/proceedings/2008/paper32.pdf}
}
%%% 117:
@inproceedings{gkrw-fptlb-09
, author = {Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote and Daniel Werner}
, title = {Fixed-parameter tractability and lower bounds for stabbing problems}
, year = {2009}
, month = mar
, pages = {281--284}
, booktitle = {Abstracts of the 25th European Workshop on Computational Geometry (EuroCG'09)}
}
%%% 117a:
@article{gkrw-fptlb-13
, author = {Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote and Daniel Werner}
, title = {Fixed-parameter tractability and lower bounds for stabbing problems}
, journal = {Computational Geometry, Theory and Applications}
, year = {2013}
, volume = {46}
, pages = {839--860}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Fixed-parameter+tractability+and+lower+bounds+for+stabbing+problems.pdf}
, eprint = {0906.3896}
, doi = {10.1016/j.comgeo.2011.06.005}
, 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$.}
}
%%% 118:
@inproceedings{r-tapm-09
, author = {G{\"u}nter Rote}
, title = {Two applications of point matching}
, year = {2009}
, month = mar
, pages = {187--189}
, booktitle = {Abstracts of the 25th European Workshop on Computational Geometry (EuroCG'09)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Two+applications+of+point+matching.pdf}
, 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.}
}
%%% 119:
@article{bbr-fgrhd-09
, author = {Ronnie Barequet and Gill Barequet and G{\"u}nter Rote}
, title = {Formulae and growth rates of high-dimensional polycubes}
, journal = {Electronic Notes in Discrete Mathematics}
, year = {2009}
, volume = {34}
, pages = {459--463}
, editor = {Jaroslav Ne\v{s}et\v{r}il and Andr\'e Raspaud}
, doi = {10.1016/j.endm.2009.07.076}
}
%%% 119a:
@article{bbr-fgrhd-10
, author = {Ronnie Barequet and Gill Barequet and G{\"u}nter Rote}
, title = {Formulae and growth rates of high-dimensional polycubes}
, journal = {Combinatorica}
, year = {2010}
, volume = {30}
, pages = {257--275}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Formulae+and+growth+rates+of+high-dimensional+polycubes.pdf}
, 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 {\it 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 $2ed-o(d)$. We conjecture that it is asymptotically equal to $(2d-3)e+O(1/d)$.}
}
%%% 120:
@inproceedings{gkr-pcsgp-09
, author = {Panos Giannopoulos and Christian Knauer and G{\"u}nter Rote}
, title = {The parameterized complexity of some geometric problems in unbounded dimension}
, year = {2009}
, month = sep
, volume = {5917}
, pages = {198--209}
, booktitle = {Proc. 4th Int. Workshop on Parameterized and Exact Computation---IWPEC 2009}
, editor = {Jianer Chen and Fedor V. Fomin}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, eprint = {0906.3469}
, doi = {10.1007/978-3-642-11269-0_16}
, abstract = {We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$:
(i) Given $n$ points in $d$, compute their minimum enclosing cylinder. (ii) Given two $n$-point sets in $d$ dimensions, decide whether they can be separated by two hyperplanes. (iii) 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)n^c)$ time, for any computable function $f$ and constant $c$ (unless FPT=W[1]). Our reductions also give an $n^{\Omega (d)}$-time lower bound (under the Exponential Time Hypothesis).}
}
%%% 121:
@inproceedings{ahhprsv-pgpc-09
, author = {Oswin Aichholzer and Thomas Hackl and Michael Hoffmann and Alexander Pilz and G{\"u}nter Rote and Bettina Speckmann and Birgit Vogtenhuber}
, title = {Plane graphs with parity constraints}
, year = {2009}
, month = aug
, volume = {5664}
, pages = {13--24}
, booktitle = {Algorithms and Data Structures Symposium---WADS 2009}
, editor = {Frank Dehne and Ian Munro and J\"org-R\"udiger Sack and Roberto Tamassia}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Plane+graphs+with+parity+constraints.pdf}
, doi = {10.1007/978-3-642-03367-4_2}
}
%%% 121a:
@article{ahhprsv-pgpc-14
, author = {Oswin Aichholzer and Thomas Hackl and Michael Hoffmann and Alexander Pilz and G{\"u}nter Rote and Bettina Speckmann and Birgit Vogtenhuber}
, title = {Plane graphs with parity constraints}
, journal = {Graphs and Combinatorics}
, year = {2014}
, volume = {30}
, pages = {47--69}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Plane+graphs+with+parity+constraints.pdf}
, 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.}
}
%%% 122:
@inproceedings{rs-rlpis-09
, author = {G{\"u}nter Rote and Andr\'e Schulz}
, title = {Resolving loads with positive interior stresses}
, year = {2009}
, month = aug
, volume = {5664}
, pages = {530--541}
, booktitle = {Algorithms and Data Structures Symposium---WADS 2009}
, editor = {Frank Dehne and Ian Munro and J\"org-R\"udiger Sack and Roberto Tamassia}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Resolving+loads+with+positive+interior+stresses.pdf}
, doi = {10.1007/978-3-642-03367-4_46}
, abstract = {We consider the pair $(p_i,f_i)$ as a force with two-dimensional direction vector $f_i$ applied at the point $p_i$ in the plane. For a given set of forces we ask for a non-crossing geometric graph on the points $p_i$ that has the following property: there exists a weight assignment to the edges of the graph, such that for every $p_i$ the sum of the weighted edges (seen as vectors) around $p_i$ yields $-f_i$. As additional constraint we restrict ourselves to weights that are 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. Our studies are motivated by the construction of discrete Laplace-Beltrami operators. }
}
%%% 123:
@article{ahorrss-fgbdt-13
, author = {Oswin Aichholzer and Thomas Hackl and Dav\'\i{}d Orden and Pedro Ramos and G{\"u}nter Rote and Andr\'e Schulz and Bettina Speckmann}
, title = {Flip graphs of bounded-degree triangulations}
, journal = {Graphs and Combinatorics}
, year = {2013}
, volume = {29}
, pages = {1577--1593}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Flip+graphs+of+bounded-degree+triangulations.pdf}
, eprint = {0903.2184}
, doi = {10.1007/s00373-012-1229-0}
, abstract = {We study flip graphs of (pseudo-)triangulations whose maximum vertex degree is bounded by a constant $k$. In particular, we consider triangulations of sets of $n$ points in convex position in the plane and prove that their flip graph is connected if and only if $k > 6$; the diameter of the flip graph is $O(n^2)$. We also show that for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for $k < 10$, and flip graphs of triangulations can be disconnected for any $k$.}
}
%%% 123a:
@article{ahorrss-fgbdt-09
, author = {Oswin Aichholzer and Thomas Hackl and Dav\'\i{}d Orden and Pedro Ramos and G{\"u}nter Rote and Andr\'e Schulz and Bettina Speckmann}
, title = {Flip graphs of bounded-degree triangulations}
, journal = {Electronic Notes in Discrete Mathematics}
, year = {2009}
, volume = {34}
, pages = {509--513}
, editor = {Jaroslav Ne\v{s}et\v{r}il and Andr\'e Raspaud}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Flip+graphs+of+bounded-degree+triangulations.pdf}
, doi = {10.1016/j.endm.2009.07.084}
}
%%% 124:
@article{amrw-cwsag-11
, author = {Tetsuo Asano and Wolfgang Mulzer and G{\"u}nter Rote and Yajun Wang}
, title = {Constant-work-space algorithms for geometric problems}
, journal = {Journal of Computational Geometry}
, year = {2011}
, volume = {2}
, pages = {46--68}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Constant-work-space+algorithms+for+geometric+problems.pdf}
, doi = {10.20382/jocg.v2i1a4}
, 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 MST in quadratic time per step, so that the whole EMST 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. }
}
%%% 124a:
@inproceedings{ar-cwsag-09
, author = {Tetsuo Asano and G{\"u}nter Rote}
, title = {Constant-working-space algorithms for geometric problems}
, year = {2009}
, pages = {87--90}
, booktitle = {Proceedings of the 21st Canadian Conference on Computational Geometry, Vancouver}
, url = {http://cccg.ca/proceedings/2009/cccg09_23.pdf}
}
%%% 125:
@inproceedings{dfrssz-ipsma-09
, author = {Erik D. Demaine and S\'andor P. Fekete and G{\"u}nter Rote and Nils Schweer and Daria Schymura and Mariano Zelke}
, title = {Integer point sets minimizing average pairwise $\ell _1$ distance: What is the optimal shape of a town?}
, year = {2009}
, pages = {145--148}
, booktitle = {Proceedings of the 21st Canadian Conference on Computational Geometry, Vancouver}
, url = {http://cccg.ca/proceedings/2009/cccg09_38.pdf}
}
%%% 125a:
@article{dfrssz-ipsma-11
, author = {Erik D. Demaine and S\'andor P. Fekete and G{\"u}nter Rote and Nils Schweer and Daria Schymura and Mariano Zelke}
, title = {Integer point sets minimizing average pairwise {$L_1$} distance: {What} is the optimal shape of a town?}
, journal = {Computational Geometry, Theory and Applications}
, year = {2011}
, volume = {44}
, pages = {82--94}
, url = {http://page.mi.fu-berlin.de/rote/Papers/postscript/Integer+point+sets+minimizing+average+pairwise+L1+distance:+what+is+the+optimal+shape+of+a+town.ps}
, eprint = {1009.5628}
, doi = {10.1016/j.comgeo.2010.09.004}
, abstract = {An {\it $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 {\it 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(n^{7.5})$ time. This is also practically useful, as it allows us to compute optimal solutions up to $n=80$. }
}
%%% 126:
@article{acgr-lpl-11
, author = {Boris Aronov and Otfried Cheong and Xavier Goaoc and G{\"u}nter Rote}
, title = {Lines pinning lines}
, journal = {Discrete and Computational Geometry}
, year = {2011}
, volume = {45}
, pages = {230--260}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Lines+pinning+lines.pdf}
, eprint = {1002.3294}
, doi = {10.1007/s00454-010-9288-6}
, 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.}
}
%%% 127:
@inproceedings{r-plspm-10
, author = {G{\"u}nter Rote}
, title = {Partial least-squares point matching under translations}
, year = {2010}
, month = mar
, pages = {249--251}
, booktitle = {26th European Workshop on Computational Geometry (EuroCG'10)}
, editor = {Jan Vahrenhold}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Partial+least-squares+point+matching+under+translations.pdf}
, abstract = {We consider the problem of translating a given {\it pattern set\/} $B$ of size $m$, and matching every point of $B$ to some point of a larger {\it 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.}
}
%%% 128:
@inproceedings{rz-c-11
, author = {G{\"u}nter Rote and Uri Zwick}
, title = {Collapse}
, year = {2011}
, pages = {606--613}
, booktitle = {Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco}
, publisher = {SIAM}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Collapse.pdf}
, 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 {\it how\/} an {\it unstable\/} tower of bricks collapses. We use Gau\ss{}' {\it 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.}
}
%%% 129:
@article{r-zz-10
, author = {G{\"u}nter Rote}
, title = {Zitate z\"ahlen}
, journal = {Internat. Math. Nachrichten}
, year = {2010}
, volume = {213}
, pages = {1--5}
, language = {German}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Zitate+zaehlen.pdf}
, 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. }
}
%%% 130:
@inproceedings{abbr-pncpn-11
, author = {Andrei Asinowski and Ronnie Barequet and Gill Barequet and G{\"u}nter Rote}
, title = {Proper $n$-cell polycubes in $n-3$ dimensions}
, year = {2011}
, volume = {6842}
, pages = {181--191}
, booktitle = {Computing and Combinatorics. Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011)}
, editor = {Bin Fu and Ding-Zhu Du}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Proper+n-cell+polycubes+in+n-3+dimensions.pdf}
, doi = {10.1007/978-3-642-22685-4_16}
}
%%% 130a:
@article{abbr-pncpn-12
, author = {Andrei Asinowski and Ronnie Barequet and Gill Barequet and G{\"u}nter Rote}
, title = {Proper $n$-cell polycubes in $n-3$ dimensions}
, journal = {Journal of Integer Sequences}
, year = {2012}
, volume = {15}
, number = {Article 12.8.4}
, pages = {16 pages}
, url = {https://cs.uwaterloo.ca/journals/JIS/VOL15/Barequet/barequet2.html}
, 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 {\it proper\/} polycubes: A polycube is said to be {\it 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.}
}
%%% 131:
@incollection{drt-mppcs-13
, author = {Adrian Dumitrescu and G{\"u}nter Rote and Csaba D. T\'oth}
, title = {Monotone paths in planar convex subdivisions and polytopes}
, year = {2013}
, volume = {69}
, pages = {79--104}
, booktitle = {Discrete Geometry and Optimization}
, editor = {K\'aroly Bezdek and Antoine Deza and Yinyu Ye}
, publisher = {Springer-Verlag}
, series = {Fields Institute Communications}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Monotone+paths+in+planar+convex+subdivisions+and+polytopes.pdf}
, doi = {10.1007/978-3-319-00200-2_6}
, abstract = {Consider a connected subdivision of the plane into $n$ convex faces where every vertex is incident to at most $\Delta $ edges. Then, starting from every vertex there is a path with at least $\Omega (\log _\Delta n)$ edges that is monotone in some direction. This bound is best possible. Consider now a connected subdivision of the plane into $n$ convex faces where exactly $k$ faces are unbounded. Then, there is a path with at least $\Omega (\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\ge 4$, there exists a polytope $P$ with $n$ vertices, bounded vertex degrees, and triangular faces such that every monotone path on the 1-skeleton of $P$ has at most $O(\log ^2 n)$ edges. We also construct a polytope $Q$ with $n$ vertices, and triangular faces, (with unbounded degree however), such that every monotone path on the 1-skeleton of $Q$ has at most $O(\log n)$ edges. }
}
%%% 131a:
@inproceedings{drt-mppcs-12
, author = {Adrian Dumitrescu and G{\"u}nter Rote and Csaba D. T\'oth}
, title = {Monotone paths in planar convex subdivisions}
, year = {2012}
, volume = {7434}
, pages = {240--251}
, booktitle = {Computing and Combinatorics. Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON 2012)}
, editor = {Joachim Gudmundsson and Julian Mestre and Taso Viglas}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, doi = {10.1007/978-3-642-32241-9_21}
}
%%% 131b:
@inproceedings{r-lmpcs-11
, author = {G{\"u}nter Rote}
, title = {Long monotone paths in convex subdivisions}
, year = {2011}
, month = mar
, pages = {183--184}
, booktitle = {Abstracts of the 27th European Workshop on Computational Geometry (EuroCG'11)}
, editor = {Michael Hoffmann}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Long+monotone+paths+in+convex+subdivisions.pdf}
, abstract = {Consider a connected subdivision of the plane into $n$ convex regions where every vertex has degree at most $d$. Then, for every vertex there is a path with at least $\Omega (\log _d n)$ edges through this vertex that is monotone in some direction. This bound is best possible.}
}
%%% 132:
@inproceedings{addmru-cdsdo-11
, author = {Zachary Abel and Erik Demaine and Martin Demaine and Hiroaki Matsui and G{\"u}nter Rote and Ryuhei Uehara}
, title = {Common developments of several different orthogonal boxes}
, year = {2011}
, pages = {77--82}
, booktitle = {Proceedings of the 23rd Canadian Conference on Computational Geometry, Vancouver}
, url = {http://2011.cccg.ca/PDFschedule/papers/paper49.pdf}
, 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\times 1\times 5$, $1\times 2\times 3$, and $0\times 1\times 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.}
}
%%% 133:
@inproceedings{aadddhlrssw-cpwlv-11
, author = {Oswin Aichholzer and Greg Aloupis and Erik D. Demaine and Martin L. Demaine and Vida Dujmovi\'c and Ferran Hurtado and Anna Lubiw and G{\"u}nter Rote and Andr\'e Schulz and Diane L. Souvaine and Andrew Winslow}
, title = {Convexifying polygons without losing visibilities}
, year = {2011}
, pages = {229--234}
, booktitle = {Proceedings of the 23rd Canadian Conference on Computational Geometry, Vancouver}
, url = {http://2011.cccg.ca/PDFschedule/papers/paper70.pdf}
, 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. }
}
%%% 134:
@inproceedings{aaacjr-tca-12
, author = {Oswin Aichholzer and Wolfgang Aigner and Franz Aurenhammer and Kate\v{r}ina {\v{C}ech Dobi\'a\v{s}ov\'a} and Bert J\"uttler and G{\"u}nter Rote}
, title = {Triangulations with circular arcs}
, year = {2012}
, volume = {7034}
, pages = {296--307}
, booktitle = {Graph Drawing. GD 2011, Proceedings of the 19th International Symposium on Graph Drawing, Eindhoven, September 2011, Revised Selected Papers}
, editor = {Marc van Kreveld and Bettina Speckmann}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Triangulations+with+circular+arcs.pdf}
, doi = {10.1007/978-3-642-25878-7_29}
}
%%% 134a:
@article{aaacjr-tca-15
, author = {Oswin Aichholzer and Wolfgang Aigner and Franz Aurenhammer and Kate\v{r}ina {\v{C}ech Dobi\'a\v{s}ov\'a} and Bert J\"uttler and G{\"u}nter Rote}
, title = {Triangulations with circular arcs}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2015}
, volume = {19}
, issue = {1}
, pages = {43--65}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Triangulations+with+circular+arcs.pdf}
, doi = {10.7155/jgaa.00346}
, abstract = {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. }
}
%%% 135:
@inproceedings{r-rpgcp-12
, author = {G{\"u}nter Rote}
, title = {Realizing planar graphs as convex polytopes}
, year = {2012}
, volume = {7034}
, pages = {238--241}
, booktitle = {Graph Drawing. GD 2011, Proceedings of the 19th International Symposium on Graph Drawing, Eindhoven, September 2011, Revised Selected Papers}
, editor = {Marc van Kreveld and Bettina Speckmann}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Realizing+planar+graphs+as+convex+polytopes.pdf}
, doi = {10.1007/978-3-642-25878-7_23}
, abstract = {This 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.}
}
%%% 136:
@article{abbkmrs-mcasp-13
, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Memory-constrained algorithms for simple polygons}
, journal = {Computational Geometry, Theory and Applications}
, year = {2013}
, volume = {46}
, pages = {959--969}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Memory-constrained+algorithms+for+simple+polygons.pdf}
, eprint = {1112.5904}
, doi = {10.1016/j.comgeo.2013.04.005}
, abstract = {A constant-workspace algorithm has read-only access to an input array and may use only $O(1)$ 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(n^2)$ 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(n^2)$ time, we are able to solve shortest path queries between any two points inside the polygon in $O(n^2/s)$ time.}
}
%%% 136a:
@article{abbkmrs-romca-14
, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Reprint of: Memory-constrained algorithms for simple polygons}
, journal = {Computational Geometry, Theory and Applications}
, year = {2014}
, volume = {47}
, pages = {469--479}
, eprint = {1112.5904}
, doi = {10.1016/j.comgeo.2013.11.004}
}
%%% 136b:
@inproceedings{abbkmrs-mcasp-12
, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Memory-constrained algorithms for simple polygons}
, year = {2012}
, month = mar
, pages = {49--52}
, booktitle = {Abstracts of the 28th European Workshop on Computational Geometry (EuroCG'12)}
, editor = {Walter Didimo and Giuseppe Liotta}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Memory-constrained+algorithms+for+simple+polygons.pdf}
}
%%% 137:
@inproceedings{ccchlr-cdpsl-12
, author = {Jean Cardinal and Nathann Cohen and S\'ebastien Collette and Michael Hoffmann and Stefan Langerman and G{\"u}nter Rote}
, title = {Coloring dynamic point sets on a line}
, year = {2012}
, month = mar
, pages = {209--212}
, booktitle = {Abstracts of the 28th European Workshop on Computational Geometry (EuroCG'12)}
, editor = {Walter Didimo and Giuseppe Liotta}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Coloring+hypergraphs+induced+by+dynamic+point+sets+and+bottomless+rectangles.pdf}
}
%%% 137a:
@inproceedings{accchhkllmru-chidp-13
, author = {Andrei Asinowski and Jean Cardinal and Nathann Cohen and S\'ebastien Collette and Thomas Hackl and Michael Hoffmann and Kolja Knauer and Stefan Langerman and Micha{\l } Laso\'n and Piotr Micek and G{\"u}nter Rote and Torsten Ueckerdt}
, title = {Coloring hypergraphs induced by dynamic point sets and bottomless rectangles}
, year = {2013}
, month = aug
, volume = {8037}
, pages = {73--84}
, booktitle = {Algorithms and Data Structures Symposium---WADS 2013}
, editor = {Frank Dehne and Roberto Solis-Oba and J\"org-R\"udiger Sack}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Coloring+hypergraphs+induced+by+dynamic+point+sets+and+bottomless+rectangles.pdf}
, eprint = {1302.2426}
, doi = {10.1007/978-3-642-40104-6_7}
, 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\'alv\"olgyi on cover-decomposability of octants (2011,2012).}
}
%%% 138:
@inproceedings{efr-aigko-12
, author = {Herbert Edelsbrunner and Brittany Terese Fasy and G{\"u}nter Rote}
, title = {Add isotropic {Gaussian} kernels at own risk: more and more resilient modes in higher dimensions}
, year = {2012}
, pages = {91--100}
, booktitle = {Proceedings of the 28th Annual Symposium on Computational Geometry, Chapel Hill, USA}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Add+isotropic+Gaussian+kernels+at+own+risk:+more+and+more+resilient+modes+in+higher+dimensions.pdf}
, doi = {10.1145/2261250.2261265}
}
%%% 138a:
@article{efr-aigko-13
, author = {Herbert Edelsbrunner and Brittany Terese Fasy and G{\"u}nter Rote}
, title = {Add isotropic {Gaussian} kernels at own risk: more and more resilient modes in higher dimensions}
, journal = {Discrete and Computational Geometry}
, year = {2013}
, volume = {49}
, pages = {797--822}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Add+isotropic+Gaussian+kernels+at+own+risk:+more+and+more+resilient+modes+in+higher+dimensions.pdf}
, 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{\accent "7E n}\'an and Williams exhibited $n+1$ isotropic 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. }
}
%%% 139:
@inproceedings{ar-csvv-12
, author = {Dror Atariah and G{\"u}nter Rote}
, title = {Configuration space visualization (video)}
, year = {2012}
, pages = {415--416}
, booktitle = {Proceedings of the 28th Annual Symposium on Computational Geometry, Chapel Hill, USA}
, publisher = {Association for Computing Machinery}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Configuration+space+visualization.pdf}
, doi = {10.1145/2261250.2261313}
, 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.}
}
%%% 140:
@article{gkpr-ostpu-13
, author = {Darius Gei\ss{} and Rolf Klein and Rainer Penninger and G{\"u}nter Rote}
, title = {Optimally solving a transportation problem using {Voronoi} diagrams}
, journal = {Computational Geometry, Theory and Applications}
, year = {2013}
, volume = {46}
, pages = {1009--1016}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimally+solving+a+transportation+problem+using+Voronoi+diagrams.pdf}
, eprint = {1206.3057}
, doi = {10.1016/j.comgeo.2013.05.005}
, 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 $C_p$ of prescribed volume, and (ii) the average distance of all points of $C$ from their respective sites $p$ is minimized. In our model, volume is quantified by some measure, and the distance between a site $p$ and a point $z$ is given by a function $d_p(z)$. Under quite liberal technical assumptions on $C$ and on the functions $d_p$ we show that a solution of minimum total cost can be obtained by intersecting with $C$ the Voronoi diagram of the sites in $S$, based on the functions $d_p$ with suitable additive weights. Moreover, this optimum partition is unique up to sets of measure zero. Unlike the deep analytic methods of classical transportation theory, our proof is based directly on geometric arguments.}
}
%%% 140a:
@article{gkpr-uroos-14
, author = {Darius Gei\ss{} and Rolf Klein and Rainer Penninger and G{\"u}nter Rote}
, title = {(Unauthorized) Reprint of: Optimally solving a transportation problem using {Voronoi} diagrams}
, journal = {Computational Geometry, Theory and Applications}
, year = {2014}
, volume = {47}
, pages = {499--506}
, eprint = {1206.3057}
, doi = {10.1016/j.comgeo.2013.11.003}
}
%%% 141:
@article{ikrss-tnttv-13
, author = {Ivan Izmestiev and Robert B. Kusner and G{\"u}nter Rote and Boris Springborn and John M. Sullivan}
, title = {There is no triangulation of the torus with vertex degrees $5,6,\ldots ,6,7$ and related results: geometric proofs for combinatorial theorems}
, journal = {Geometriae Dedicata}
, year = {2013}
, volume = {166}
, pages = {15--29}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/There+is+no+triangulation+of+the+torus+with+vertex+degrees+5,6,...,6,7+and+related+results:+geometric+proofs+for+combinatorial+theorems.pdf}
, eprint = {1207.3605}
, doi = {10.1007/s10711-012-9782-5}
, 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. }
}
%%% 142:
@incollection{bpr-th-13
, author = {Sarit Buzaglo and Rom Pinchasi and G{\"u}nter Rote}
, title = {Topological hypergraphs}
, year = {2013}
, pages = {71--81}
, booktitle = {Thirty Essays on Geometric Graph Theory}
, editor = {J\'anos Pach}
, publisher = {Springer-Verlag}
, 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.}
}
%%% 143:
@inproceedings{r-dc-13
, author = {G{\"u}nter Rote}
, title = {The degree of convexity}
, year = {2013}
, month = mar
, pages = {69--72}
, booktitle = {Abstracts of the 29th European Workshop on Computational Geometry (EuroCG'13)}
, editor = {S\'andor Fekete}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+degree+of+convexity.pdf}
, abstract = {We measure the degree of convexity of a planar region by the probability that two randomly chosen points see each other inside the polygon. We show that, for a polygonal region with $n$ edges, this measure can be evaluated in polynomial time as a sum of $O(n^9)$ closed-form expressions.}
}
%%% 144:
@article{amr-qpscu-15
, author = {Andrei Asinowski and Tillmann Miltzow and G{\"u}nter Rote}
, title = {Quasi-parallel segments and characterization of unique bichromatic matchings}
, journal = {Journal of Computational Geometry}
, year = {2015}
, volume = {6}
, pages = {185--219}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Quasi-parallel+segments+and+characterization+of+unique+bichromatic+matchings.pdf}
, eprint = {1302.4400}
, doi = {10.20382/jocg.v6i1a8}
, 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.}
}
%%% 144a:
@inproceedings{amr-qpscu-13
, author = {Andrei Asinowski and Tillmann Miltzow and G{\"u}nter Rote}
, title = {Quasi-parallel segments and characterization of unique bichromatic matchings (extended abstract)}
, year = {2013}
, month = mar
, pages = {225--228}
, booktitle = {Abstracts of the 29th European Workshop on Computational Geometry (EuroCG'13)}
, editor = {S\'andor Fekete}
}
%%% 145:
@article{ammnr-ivcpa-14
, author = {N. V. Abrosimov and E. {Makai, jr.} and A. D. Mednykh and Yu. G. Nikonorov and G{\"u}nter Rote}
, title = {The infimum of the volumes of convex polytopes of any given facet areas is 0}
, journal = {Stud. Sci. Math. Hungarica}
, year = {2014}
, volume = {51}
, pages = {466--519}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+infimum+of+the+volumes+of+convex+polytopes+of+any+given+facet+areas+is+0.pdf}
, eprint = {1304.6579}
, doi = {10.1556/SScMath.51.2014.4.1292}
, abstract = {We prove that, for any dimension $n\ge 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. }
}
%%% 146:
@article{gmppr-advg-14
, author = {D\'aniel Gerbner and Viola M\'esz\'aros and D\"om\"ot\"or P\'alv\"olgyi and Alexey Pokrovskiy and G{\"u}nter Rote}
, title = {Advantage in the discrete {Voronoi} game}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2014}
, volume = {18}
, issue = {3}
, pages = {439--455}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Advantage+in+the+discrete+Voronoi+game.pdf}
, eprint = {1303.0523}
, doi = {10.7155/jgaa.00331}
, 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 one quarter of the vertices, and we give examples where she can get only little more than one 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. }
}
%%% 147:
@inproceedings{hkrss-chatt-13
, author = {Michael Hoffmann and Vincent Kusters and G{\"u}nter Rote and Maria Saumell and Rodrigo I. Silveira}
, title = {Convex hull alignment through translation}
, year = {2013}
, pages = {295--300}
, booktitle = {Proceedings of the 25th Canadian Conference on Computational Geometry, (CCCG'2013)}
, url = {http://2013.cccg.ca/proceedings/2013/papers/paper_67.pdf}
, 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. }
}
%%% 148:
@article{bhhlnprss-fmsdp-15
, author = {Tristram Bogart and Christian Haase and Milena Hering and Benjamin Lorenz and Benjamin Nill and Andreas Paffenholz and G{\"u}nter Rote and Francisco Santos and Hal Schenck}
, title = {Finitely many smooth $d$-polytopes with $n$ lattice points}
, journal = {Israel Journal of Mathematics}
, year = {2015}
, volume = {207}
, pages = {301--329}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Finitely+many+smooth+d-polytopes+with+n+lattice+points.pdf}
, eprint = {1010.3887}
, doi = {10.1007/s11856-015-1175-7}
, 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 $P^n$ that are induced by a complete linear system. We also enumerate all smooth 3-polytopes with at most 12 lattice points.}
}
%%% 149:
@article{agr-pgcss-13
, author = {Dror Atariah and Sunayana Ghosh and G{\"u}nter Rote}
, title = {On the parameterization and the geometry of the configuration space of a single planar robot}
, journal = {Journal of WSCG}
, year = {2013}
, volume = {21}
, pages = {11--20}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/On+the+parameterization+and+the+geometry+of+the+configuration+space+of+a+single+planar+robot.pdf}
, 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.}
}
%%% 150:
@article{jr-rrsa-16
, author = {Rafel Jaume and G{\"u}nter Rote}
, title = {Recursively-regular subdivisions and applications}
, journal = {Journal of Computational Geometry}
, year = {2016}
, volume = {7}
, pages = {185--220}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Recursively-regular+subdivisions+and+applications.pdf}
, eprint = {1310.4372}
, doi = {10.20382/jocg.v7i1a10}
, abstract = {We generalize regular subdivisions (polyhedral complexes resulting from the projection of the lower faces of a polyhedron) introducing the class of {\it 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 {\it finest regular coarsening\/} and the {\it 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.}
}
%%% 151:
@inproceedings{r-lfmea-14
, author = {G{\"u}nter Rote}
, title = {Lexicographic Fr\'echet matchings (extended abstract)}
, year = {2014}
, month = mar
, booktitle = {Abstracts of the 30th European Workshop on Computational Geometry (EuroCG'14)}
, editor = {Paz Carmi and Matthew Katz and Shakhar Smorodinsky}
, url = {http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000020012}
, abstract = {The Fr\'echet 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.}
}
%%% 152:
@inproceedings{brs-4ea-14
, author = {Gill Barequet and G{\"u}nter Rote and Mira Shalah}
, title = {$\lambda >4$ (extended abstract)}
, year = {2014}
, month = mar
, booktitle = {Abstracts of the 30th European Workshop on Computational Geometry (EuroCG'14)}
, editor = {Paz Carmi and Matthew Katz and Shakhar Smorodinsky}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf}
}
%%% 152a:
@inproceedings{brs-4-15
, author = {Gill Barequet and G{\"u}nter Rote and Mira Shalah}
, title = {$\lambda >4$}
, year = {2015}
, volume = {9294}
, pages = {83--94}
, booktitle = {Algorithms --- ESA 2015. Proc. 23rd Annual European Symposium on Algorithms, Patras}
, editor = {Nikhil Bansal and Irene Finocchi}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf}
, doi = {10.1007/978-3-662-48350-3_8}
}
%%% 152b:
@article{brs-4ilbg-16
, author = {Gill Barequet and G{\"u}nter Rote and Mira Shalah}
, title = {$\lambda >4$: An improved lower bound on the growth constant of polyominoes}
, journal = {Communications of the ACM}
, year = {2016}
, month = jul
, volume = {59}
, issue = {7}
, pages = {88--95}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf}
, doi = {10.1145/2851485}
, abstract = {A {\it polyomino\/} (or {\it 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 \to \infty $, where $A(n)$ is the number of polyominoes of size $n$. This value is also known as ``Klarner's constant'' and denoted by $\lambda $. So far, the best lower and upper bounds on $\lambda $ were roughly 3.98 and 4.65, respectively, and so not even a single decimal digit of $\lambda $ was known. Using extremely high computing resources, we have shown (still rigorously) that $\lambda > 4.00253$, thereby settling a long-standing problem: proving that the leading digit of $\lambda $ is 4.}
}
%%% 153:
@inproceedings{hkkr-qrmgd-14
, author = {Michael Hoffmann and Marc van Kreveld and Vincent Kusters and G{\"u}nter Rote}
, title = {Quality ratios of measures for graph drawing styles}
, year = {2014}
, booktitle = {Proceedings of the 26th Canadian Conference on Computational Geometry, (CCCG'2014)}
, url = {http://cccg.ca/proceedings/2014/papers/paper05.pdf}
, 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.}
}
%%% 154:
@inproceedings{ahkr-gdrel-14
, author = {Oswin Aichholzer and Michael Hoffmann and Marc van Kreveld and G{\"u}nter Rote}
, title = {Graph drawings with relative edge length specifications}
, year = {2014}
, booktitle = {Proceedings of the 26th Canadian Conference on Computational Geometry, (CCCG'2014)}
, url = {http://cccg.ca/proceedings/2014/papers/paper27.pdf}
, 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.}
}
%%% 155:
@article{gkprw-sepdd-17
, author = {D\'aniel Gerbner and Bal\'azs Keszegh and D\"om\"ot\"or P\'alv\"olgyi and G{\"u}nter Rote and G\'abor Wiener}
, title = {Search for the end of a path in the $d$-dimensional grid and in other graphs}
, journal = {Ars Mathematica Contemporanea}
, year = {2017}
, volume = {12}
, issue = {2}
, pages = {301--314}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Search+for+the+end+of+a+path+in+the+d-dimensional+grid+and+in+other+graphs.pdf}
, 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. }
}
%%% 156:
@article{ar-psmnc-18
, author = {Andrei Asinowski and G{\"u}nter Rote}
, title = {Point sets with many non-crossing matchings}
, journal = {Computational Geometry, Theory and Applications}
, year = {2018}
, volume = {68}
, pages = {7--33}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Point+sets+with+many+non-crossing+matchings.pdf}
, eprint = {1502.04925}
, doi = {10.1016/j.comgeo.2017.05.006}
, 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.0438^n)$ and $\Omega ^*(3^n)$, where the $\Omega ^*$ notation hides polynomial factors in the aymptotic expression. The lower bound, due to Garc\'ia, Noy, and Tejel (2000), is attained by the double chain, which has $\Theta (3^n/n^{\Theta (1)})$ such matchings. We reprove this bound in a simplified way that uses the novel notion of {\it down-free matchings\/}. We 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 $\Theta ^*(\lambda ^n)$ non-crossing perfect matchings matchings with $\lambda \approx 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 $\Theta ^*(\nu ^n)$ non-crossing perfect matchings with $\nu \approx 3.0930$. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors. }
}
%%% 157:
@article{aekmprst-spsqv-16
, author = {Esther M. Arkin and Alon Efrat and Christian Knauer and Joseph S. B. Mitchell and Valentin Polishchuk and G{\"u}nter Rote and Lena Schlipf and Topi Talvitie}
, title = {Shortest path to a segment and quickest visibility queries}
, journal = {Journal of Computational Geometry}
, year = {2016}
, volume = {7}
, pages = {77--100}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Shortest+path+to+a+segment+and+quickest+visibility+queries.pdf}
, doi = {10.20382/jocg.v7i2a5}
, 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 {\it 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 {\it 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 {\it segment\/} in the domain.}
}
%%% 157a:
@inproceedings{aekmprst-spsqv-15
, author = {Esther M. Arkin and Alon Efrat and Christian Knauer and Joseph S. B. Mitchell and Valentin Polishchuk and G{\"u}nter Rote and Lena Schlipf and Topi Talvitie}
, title = {Shortest path to a segment and quickest visibility queries}
, year = {2015}
, volume = {34}
, pages = {658--673}
, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}
, editor = {Lars Arge and J\'anos Pach}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Shortest+path+to+a+segment+and+quickest+visibility+queries.pdf}
, doi = {10.4230/LIPIcs.SOCG.2015.658}
}
%%% 157b:
@inproceedings{krs-sipqs-08
, author = {Christian Knauer and G{\"u}nter Rote and Lena Schlipf}
, title = {Shortest inspection-path queries in simple polygons}
, year = {2008}
, pages = {153--156}
, booktitle = {Abstracts of the 24th European Workshop on Computational Geometry}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Shortest+inspection-path+queries+in+simple+polygons.pdf}
}
%%% 158:
@inproceedings{hirs-ss2st-16
, author = {P\'eter Hajnal and Alexander Igamberdiev and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Saturated simple and 2-simple topological graphs with few edges}
, year = {2016}
, month = jun
, volume = {9224}
, pages = {391--405}
, booktitle = {41st International Workshop on Graph-Theoretic Concepts in Computer Science---WG 2015}
, editor = {Ernst Mayr}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Saturated+simple+and+2-simple+topological+graphs+with+few+edges.pdf}
, eprint = {1503.01386}
, doi = {10.1007/978-3-662-53174-7_28}
}
%%% 158a:
@article{hirs-ss2st-17
, author = {P\'eter Hajnal and Alexander Igamberdiev and G{\"u}nter Rote and Andr\'e Schulz}
, title = {Saturated simple and 2-simple topological graphs with few edges}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2017}
, volume = {22}
, issue = {1}
, pages = {117--138}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Saturated+simple+and+2-simple+topological+graphs+with+few+edges.pdf}
, doi = {10.7155/jgaa.00460}
, abstract = {A {\it 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 {\it $k$-simple topological graph\/}, every pair of edges has at most $k$ common points of this kind. We construct {\it 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 Kyn\v{c}l, Pach, Radoi\v{c}i\'c, and T\'oth (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. }
}
%%% 159:
@inproceedings{adddkrr-wpegd-16
, author = {Patrizio Angelini and Giordano {Da Lozzo} and Giuseppe {Di Battista} and Valentino {Di Donato} and Philipp Kindermann and G{\"u}nter Rote and Ignaz Rutter}
, title = {Windrose planarity: embedding graphs with direction-constrained edges}
, year = {2016}
, pages = {985--996}
, booktitle = {Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA16), San Francisco}
, editor = {Robert Krauthgamer}
, publisher = {SIAM}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Windrose+planarity:+embedding+graphs+with+direction-constrained+edges.pdf}
, doi = {10.1137/1.9781611974331.ch70}
}
%%% 159a:
@article{adddkrr-wpegd-18
, author = {Patrizio Angelini and Giordano {Da Lozzo} and Giuseppe {Di Battista} and Valentino {Di Donato} and Philipp Kindermann and G{\"u}nter Rote and Ignaz Rutter}
, title = {Windrose planarity: embedding graphs with direction-constrained edges}
, journal = {ACM Transactions on Algorithms}
, year = {2018}
, month = sep
, volume = {14}
, number = {Article 54}
, pages = {54:1--54:24}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Windrose+planarity:+embedding+graphs+with+direction-constrained+edges.pdf}
, eprint = {1510.02659}
, doi = {10.1145/3239561}
, 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(n) \times O(n)$ grid. This contrasts with the fact that straight-line windrose-planar drawings may require exponential area. }
}
%%% 160:
@article{arw-otss-18
, author = {Dror Atariah and G{\"u}nter Rote and Mathijs Wintraecken}
, title = {Optimal triangulation of saddle surfaces}
, journal = {Beitr{\"a}ge zur Algebra und Geometrie---Contributions to Algebra and Geometry}
, year = {2018}
, volume = {59}
, issue = {1}
, pages = {113--126}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimal+triangulation+of+saddle+surfaces.pdf}
, eprint = {1511.01361}
, doi = {10.1007/s13366-017-0351-9}
, abstract = {We consider the piecewise linear approximation of saddle functions of the form $f(x,y)=ax^2-by^2$ under the $L_{\infty }$ 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.}
}
%%% 161:
@inproceedings{r-ctpst-16
, author = {G{\"u}nter Rote}
, title = {Congruence testing of point sets in three and four dimensions---Results and techniques (invited talk)}
, year = {2016}
, volume = {9582}
, pages = {50--59}
, booktitle = {Sixth International Conference on Mathematical Aspects of Computer and Information Sciences---MACIS 2015}
, editor = {Ilias S. Kotsireas and Siegfried Rump and Chee Yap}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Congruence+testing+of+point+sets+in+three+and+four+dimensions-Results+and+techniques.pdf}
, 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. }
}
%%% 162:
@inproceedings{kr-ctps4-16
, author = {Heuna Kim and G{\"u}nter Rote}
, title = {Congruence testing of point sets in 4-space}
, year = {2016}
, volume = {51}
, pages = {48:1--48:16}
, booktitle = {32st International Symposium on Computational Geometry (SoCG 2016)}
, editor = {S\'andor Fekete and Anna Lubiw}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Congruence+testing+of+point+sets+in+4-space.pdf}
, doi = {10.4230/LIPIcs.SOCG.2016.48}
, 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 $\Omega (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 a deterministic algorithm by Brass and Knauer (2000) and a randomized Monte Carlo algorithm by Akutsu (1998). In 4-space, they take time $O(n^2 \log n)$ and $O(n^{3/2} \log n)$, respectively. Our algorithm exploits the geometric structure and the properties of 4-dimensional space, such as angles between planes, packing numbers, Hopf fibrations, Pl\"{u}cker coordinates, the classification of Coxeter groups, and rotations in 4-space. }
}
%%% 162a:
@techreport{kr-ctps4-16t
, author = {Heuna Kim and G{\"u}nter Rote}
, title = {Congruence testing of point sets in 4 dimensions}
, year = {2016}
, month = mar
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Congruence+testing+of+point+sets+in+4+dimensions.pdf}
, eprint = {1603.07269}
}
%%% 163:
@inproceedings{mnortu-ahts-16
, author = {Tillmann Miltzow and Lothar Narins and Yoshio Okamoto and G{\"u}nter Rote and Antonis Thomas and Takeaki Uno}
, title = {Approximation and hardness for token swapping}
, year = {2016}
, pages = {185:1--185:15}
, booktitle = {Algorithms --- ESA 2016. Proc. 24th Annual European Symposium on Algorithms, Aarhus}
, editor = {Piotr Sankowski and Christos Zaroliagis}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Approximation+and+hardness+for+token+swapping.pdf}
, eprint = {1602.05150}
, doi = {10.4230/LIPIcs.ESA.2016.185}
, abstract = {We are given a graph with $n$ vertices $V=\{1,\ldots ,n\}$. On each vertex, a distict token from the set $\{T_1,\ldots ,T_n\}$ is placed. A swap is an exchange of tokens between adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that each token $T_i$ is on vertex $i$. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out $2^{o(n)}$ algorithms under the Exponential Time Hypothesis ETH. This is matched with a simple $2^{O(n\log n)}$ algorithm based on exploring the state space. We give a general $4$-approximation algorithm and show APX-hardness. Thus, there is a constant $\delta >1$ such that every polynomial-time approximation algorithm has approximation factor at least $\delta $.
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. }
}
%%% 164:
@inproceedings{hr-lgcet-16
, author = {Felix Herter and G{\"u}nter Rote}
, title = {Loopless {Gray} code enumeration and the {Tower} of {Bucharest}}
, year = {2016}
, volume = {49}
, pages = {19:1--19:19}
, booktitle = {Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016)}
, editor = {Erik D. Demaine and Fabrizio Grandoni}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Loopless+Gray+code+enumeration+and+the+Tower+of+Bucharest.pdf}
, eprint = {1604.06707}
, doi = {10.4230/LIPIcs.FUN.2016.19}
}
%%% 164a:
@article{hr-lgcet-18
, author = {Felix Herter and G{\"u}nter Rote}
, title = {Loopless {Gray} code enumeration and the {Tower} of {Bucharest}}
, journal = {Theoretical Computer Science}
, year = {2018}
, volume = {748}
, pages = {40--54}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Loopless+Gray+code+enumeration+and+the+Tower+of+Bucharest.pdf}
, doi = {10.1016/j.tcs.2017.11.017}
, 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.}
}
%%% 165:
@inproceedings{ahkprrrv-pspst-16
, author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and G{\"u}nter Rote and Andr{\'e} van Renssen and Marcel Roeloffzen and Birgit Vogtenhuber}
, title = {Packing short plane spanning trees in complete geometric graphs}
, year = {2016}
, volume = {64}
, pages = {9:1--9:12}
, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}
, editor = {Seok-Hee Hong}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, doi = {10.4230/LIPIcs.ISAAC.2016.9}
}
%%% 165a:
@article{ahkprrrv-ppsgs-19
, author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and Andr{\'e} van Renssen and Marcel Roeloffzen and G{\"u}nter Rote and Birgit Vogtenhuber}
, title = {Packing plane spanning graphs with short edges in complete geometric graphs}
, journal = {Computational Geometry, Theory and Applications}
, year = {2019}
, volume = {82}
, pages = {1--15}
, eprint = {1703.05863}
, doi = {10.1016/j.comgeo.2019.04.001}
, 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 too long when compared to the length needed to obtain a spanning tree.
We consider two different approaches. First we show an almost optimal centralized approach to extract two layers. Then we consider a distributed model in which each point can compute its adjacencies using only information about vertices at most a predefined distance away. We obtain a constant-factor approximation with respect to the length of the longest edge in the graphs. In both cases the obtained layers are plane.}
}
%%% 166:
@article{brsz-cecps-19
, author = {Pavle V. M. Blagojevi\'{c} and G{\"u}nter Rote and Johanna K. Steinmeyer and G\"unter M. Ziegler}
, title = {Convex equipartitions of colored point sets}
, journal = {Discrete and Computational Geometry}
, year = {2019}
, volume = {61}
, pages = {355--363}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Convex+equipartitions+of+colored+point+sets.pdf}
, eprint = {1705.03953}
, doi = {10.1007/s00454-017-9959-7}
, 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\v{c}l, and Valculescu (2017) and establishes a central case of their general conjecture. Our proof utilizes a result of Sober\'on (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.}
}
%%% 167:
@inproceedings{kr-olpgp-17
, author = {Boris Klemz and G{\"u}nter Rote}
, title = {Ordered level planarity and geodesic planarity}
, year = {2017}
, month = apr
, pages = {269--272}
, booktitle = {Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Ordered+level+planarity+and+its+relationship+to+geodesic+planarity,+bi-monotonicity,+and+variations+of+level+planarity.pdf}
}
%%% 167a:
@inproceedings{kr-olpgp-18
, author = {Boris Klemz and G{\"u}nter Rote}
, title = {Ordered level planarity, geodesic planarity and bi-monotonicity}
, year = {2018}
, volume = {10692}
, pages = {440--453}
, booktitle = {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}
, editor = {Frabrizio Frati and Kwan-Liu Ma}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Ordered+level+planarity+and+its+relationship+to+geodesic+planarity,+bi-monotonicity,+and+variations+of+level+planarity.pdf}
, doi = {10.1007/978-3-319-73915-1_34}
}
%%% 167b:
@article{kr-olpir-19
, author = {Boris Klemz and G{\"u}nter Rote}
, title = {Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity}
, journal = {ACM Transactions on Algorithms}
, year = {2019}
, month = oct
, volume = {15}
, issue = {4}
, number = {Article 53}
, pages = {53:1--53:25}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Ordered+level+planarity+and+its+relationship+to+geodesic+planarity,+bi-monotonicity,+and+variations+of+level+planarity.pdf}
, eprint = {1708.07428}
, doi = {10.1145/3359587}
, abstract = {We introduce and study the problem {\it 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 {\it 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 {\it T-Level Planarity}, {\it Clustered Level Planarity}, and {\it Constrained Level Planarity}. We strengthen previous hardness results and solve open questions that were posed by Fulek, Pelsmajer, Schaefer and \v{S}tefankovi\v{c} (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 {\it Manhattan Geodesic Planarity\/} is incorrect unless P=NP.}
}
%%% 168:
@article{kr-ltamw-22
, author = {Boris Klemz and G{\"u}nter Rote}
, title = {Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs}
, journal = {Algorithmica}
, year = {2022}
, volume = {84}
, pages = {1064--1080}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Linear-time+algorithms+for+maximum-weight+induced+matchings+and+minimum+chain+covers+in+convex+bipartite+graphs.pdf}
, eprint = {1711.04496}
, doi = {10.1007/s00453-021-00904-w}
, abstract = {A bipartite graph $G=(U,V,E)$ is {\it 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 {\it 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$ {\it weighted\/} edges, an induced matching of maximum total weight can be computed in optimal $O(n+m)$ time.
An {\it 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 {\it 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 {\it chain covers}. A chain cover is a covering of the edge set by {\it 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(n^2)$.}
}
%%% 169:
@article{lrz-adbds-20
, author = {Jean-Philippe Labb\'e and G{\"u}nter Rote and G\"unter M. Ziegler}
, title = {Area difference bounds for dissections of a square into an odd number of triangles}
, journal = {Experimental Mathematics}
, year = {2020}
, volume = {29}
, pages = {253--275}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Area+difference+bounds+for+dissections+of+a+square+into+an+odd+number+of+triangles.pdf}
, eprint = {1708.02891}
, doi = {10.1080/10586458.2018.1459961}
, 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.}
}
%%% 170:
@inproceedings{fr-pdcr-19
, author = {Stefan Felsner and G{\"u}nter Rote}
, title = {On primal-dual circle representations}
, year = {2019}
, volume = {69}
, pages = {8:1--8:18}
, booktitle = {Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019), San Diego}
, editor = {Jeremy Fineman and Michael Mitzenmacher}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {OpenAccess Series in Informatics (OASIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/On+primal-dual+circle+representations.pdf}
, doi = {10.4230/OASIcs.SOSA.2019.8}
, abstract = {The Koebe--Andreev--Thurston Circle Packing Theorem states that every triangulated planar graph has a circle-contact representation. The theorem has been generalized in various ways. The arguably most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. The aim of this note is to give a streamlined proof of this result.}
}
%%% 170a:
@inproceedings{fr-pdcr-18
, author = {Stefan Felsner and G{\"u}nter Rote}
, title = {On primal-dual circle representations}
, year = {2018}
, month = mar
, pages = {72:1--72:6}
, booktitle = {Abstracts of the 34th European Workshop on Computational Geometry (EuroCG 2018)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/On+primal-dual+circle+representations.pdf}
}
%%% 171:
@inproceedings{ra-ac-17
, author = {G{\"u}nter Rote and Mikkel Abrahamsen}
, title = {The algebraic conspiracy}
, year = {2017}
, volume = {14}
, pages = {1180--1182}
, booktitle = {Oberwolfach Reports}
, publisher = {European Mathematical Society - Publishing House}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+algebraic+conspiracy.pdf}
, doi = {10.4171/OWR/2017/19}
, abstract = {We consider the problem of sandwiching a polytope $\Delta $ with a given number $k$ of vertices between two nested polytopes $P$ and $Q$ in $d$ dimensions. The polytope $P$ is not necessarily full-dimensional.
Besides the question of (a) computing $\Delta $, we study the following question: (b) Assuming that the given polytopes $P$ and $Q$ are rational polytopes (polytopes with rational vertex coordinates), does it suffice to look for $\Delta $ among the rational polytopes?
This problem has several applications: (1) When $Q$ is a dilation of $P$ (or an offset of $P$), $\Delta $ can serve as a thrifty approximation of $P$. (2) The polytope nesting problem can model the nonnegative rank of a matrix, and thereby the extension complexity of polytopes, as well as other problems in statistics and communication complexity. It was in this context that question (b) was first asked.}
}
%%% 172:
@inproceedings{akkmrsx-amwmo-15
, author = {Pankaj Agarwal and Haim Kaplan and Geva Kipper and Wolfgang Mulzer and G{\"u}nter Rote and Micha Sharir and Allen Xiao}
, title = {Approximate minimum-weight matching with outliers under translation}
, year = {2015}
, volume = {123}
, pages = {26:1--26:13}
, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}
, editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, doi = {10.4230/LIPIcs.ISAAC.2018.26}
, abstract = {Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the $L_p$-norm of the tuple of the Euclidean distances between the pairs of matched points, for any $p\ge 1$, including $p=\infty $, and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.}
}
%%% 173:
@inproceedings{dfgmr-ecspg-19
, author = {Vida Dujmovi\'c and Fabrizio Frati and Daniel Gon{\c c}alves and Pat Morin and G{\"u}nter Rote}
, title = {Every collinear set in a planar graph is free}
, year = {2019}
, pages = {1521--1538}
, booktitle = {Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA19), San Diego}
, editor = {Timothy Chan}
, publisher = {SIAM}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Every+collinear+set+in+a+planar+graph+is+free.pdf}
, eprint = {1811.03432}
, doi = {10.1137/1.9781611975482.92}
}
%%% 173a:
@article{dfgmr-ecspg-21
, author = {Vida Dujmovi\'c and Fabrizio Frati and Daniel Gon{\c c}alves and Pat Morin and G{\"u}nter Rote}
, title = {Every collinear set in a planar graph is free}
, journal = {Discrete and Computational Geometry}
, year = {2021}
, volume = {65}
, pages = {999--1027}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Every+collinear+set+in+a+planar+graph+is+free.pdf}
, doi = {10.1007/s00454-019-00167-x}
, abstract = {We show that if a planar graph $G$ has a plane straight-line drawing in which a subset $S$ of its vertices are collinear, then for any set $X$ of points in the plane with $|X|=|S|$, there is a plane straight-line drawing of $G$ in which the vertices in $S$ are mapped to the points in $X$. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free.
This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings. }
}
%%% 174:
@inproceedings{r-mnmds-19
, author = {G{\"u}nter Rote}
, title = {The maximum number of minimal dominating sets in a tree}
, year = {2019}
, pages = {1201--1214}
, booktitle = {Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA19), San Diego}
, editor = {Timothy Chan}
, publisher = {SIAM}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Minimal+dominating+sets+in+a+tree:+counting,+and+enumeration,+and+extremal+results.pdf}
, doi = {10.1137/1.9781611975482.73}
}
%%% 174a:
@article{r-mdstc-19t
, author = {G{\"u}nter Rote}
, title = {Minimal dominating sets in a tree: counting, enumeration, and extremal results}
, year = {2019}
, month = mar
, eprint = {1903.04517}
, note = {submitted}
, abstract = {A tree with $n$ vertices has at most $95^{n/13}$ minimal dominating sets. The growth constant $\lambda = \radical "270370 [13]{95} \approx 1.4194908$ is best possible. It is obtained in a semi-automatic way as a kind of ``dominant eigenvalue'' of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of $\lambda $. This technique is generalizable to other counting problems, and it raises questions about the ``growth'' of a general bilinear operation.
We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions. }
}
%%% 175:
@inproceedings{r-irdp-19
, author = {G{\"u}nter Rote}
, title = {Isotonic regression by dynamic programming}
, year = {2019}
, volume = {69}
, pages = {1:1--1:18}
, booktitle = {Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019), San Diego}
, editor = {Jeremy Fineman and Michael Mitzenmacher}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {OpenAccess Series in Informatics (OASIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Isotonic+regression+by+dynamic+programming.pdf}
, doi = {10.4230/OASIcs.SOSA.2019.1}
, abstract = {For a given sequence of numbers, we want to find a monotonically increasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time $O(n\log n)$. While other algorithms with the same running time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures. }
}
%%% 176:
@inproceedings{aglr-gm-19
, author = {Mikkel Abrahamsen and Panos Giannopoulos and Maarten L\"offler and G{\"u}nter Rote}
, title = {Geometric multicut}
, year = {2019}
, volume = {132}
, pages = {9:1--9:15}
, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}
, editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Geometric+multicut:+shortest+fences+for+separating+groups+of+objects+in+the+plane.pdf}
, eprint = {1902.04045}
, doi = {10.4230/LIPIcs.ICALP.2019.9}
}
%%% 176a:
@article{aglr-gmsfs-20
, author = {Mikkel Abrahamsen and Panos Giannopoulos and Maarten L\"offler and G{\"u}nter Rote}
, title = {Geometric multicut: shortest fences for separating groups of objects in the plane}
, journal = {Discrete \& Computational Geometry}
, year = {2020}
, volume = {64}
, pages = {575--607}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Geometric+multicut:+shortest+fences+for+separating+groups+of+objects+in+the+plane.pdf}
, doi = {10.1007/s00454-020-00232-w}
, abstract = {We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest ``fence'' $F$, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if $F$ contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC $k$-CUT, where $k$ is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an $O(n^4\log ^3 n)$-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and $n$ corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a $(2-4/3k)$-approximation algorithm.}
}
%%% 177:
@article{bfghr-rpwpa-20
, author = {Imre B\'ar\'any and Matthieu Fradelizi and Xavier Goaoc and Alfredo Hubard and G{\"u}nter Rote}
, title = {Random polytopes and the wet part for arbitrary probability distributions}
, journal = {Annales Henri Lebesgue}
, year = {2020}
, volume = {3}
, pages = {701--715}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Random+polytopes+and+the+wet+part+for+arbitrary+probability+distributions.pdf}
, eprint = {1902.06519}
, doi = {10.5802/ahl.44}
, abstract = {We examine how the measure and the number of vertices of the convex hull of a random sample of $n$ points from an arbitrary probability measure in $d$-dimensional space relates to the wet part of that measure. This extends classical results for the uniform distribution from a convex set [B\'ar\'any and Larman 1988]. The lower bound of B\'ar\'any and Larman continues to hold in the general setting, but the upper bound must be relaxed by a factor of $\log n$. We show by an example that this is tight.}
}
%%% 178:
@article{bcfrs-ncpgh-19
, author = {Kevin Buchin and Man-Kwun Chiu and Stefan Felsner and G{\"u}nter Rote and Andr\'e Schulz}
, title = {The number of convex polyominoes with given height and width}
, year = {2019}
, month = mar
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+number+of+convex+polyominoes+with+given+height+and+width.pdf}
, eprint = {1903.01095}
, note = {submitted}
, abstract = {We give a new combinatorial proof for the number of convex polyominoes whose minimum enclosing rectangle has given dimensions. We also count the subclass of these polyominoes that contain the lower left corner of the enclosing rectangle (directed polyominoes). We indicate how to sample random polyominoes in these classes. As a side result, we calculate the first and second moments of the number of common points of two monotone lattice paths between two given points.}
}
%%% 179:
@article{r-crmac-20
, author = {G{\"u}nter Rote}
, title = {Characterization of the response maps of alternating-current networks}
, journal = {Electronic Journal of Linear Algebra}
, year = {2020}
, volume = {36}
, pages = {697--703}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Characterization+of+the+response+maps+of+alternating-current+networks.pdf}
, eprint = {1904.02031}
, doi = {10.13001/ela.2020.4981}
, abstract = {An {\it alternating-current network\/} is an undirected graph in which each edge is weighted by a {\it conductance\/}, a complex number with positive real part. Some nodes are designated as {\it boundary nodes\/}. The {\it response map\/} is the linear map from the vector of voltages at the boundary nodes to the vector of currents flowing into the network through these nodes.
We prove that the known necessary conditions for these response maps are sufficient, and we show how to construct an appropriate alternating-current network for a given response map.}
}
%%% 180:
@article{ekkr-gdtp-19
, author = {Annette Ebbers-Baumann and Rolf Klein and Christian Knauer and G{\"u}nter Rote}
, title = {The geometric dilation of three points}
, journal = {Journal of Computational Geometry}
, year = {2019}
, volume = {10}
, issue = {1}
, pages = {532--549}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+geometric+dilation+of+three+points.pdf}
, doi = {10.20382/jocg.v10i1a18}
, abstract = {Given three points in the plane, we construct the plane geometric network of smallest geometric dilation that connects them. The geometric dilation of a plane network is defined as the maximum dilation (distance along the network divided by Euclidean distance) between any two points on its edges. The optimum network is either a line segment, a Steiner tree, or a curve consisting of two straight edges and a segment of a logarithmic spiral.}
}
%%% 181:
@article{brs-iubgc-19
, author = {Gill Barequet and G{\"u}nter Rote and Mira Shalah}
, title = {An improved upper bound on the growth constant of polyiamonds}
, journal = {Acta Mathematica Universitatis Comenianae (AMUC)}
, year = {2019}
, volume = {88}
, pages = {429--436}
, editor = {Jaroslav Ne\v{s}et\v{r}il and Martin \v{S}koviera}
, url = {http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1205}
, abstract = {A polyiamond is an edge-connected set of cells on the triangular lattice. If $T(n)$ denotes the number of distinct (up to translation) polyiamonds made of $n$ cells. It is known that the limit $\lambda _T$ of $T(n+1) / T(n)$ (the {\it growth constant\/}) exists. In this paper, we improve considerably the best upper bound on $\lambda _T$ from 4 to 3.6108.}
}
%%% 182:
@misc{r-lcqse-19
, author = {G{\"u}nter Rote}
, title = {The largest contained quadrilateral and the smallest enclosing parallelogram of a convex polygon}
, year = {2019}
, month = jun
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+largest+contained+quadrilateral+and+the+smallest+enclosing+parallelogram+of+a+convex+polygon.pdf}
, eprint = {1905.11203}
, abstract = {We present a linear-time algorithm for finding the quadrilateral of largest area contained in a convex polygon, and we show that it is closely related to an old algorithm for the smallest enclosing parallelogram of a convex polygon.}
}
%%% 183:
@article{bjmpr-fadch-19
, author = {Julien Baste and Lars Jaffke and Tom\'a\v{s} Masa\v{r}\'{\i{}}k and Geevarghese Philip and G{\"u}nter Rote}
, title = {{FPT} algorithms for diverse collections of hitting sets}
, journal = {Algorithms}
, year = {2019}
, volume = {12}
, number = {Article 53}
, pages = {18 pages}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/FPT+algorithms+for+diverse+collections+of+hitting+sets.pdf}
, eprint = {1911.05032}
, doi = {10.3390/a12120254}
, abstract = {We study the Hitting Set and Feedback Vertex Set problems through the paradigm of finding {\it diverse\/} collections of $r$ solutions of size at most $k$ each, which has recently been introduced to the field of parameterized complexity [Baste et al., 2019]. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are FPT in $k + r$ for both diversity measures. A key ingredient in our algorithms is a problem-independent network flow formulation that, given a set of {\it base\/} solutions, computes a maximally diverse collection of solutions. This could be of independent interest. }
}
%%% 184:
@article{gkr-pmtld-23
, author = {Romain Grunert and Wolfgang K\"uhnel and G{\"u}nter Rote}
, title = {{PL} {Morse} theory in low dimensions}
, journal = {Advances in Geometry}
, year = {2023}
, volume = {23}
, pages = {135--150}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/PL+Morse+theory+in+low+dimensions.pdf}
, eprint = {1912.05054}
, doi = {10.1515/advgeom-2022-0027}
, abstract = {We discuss a piecewise linear (PL) analogue of Morse theory for PL manifolds. There are several notions of regular and critical points. A point is homologically regular if the homology does not change when passing through its level, it is strongly regular if the function can serve as one coordinate in a chart. Several criteria for strong regularity are presented. In particular we show that in low dimensions $d \le 4$ a homologically regular point on a PL $d$-manifold is always strongly regular. Examples show that this fails to hold in higher dimensions $d \ge 5$. One of our constructions involves an 8-vertex embedding of the dunce hat into a polytopal 4-sphere with 8 vertices such that a regular neighborhood is Mazur's contractible 4-manifold. Finally, decidability questions in this context are discussed.}
}
%%% 185:
@inproceedings{akr-aobni-20
, author = {Eyal Ackerman and Bal\'azs Keszegh and G{\"u}nter Rote}
, title = {An almost optimal bound on the number of intersections of two simple polygons}
, year = {2020}
, volume = {164}
, pages = {1:1--1:18}
, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}
, editor = {Sergio Cabello and Danny Z. Chen}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/An+almost+optimal+bound+on+the+number+of+intersections+of+two+simple+polygons.pdf}
, eprint = {2002.05680}
, doi = {10.4230/LIPIcs.SOCG.2020.1}
}
%%% 185a:
@article{akr-aobni-22
, author = {Eyal Ackerman and Bal\'azs Keszegh and G{\"u}nter Rote}
, title = {An almost optimal bound on the number of intersections of two simple polygons}
, journal = {Discrete and Computational Geometry}
, year = {2022}
, volume = {68}
, pages = {1049--1077}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/An+almost+optimal+bound+on+the+number+of+intersections+of+two+simple+polygons.pdf}
, doi = {10.1007/s00454-022-00438-0}
, abstract = {What is the maximum number of intersections of the boundaries of a simple $m$-gon and a simple $n$-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of $m$ and $n$ is even: If both $m$ and $n$ are even, then every pair of sides may cross and so the answer is $mn$. If exactly one polygon, say the $n$-gon, has an odd number of sides, it can intersect each side of the $m$-gon at most $n-1$ times; hence there are at most $mn-m$ intersections. It is not hard to construct examples that meet these bounds. If both $m$ and $n$ are odd, the best known construction has $mn-(m+n)+3$ intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $mn-(m + \delimiter "4264306 \frac {n}{6} \delimiter "5265307 )$, for $m \ge n$. We prove a new upper bound of $mn-(m+n)+C$ for some constant $C$, which is optimal apart from the value of $C$.}
}
%%% 186:
@article{brt-osfgv-24
, author = {Csilla Bujt\'as and G{\"u}nter Rote and Zsolt Tuza}
, title = {Optimal strategies in fractional games: vertex cover and domination}
, journal = {Ars Mathematica Contemporanea}
, year = {2024}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimal+strategies+in+fractional+games:+vertex+cover+and+domination.pdf}
, eprint = {2105.03890}
, note = {to appear}
, abstract = {In a hypergraph with vertex set $V$ and edge set $E$, a real-valued function $f\colon V \to [0, 1]$ is a fractional transversal if $\sum _{v\in e} f(v) \ge 1$ for every edge $e \in E$. Its size is $|f| := \sum _{v \in V} f(v)$, and the fractional transversal number is the smallest possible $|f|$. We consider a game scenario where two players with opposite goals construct a fractional transversal incrementally, trying to minimize and maximize $|f|$, respectively. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.}
}
%%% 187:
@inproceedings{abbor-nctp-21
, author = {Andrei Asinowski and Gill Barequet and Gil Ben-Shachar and Martha Carolina Osegueda and G{\"u}nter Rote}
, title = {On the number of compositions of two polycubes}
, year = {2021}
, pages = {71--77}
, booktitle = {Extended Abstracts EuroComb 2021}
, editor = {Jaroslav Ne{\v{s}}et{\v{r}}il and Guillem Perarnau and Juanjo Ru{\'e} and Oriol Serra}
, publisher = {Springer-Verlag}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/On+the+number+of+compositions+of+two+polycubes.pdf}
, doi = {10.1007/978-3-030-83823-2_12}
, abstract = {We provide almost tight bounds on the minimum and maximum possible numbers of compositions of two polycubes of given total size, in two and higher dimensions. In the plane, we reach a near-quadratic number of compositions. We also provide an efficient algorithm (with some trade-off between time and space) for computing the number of composition of two given polyominoes (or polycubes).}
}
%%% 188:
@inproceedings{ntwmmlr-rpfca-23
, author = {Phoebe de Nooijer and Soeren Terziadis and Alexandra Weinberger and Zuzana Mas\'arov\'a and Tamara Mchedlidze and Maarten L\"offler and G{\"u}nter Rote}
, title = {Removing popular faces in curve arrangements}
, year = {2023}
, volume = {14466}
, pages = {18--33}
, booktitle = {Graph Drawing and Network Visualization. GD 2023, Proceedings of the 31th International Symposium on Graph Drawing and Network Visualization, Palermo, September 2023, Revised Selected Papers, Part II}
, editor = {Michael A. Bekos and Markus Chimani}
, publisher = {Springer-Verlag}
, series = {Lecture Notes in Computer Science}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Removing+popular+faces+in+curve+arrangements.pdf}
, eprint = {2202.12175}
, doi = {10.1007/978-3-031-49275-4_2}
, abstract = {A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate popular faces in an arrangement by inserting a single additional curve. This turns out to be already NP-hard; however, we present a probabilistic FPT-approach in the number of such faces.}
}
%%% 188a:
@article{nnwmmlr-rpfca-24
, author = {Phoebe de Nooijer and Soeren Nickel and Alexandra Weinberger and Zuzana Mas\'arov\'a and Tamara Mchedlidze and Maarten L\"offler and G{\"u}nter Rote}
, title = {Removing popular faces in curve arrangements}
, journal = {Journal of Graph Algorithms and Applications}
, year = {2024}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Removing+popular+faces+in+curve+arrangements.pdf}
, note = {submitted}
}
%%% 188b:
@inproceedings{nnwmmlr-rpfca-22
, author = {Phoebe de Nooijer and Soeren Nickel and Alexandra Weinberger and Zuzana Mas\'arov\'a and Tamara Mchedlidze and Maarten L\"offler and G{\"u}nter Rote}
, title = {Removing popular faces in curve arrangements by inserting one more curve}
, year = {2022}
, month = mar
, pages = {38:1--38:8}
, booktitle = {Abstracts of the 38th European Workshop on Computational Geometry (EuroCG 2022)}
, editor = {Emilio Di Giacomo and Fabrizio Montecchiani}
, url = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf}
}
%%% 189:
@article{rr-tgu4d-22
, author = {Laith Rastanawi and G{\"u}nter Rote}
, title = {Towards a geometric understanding of the 4-dimensional point groups}
, year = {2022}
, month = may
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Towards+a+geometric+understanding+of+the+4-dimensional+point+groups.pdf}
, eprint = {2205.04965}
, abstract = {We classify the finite groups of orthogonal transformations in 4-space, and we study these groups from the viewpoint of their geometric action, using polar orbit polytopes. For one type of groups (the toroidal groups), we develop a new classification based on their action on an invariant torus, while we rely on classic results for the remaining groups.
As a tool, we develop a convenient parameterization of the oriented great circles on the 3-sphere, which leads to (oriented) Hopf fibrations in a natural way.}
}
%%% 190:
@article{r-g-23
, author = {G{\"u}nter Rote}
, title = {The {Generalized Combinatorial Laso\'n--Alon--Zippel--Schwartz Nullstellensatz Lemma}}
, year = {2023}
, month = may
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/The+Generalized+Combinatorial+Lason-Alon-Zippel-Schwartz+Nullstellensatz+Lemma.pdf}
, eprint = {2305.10900}
, abstract = {We survey a few strengthenings and generalizations of the Schwartz--Zippel Lemma and Alon's Combinatorial Nullstellensatz. These lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges.}
}
%%% 191:
@inproceedings{rrs-gpp-24
, author = {G{\"u}nter Rote and Moritz R\"uber and Morteza Saghafian}
, title = {Grid peeling of parabolas}
, year = {2024}
, volume = {293}
, pages = {70:1--70:18}
, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}
, editor = {Wolfgang Mulzer and Jeff M. Phillips}
, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik}
, series = {Leibniz International Proceedings in Informatics (LIPIcs)}
, url = {http://page.mi.fu-berlin.de/rote/Papers/pdf/Grid+peeling+of+parabolas.pdf}
, eprint = {2402.15787}
, note = {to appear}
, abstract = {Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the {\it affine curve-shortening flow}, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.}
}