Long Monotone Paths in Convex Subdivisions
Günter Rote · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2011
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 Ω(log d n) edges through this vertex that is monotone in some direction. This bound is best possible. for your paper. 1