We show that the total number of faces bounding any one cell in an arr
angement of n (d - 1)-simplices in R(d) is O(n(d-1) log n), thus almos
t settling a conjecture of Pach and Sharir. We present several applica
tions of this result, mainly to translational motion planning in polyh
edral environments. We then extend our analysis to derive other result
s on complexity in arrangements of simplices. For example, we show tha
t in such an arrangement the total number of vertices incident to the
same cell on more than one ''side'' is O(n(d-1) log n). We also show t
hat the number of repetitions of a ''k-flap,'' formed by intersecting
d - k given simplices, along the boundary of the same cell, summed ove
r all cells and all k-flaps, is O(n(d-1) log2 n). We use this quantity
, which we call the excess of the arrangement, to derive bounds on the
complexity of m distinct cells of such an arrangement.