@inproceedings{b43647733a65487295c82dd59bf24f3d,
title = "Combinatorial complexity of translating a box in polyhedral 3-space",
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(n2α(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(n3).",
author = "Dan Halperin and Yap, {Chee Keng}",
year = "1993",
doi = "10.1145/160985.160992",
language = "English (US)",
isbn = "0897915828",
series = "Proceedings of the 9th Annual Symposium on Computational Geometry",
publisher = "Publ by ACM",
pages = "29--37",
booktitle = "Proceedings of the 9th Annual Symposium on Computational Geometry",
note = "Proceedings of the 9th Annual Symposium on Computational Geometry ; Conference date: 19-05-1993 Through 21-05-1993",
}