1. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:
Monotone paths in planar convex subdivisions and polytopes
In: Discrete Geometry and Optimization, Editors: Károly
Bezdek, Antoine Deza, and Yinyu Ye, Fields Institute Communications,
Vol. 69, Springer-Verlag, 2013,
pp. 79–104. doi:10.1007/978-3-319-00200-2_6
2. Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth:
Monotone paths in planar convex subdivisions
In: Computing and Combinatorics. Proceedings of the 18th
Annual International Computing and Combinatorics Conference (COCOON
2012), Sidney, August 2012. Editors: Joachim Gudmundsson, Julian
Mestre, and Taso Viglas. Lecture Notes in Computer Science,
Vol. 7434, Springer-Verlag, 2012, pp. 240–251. doi:10.1007/978-3-642-32241-9_21
3. Günter Rote:
Long monotone paths in convex subdivisions
In: Abstracts of the 27th European Workshop on Computational Geometry
(EuroCG'11), Morschach, Switzerland, March 2011, pp. 183–184, Editor:
Michael Hoffmann.
This is a preliminary version with partial results.
Abstract
Consider a connected subdivision of the plane into n convex
faces where every vertex is incident to at most d edges.
Then, starting from every vertex there is a path with at least
Ω(logdn) edges that is monotone in
some direction. This bound is best possible. Consider now a connected
subdivision of the plane into n convex faces where exactly
k faces are unbounded. Then, there is a path with at least
Ω(log(n/k)/log log(n/k))
edges that is monotone in some direction. This bound is also best possible.
Our methods are constructive and lead to efficient algorithms for computing
monotone paths of lengths specified above. In 3-space, we show
that for every n>3, there exists a polytope
with
n vertices, bounded vertex degrees, and triangular faces such
that every monotone path on its 1-skeleton has at most
O(log2n) edges. We also construct a polytope
with n vertices, and triangular faces, (with unbounded degree
however), such that every monotone path on its 1-skeleton has
at most O(log n) edges.
Last update: June 22, 2012.