关于 R^3 中平移盒体自由空间复杂度
On the complexity of the free space of a translating box in R^3
Gabriel Nivasch
AI 速读 基于摘要
作者证明在 R^3 中平移盒体(以及边成平行对的凸多边形)的自由空间组合复杂度为 O(n^2),从而解决盒体及所有凸多边形的渐近最坏情况复杂度问题。
cs.CG
查看原文摘要
Consider a convex polyhedral robot $B$ that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in $\mathbb R^3$. The "free space" $\mathcal F$ of $B$ is the set of all positions in which $B$ is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of $O(n^2\log n)$ for the combinatorial complexity (number of vertices, edges, and faces) of $\mathcal F$, where $n$ is the total complexity of the obstacles, and the complexity of $B$ is assumed constant. Halperin and Yap (1993) showed that, if $B$ is either a box or a "flat" convex polygon, then a tighter bound of $O(n^2α(n))$ holds. Here $α(n)$ is the inverse Ackermann function. In this paper we prove that if $B$ is a box, then the complexity of $\mathcal F$ is $O(n^2)$. Furthermore, if $B$ is a convex polygon whose edges come in parallel pairs, then the complexity of $\mathcal F$ is $O(n^2)$ as well. These results settle the question of the asymptotical worst-case complexity of $\mathcal F$ for a box, as well as for all convex polygons.