The geometry of cube complexes and the complexity of their fundamental groups (Q1384312)

The main result of this paper is that if \(G\) is a group acting effectively, cellularly, properly discontinuously, and cocompactly on a simply connected, nonpositively curved cube complex, then there is a synchronously biautomatic structure on \(G\). This unifies and generalizes a number of cases which had previously been shown to be automatic or biautomatic, such as free groups, free abelian groups, right angled Coxeter groups, right angled Artin groups, word hyperbolic Coxeter groups, \(T(4)\)-\(C(4)\)-\(P\) small cancellation groups, and many 3-manifold groups. The proof of the main result involves the development of some geometric properties of hyperplanes in simply-connected nonpositively curved cube complexes, and the definition of a ``normal cube-path'' connecting two vertices. The latter is a path that moves as diagonally as possible through the cube structure. The authors show that normal cube-paths satisfy the \(k\)-fellow traveler property, in fact that they satisfy it for \(k=1\).