论文标题
计算在三个维度的铰接探针的可行轨迹
Computing Feasible Trajectories for an Articulated Probe in Three Dimensions
论文作者
论文摘要
考虑一个输入，该输入由$ \ Mathbb {r}^3 $的一组$ n $分离三角障碍物和一个自由空间中的目标点$ t $组成，全部由以$ t $为$ t $的大范围$ s $ s $ s $ s $ s $ s。铰接式探测器被建模为两行段$ ab $和$ b $连接的$ bc $。 $ ab $的长度可以等于或大于$ r $，而$ bc $的长度为给定的长度$ r \ leq r $。该探针最初位于$ s $之外，假设有未明确的配置，其中$ ab $和$ bc $是collinear，而$ b \ in AC $。目的是找到可行的（避开障碍物）探针轨迹以达到$ t $，条件是探针受到以下动作顺序的约束，这是将未明确的探针的直线插入到$ s $中的直线插入，可能是$ bc $ bc $ bc $ bc $ to $ bc $ to $ $π/2 $ co co c $ co c $ co co co co co c $ c $ c。 我们证明，如果存在可行的探测轨迹，则必须存在一组极端可行的轨迹。通过仔细的病例分析，我们表明这些极端轨迹可以由$ O（n^4）$组合事件表示。我们提出了一种解决方案方法，该方法列举并验证了这些组合事件，以在总体$ o（n^{4+ε}）$ time中使用$ o（n^{4+ε}）$ space，对于任何常数$ε> 0 $。考虑到每个组合事件都可以独立于其他组合，可以生成和验证每个组合事件，因此枚举算法高度平行。在得出解决方案的过程中，我们设计了第一个数据结构，以解决三维空间中多面体障碍之间的圆形部门空虚查询的特殊实例，并为相应的空虚查询问题提供了简化的数据结构。
Consider an input consisting of a set of $n$ disjoint triangular obstacles in $\mathbb{R}^3$ and a target point $t$ in the free space, all enclosed by a large sphere $S$ of radius $R$ centered at $t$. An articulated probe is modeled as two line segments $ab$ and $bc$ connected at point $b$. The length of $ab$ can be equal to or greater than $R$, while $bc$ is of a given length $r \leq R$. The probe is initially located outside $S$, assuming an unarticulated configuration, in which $ab$ and $bc$ are collinear and $b \in ac$. The goal is to find a feasible (obstacle-avoiding) probe trajectory to reach $t$, with the condition that the probe is constrained by the following sequence of moves -- a straight-line insertion of the unarticulated probe into $S$, possibly followed by a rotation of $bc$ at $b$ for at most $π/2$ radians, so that $c$ coincides with $t$. We prove that if there exists a feasible probe trajectory, then a set of extremal feasible trajectories must be present. Through careful case analysis, we show that these extremal trajectories can be represented by $O(n^4)$ combinatorial events. We present a solution approach that enumerates and verifies these combinatorial events for feasibility in overall $O(n^{4+ε})$ time using $O(n^{4+ε})$ space, for any constant $ε> 0$. The enumeration algorithm is highly parallel, considering that each combinatorial event can be generated and verified for feasibility independently of the others. In the process of deriving our solution, we design the first data structure for addressing a special instance of circular sector emptiness queries among polyhedral obstacles in three dimensional space, and provide a simplified data structure for the corresponding emptiness query problem in two dimensions.
