Monotone Paths in Geometric Triangulations

Abstract

(I) We prove that the (maximum) number of monotone paths in a geometric triangulation of $n$ points in the plane is $O(1.7864^n)$. This improves an earlier upper bound of $O(1.8393^n)$; the current best lower bound is $\Omega (1.7003^n)$. (II) Given a planar geometric graph $G$ with $n$ vertices, we show that the number of monotone paths in $G$ can be computed in $O(n^2)$ time.

50 pages, 35 figures

References in corpus (2)

• On Simplex Pivoting Rules and Complexity Theory
• How Many Potatoes are in a Mesh?