TY - GEN

T1 - Castles in the air revisited

AU - Aronov, Boris

AU - Sharir, Micha

PY - 1992

Y1 - 1992

N2 - We show that the total number of faces bounding any single cell in an arrangement of n (d - 1)-simplices in IRd is O(nd-1 log n), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We then extend our analysis technique to derive other results on complexity in simplex arrangements. For example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one 'side,' is O(nd-1 log n). We also show that the number of repetitions of a 'k-flap,' formed by intersecting d-k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is O(nd-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.

AB - We show that the total number of faces bounding any single cell in an arrangement of n (d - 1)-simplices in IRd is O(nd-1 log n), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We then extend our analysis technique to derive other results on complexity in simplex arrangements. For example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one 'side,' is O(nd-1 log n). We also show that the number of repetitions of a 'k-flap,' formed by intersecting d-k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is O(nd-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.

UR - http://www.scopus.com/inward/record.url?scp=0026998103&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026998103&partnerID=8YFLogxK

U2 - 10.1145/142675.142710

DO - 10.1145/142675.142710

M3 - Conference contribution

AN - SCOPUS:0026998103

SN - 0897915178

SN - 9780897915175

T3 - Eighth Annual Symposium On Computational Geometry

SP - 146

EP - 156

BT - Eighth Annual Symposium On Computational Geometry

PB - Publ by ACM

T2 - Eighth Annual Symposium On Computational Geometry

Y2 - 10 June 1992 through 12 June 1992

ER -