论文标题
具有可变末端段的明显探针的可行轨迹的表征和计算
Characterization and Computation of Feasible Trajectories for an Articulated Probe with a Variable-Length End Segment
论文作者
论文摘要
在飞机上建模了一个清晰的探测器，为两个线段，$ ab $和$ bc $，以$ b $的价格加入，$ ab $很长，而$ bc $的一些小长度$ r $。我们研究了一个涉及铰接的两段探测器的轨迹计划问题，可以自定义长度$ r $ $ r $ $ r $。考虑一个简单的多边形障碍物的套装$ p $，总共有$ n $顶点，一个位于自由空间中的目标点$ t $，以至于$ t $无法看到无限，而一个圆圈$ s $以$ t $ enclate $ p $。该探测最初居住在$ s $之外，$ ab $和$ bc $是colinear，并且仅限于以下移动序列：$ abc $ $ abc $ in $ s $的直线插入，然后旋转$ bc $ agure $ b $。目的是为探针计算可行的避免障碍物的轨迹，以便在移动序列之后，$ c $与$ t $重合。 我们证明，对于$ n $线段的障碍物，可以在$ o（n^{2+ε}）$ time中使用$ o（n^{2+ε}）$ space（n^{2+ε}）$ time，对于任何常量$ε> 0 $ $（n^{2+ε}）$ space的最小长度$ r $。此外，我们证明所有值$ r $都存在可行的探针轨迹的形式$ o（n^2）$间隔，并且可以使用$ o（n^{5/2}）$ time使用$ o（n^{2+ε}）$ SPACE计算。我们还表明，对于给定的$ r $，铰接探针的可行轨迹空间的特征是简单的复杂性$ o（n^2）$，可以用$ o（n^2）$ time构建。为了获得解决方案，我们为几何相交和空虚查询问题的许多有趣的变体设计有效的数据结构。
An articulated probe is modeled in the plane as two line segments, $ab$ and $bc$, joined at $b$, with $ab$ being very long, and $bc$ of some small length $r$. We investigate a trajectory planning problem involving the articulated two-segment probe where the length $r$ of $bc$ can be customized. Consider a set $P$ of simple polygonal obstacles with a total of $n$ vertices, a target point $t$ located in the free space such that $t$ cannot see to infinity, and a circle $S$ centered at $t$ enclosing $P$. The probe initially resides outside $S$, with $ab$ and $bc$ being collinear, and is restricted to the following sequence of moves: a straight line insertion of $abc$ into $S$ followed by a rotation of $bc$ around $b$. The goal is to compute a feasible obstacle-avoiding trajectory for the probe so that, after the sequence of moves, $c$ coincides with $t$. We prove that, for $n$ line segment obstacles, the smallest length $r$ for which there exists a feasible probe trajectory can be found in $O(n^{2+ε})$ time using $O(n^{2+ε})$ space, for any constant $ε> 0$. Furthermore, we prove that all values $r$ for which a feasible probe trajectory exists form $O(n^2)$ intervals, and can be computed in $O(n^{5/2})$ time using $O(n^{2+ε})$ space. We also show that, for a given $r$, the feasible trajectory space of the articulated probe can be characterized by a simple arrangement of complexity $O(n^2)$, which can be constructed in $O(n^2)$ time. To obtain our solutions, we design efficient data structures for a number of interesting variants of geometric intersection and emptiness query problems.
