  We study the simplex method over polyhedra satisfying certain "discrete
curvature" lower bounds, which enforce that the boundary always meets vertices
at sharp angles. Motivated by linear programs with totally unimodular
constraint matrices, recent results of Bonifas et al (SOCG 2012), Brunsch and
R\"oglin (ICALP 2013), and Eisenbrand and Vempala (2014) have improved our
understanding of such polyhedra.
  We develop a new type of dual analysis of the shadow simplex method which
provides a clean and powerful tool for improving all previously mentioned
results. Our methods are inspired by the recent work of Bonifas and the first
named author (SODA 2015), who analyzed a remarkably similar process as part of
an algorithm for the Closest Vector Problem with Preprocessing.
  For our first result, we obtain a constructive diameter bound of
$O(\frac{n^2}{\delta} \ln \frac{n}{\delta})$ for $n$-dimensional polyhedra with
curvature parameter $\delta \in [0,1]$. For the class of polyhedra arising from
totally unimodular constraint matrices, this implies a bound of $O(n^3 \ln n)$.
For linear optimization, given an initial feasible vertex, we show that an
optimal vertex can be found using an expected $O(\frac{n^3}{\delta} \ln
\frac{n}{\delta})$ simplex pivots, each requiring $O(m n)$ time to compute. An
initial feasible solution can be found using $O(\frac{m n^3}{\delta} \ln
\frac{n}{\delta})$ pivot steps.
