← 研踪 PaperTrailarXiv:2510.22386 · v4
On the complexity of the free space of a translating box in R^3
关于 R^3 中平移盒体自由空间复杂度
首次提交 2025-10-26 02:07
版本更新 2026-11-06 01:17
雷达观测 2026-11-06 13:11
摘要
Consider a convex polyhedral robot that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in . The "free space" of is the set of all positions in which is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of for the combinatorial complexity (number of vertices, edges, and faces) of , where is the total complexity of the obstacles, and the complexity of is assumed constant. Halperin and Yap (1993) showed that, if is either a box or a "flat" convex polygon, then a tighter bound of holds. Here is the inverse Ackermann function. In this paper we prove that if is a box, then the complexity of is . Furthermore, if is a convex polygon whose edges come in parallel pairs, then the complexity of is as well. These results settle the question of the asymptotical worst-case complexity of for a box, as well as for all convex polygons.
作者备注:19 pages, 13 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v4 · 2026-11-06 01:17 · 最新观测版本
On the complexity of the free space of a translating box in R^3
Consider a convex polyhedral robot that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in . The "free space" of is the set of all positions in which is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of for the combinatorial complexity (number of vertices, edges, and faces) of , where is the total complexity of the obstacles, and the complexity of is assumed constant. Halperin and Yap (1993) showed that, if is either a box or a "flat" convex polygon, then a tighter bound of holds. Here is the inverse Ackermann function. In this paper we prove that if is a box, then the complexity of is . Furthermore, if is a convex polygon whose edges come in parallel pairs, then the complexity of is as well. These results settle the question of the asymptotical worst-case complexity of for a box, as well as for all convex polygons.
查看此版本解读 →查看此版本原文 ↗