Let $P$ be a polytope given by some half-space description: $P=\{x\in\mathbb{R}^n: Ax\leq b\}$ for some $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m$, $m\geq n$. Assume that $x_0\in P$ for some given $x_0$ (in particular, $P\neq\emptyset$). What is the complexity of finding one (i.e., any) vertex of $P$?

Obviously, we can find a vertex in polynomial time by using Linear Programming, by optimizing over $P$ in an arbitrary direction, but I guess we can do better than that. For example, I think it might be possible to shoot from $x_0$ in an arbitrary direction until a face is hit (which can be done in $O(mn)$), and then proceed inductively within this face. To do this, I think we need to compute a basis for the affine hull of that face, which also certainly requires something like $O(nm)$. Since we need $n$ iterations, that would be a $O(n^2m)$ algorithm, can't we do better?