跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

Consider a convex polyhedral robot BB that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in R3\mathbb R^3. The "free space" F\mathcal F of BB is the set of all positions in which BB is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of O(n2log⁡n)O(n^2\log n) for the combinatorial complexity (number of vertices, edges, and faces) of F\mathcal F, where nn is the total complexity of the obstacles, and the complexity of BB is assumed constant. Halperin and Yap (1993) showed that, if BB is either a box or a "flat" convex polygon, then a tighter bound of O(n2α(n))O(n^2α(n)) holds. Here α(n)α(n) is the inverse Ackermann function. In this paper we prove that if BB is a box, then the complexity of F\mathcal F is O(n2)O(n^2). Furthermore, if BB is a convex polygon whose edges come in parallel pairs, then the complexity of F\mathcal F is O(n2)O(n^2) as well. These results settle the question of the asymptotical worst-case complexity of F\mathcal F for a box, as well as for all convex polygons.

作者备注:19 pages, 13 figures

AI 论文解读

基于摘要 · 非全文审阅

作者证明在 R^3 中平移盒体(以及边成平行对的凸多边形)的自由空间组合复杂度为 O(n^2),从而解决盒体及所有凸多边形的渐近最坏情况复杂度问题。

正在读取账号与研究记录…

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 BB that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in R3\mathbb R^3. The "free space" F\mathcal F of BB is the set of all positions in which BB is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of O(n2log⁡n)O(n^2\log n) for the combinatorial complexity (number of vertices, edges, and faces) of F\mathcal F, where nn is the total complexity of the obstacles, and the complexity of BB is assumed constant. Halperin and Yap (1993) showed that, if BB is either a box or a "flat" convex polygon, then a tighter bound of O(n2α(n))O(n^2α(n)) holds. Here α(n)α(n) is the inverse Ackermann function. In this paper we prove that if BB is a box, then the complexity of F\mathcal F is O(n2)O(n^2). Furthermore, if BB is a convex polygon whose edges come in parallel pairs, then the complexity of F\mathcal F is O(n2)O(n^2) as well. These results settle the question of the asymptotical worst-case complexity of F\mathcal F for a box, as well as for all convex polygons.

查看此版本解读 →查看此版本原文 ↗