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

Monotone paths in planar convex subdivisions and polytopes

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

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

Monotone paths in planar convex subdivisions

In: Computing and Combinatorics. Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON 2012), Sidney, August 2012. Editors: Joachim Gudmundsson, Julian Mestre, and Taso Viglas. Lecture Notes in Computer Science, Vol. 7434, Springer-Verlag, 2012, pp. 240–251. doi:10.1007/978-3-642-32241-9_21

3. Günter Rote:

Long monotone paths in convex subdivisions

In: Abstracts of the 27th European Workshop on Computational Geometry (EuroCG'11), Morschach, Switzerland, March 2011, pp. 183–184, Editor: Michael Hoffmann. This is a preliminary version with partial results.

Abstract

Consider a connected subdivision of the plane into n convex faces where every vertex is incident to at most d edges. Then, starting from every vertex there is a path with at least Ω(logdn) edges that is monotone in some direction. This bound is best possible. Consider now a connected subdivision of the plane into n convex faces where exactly k faces are unbounded. Then, there is a path with at least Ω(log(n/k)/log log(n/k)) edges that is monotone in some direction. This bound is also best possible. Our methods are constructive and lead to efficient algorithms for computing monotone paths of lengths specified above. In 3-space, we show that for every n>3, there exists a polytope with n vertices, bounded vertex degrees, and triangular faces such that every monotone path on its 1-skeleton has at most O(log2n) edges. We also construct a polytope with n vertices, and triangular faces, (with unbounded degree however), such that every monotone path on its 1-skeleton has at most O(log n) edges.

  slides of a talk in Lausanne (2012)   pdf file (gzipped)
other papers about this subject
Last update: June 22, 2012.