Castles in the air revisited (Q1334929)

Let \(T\) be a set of \(n\) \((d-1)\)-simplices in \(\mathbb{R}^ d\), decomposing the space into open \(d\)-dimensional cells and into relatively open \(k\)- faces, \(0\leq k\leq d-1\). The structure defined by these cells and faces is said to be the arrangement \(A(T)\) of \(T\). The authors show that the maximum possible number of boundary faces of any cell in \(A(T)\) is \(O(n^{d-1}\log n)\), which is the first nontrivial upper bound for arbitrary \(d\); it comes within a logarithmic factor of the best-known lower bound of \(\Omega (n^{d-1} \alpha(n))\), where \(\alpha(n)\) denotes the inverse Ackermann function. The paper contains further results, such as the total number \(O(n^{d-1} \log n)\) of vertices incident to the same cell on more than one ``side'', or bounds on the complexity of \(m\) distinct cells in \(A(T)\). All these results have applications to motion planning of mechanical systems subject to piecewise-linear ``collision- constraints'', such as e.g. a system of polyhedral bodies translating independently in a polyhedral environment, avoiding the obstacles and each other. Moreover, the authors discuss the main challenge lying further ahead in this direction, namely the extension to the general case of motion planning considering collections of \(n\) constraint surfaces of bounded algebraic degree in \(d\)-space, with \(d\) as the number of degrees of freedom of the moving system.