Abstract   We study the space of free translations of a box amidst polyhedral obstacles with  n  vertices. We show that the combinatorial complexity of this space is O( n  2  α ( n )), where  α ( n ) is the inverse Ackermann function. Our bound is within an  α ( n ) factor off the lower bound, and it constitutes an improvement of almost an order of magnitude over the best previously known (and naive) bound for this problem, O( n  3 ). For the case of a convex polygon of fixed (constant) size translating in the same setting (namely, a two-dimensional polygon translating in three-dimensional space), we show a tight bound  Θ ( n  2  α ( n )) on the complexity of the free space.
['Dan Halperin', 'Chee-Keng Yap']
Combinatorial complexity of translating a box in polyhedral 3-space