### Abstract

We show that the total number of faces bounding any single cell in an arrangement of n (d - 1)-simplices in IR^{d} is O(n^{d-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(n^{d-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(n^{d-1} log^{2} 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.

Original language | English (US) |
---|---|

Title of host publication | Eighth Annual Symposium On Computational Geometry |

Publisher | Publ by ACM |

Pages | 146-156 |

Number of pages | 11 |

ISBN (Print) | 0897915178, 9780897915175 |

DOIs | |

State | Published - 1992 |

Event | Eighth Annual Symposium On Computational Geometry - Berlin, Ger Duration: Jun 10 1992 → Jun 12 1992 |

### Publication series

Name | Eighth Annual Symposium On Computational Geometry |
---|

### Other

Other | Eighth Annual Symposium On Computational Geometry |
---|---|

City | Berlin, Ger |

Period | 6/10/92 → 6/12/92 |

### ASJC Scopus subject areas

- Engineering(all)

## Fingerprint Dive into the research topics of 'Castles in the air revisited'. Together they form a unique fingerprint.

## Cite this

*Eighth Annual Symposium On Computational Geometry*(pp. 146-156). (Eighth Annual Symposium On Computational Geometry). Publ by ACM. https://doi.org/10.1145/142675.142710