### Abstract

We study the space of free translations of a box amidst polyhedral obstacles with n features. 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}).

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

Title of host publication | Proceedings of the 9th Annual Symposium on Computational Geometry |

Publisher | Publ by ACM |

Pages | 29-37 |

Number of pages | 9 |

ISBN (Print) | 0897915828, 9780897915823 |

DOIs | |

State | Published - 1993 |

Event | Proceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA Duration: May 19 1993 → May 21 1993 |

### Publication series

Name | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|

### Other

Other | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|---|

City | San Diego, CA, USA |

Period | 5/19/93 → 5/21/93 |

### ASJC Scopus subject areas

- Engineering(all)

## Cite this

Halperin, D., & Yap, C. K. (1993). Combinatorial complexity of translating a box in polyhedral 3-space. In

*Proceedings of the 9th Annual Symposium on Computational Geometry*(pp. 29-37). (Proceedings of the 9th Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/160985.160992