论文标题
用线段和多边形路径刺伤球
Stabbing balls with line segments and polygonal paths
论文作者
论文摘要
我们研究了$ n $ balls（任意和可能不同的半径，另一个没有球）刺伤的问题，$ \ mathbb {r}^d $，$ d \ geq 3 $，带有定向线段或（定向）的多边形曲线。在这里，线段分别以多边形曲线访问（相交）序列顺序给定的球序列。我们提出了一种确定性算法，该算法决定是否存在一个线段刺入给定的球序列，以便在时间$ o（n^{4d-2} \ log n）$中。由于包含这些线段的区域的描述复杂性，我们无法将此算法扩展到实际计算一个算法。我们通过设计一种随机算法来为有序线段刺伤问题的轻松变体设计一种随机算法来避免这一障碍，该算法是基于上述决策算法的中心见解。我们进一步表明，Guibas等人可以将该算法插入算法方案中，从而产生了最小链路有序的刺激路径问题的放松变体的算法，该算法与链接数量相对于近似值2。我们以后两种算法的实验评估结束，显示了实际的适用性。
We study the problem of ordered stabbing of $n$ balls (of arbitrary and possibly different radii, no ball contained in another) in $\mathbb{R}^d$, $d \geq 3$, with either a directed line segment or a (directed) polygonal curve. Here, the line segment, respectively polygonal curve, shall visit (intersect) the given sequence of balls in the order of the sequence. We present a deterministic algorithm that decides whether there exists a line segment stabbing the given sequence of balls in order, in time $O(n^{4d-2} \log n)$. Due to the descriptional complexity of the region containing these line segments, we can not extend this algorithm to actually compute one. We circumvent this hurdle by devising a randomized algorithm for a relaxed variant of the ordered line segment stabbing problem, which is built upon the central insights from the aforementioned decision algorithm. We further show that this algorithm can be plugged into an algorithmic scheme by Guibas et al., yielding an algorithm for a relaxed variant of the minimum-link ordered stabbing path problem that achieves approximation factor 2 with respect to the number of links. We conclude with experimental evaluations of the latter two algorithms, showing practical applicability.
