  Oriented matroids (often called order types) are combinatorial structures
that generalize point configurations, vector configurations, hyperplane
arrangements, polyhedra, linear programs, and directed graphs. Oriented
matroids have played a key role in combinatorics, computational geometry, and
optimization. This paper surveys prior work and presents an update on the
search for bounds on the diameter of the cocircuit graph of an oriented
matroid.
  We review the diameter problem and show the diameter bounds of general
oriented matroids reduce to those of uniform oriented matroids. We give the
latest exact bounds for oriented matroids of low rank and low corank, and for
all oriented matroids with up to nine elements (this part required a large
computer-based proof). The motivation for our investigations is the complexity
of the simplex method and the criss-cross method. For arbitrary oriented
matroids, we present an improvement to a quadratic bound of Finschi. Our
discussion highlights two very important conjectures related to the polynomial
Hirsch conjecture for polytope diameters.
