Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection

Let ${\bf \Gamma }$ be a collection of n (possibly intersecting) “red” Jordan arcs of some simple shape in the plane and let ${\bf \Gamma }^{\prime}$ be a similar collection of m “blue” arcs. Several efficient algorithms are presented for detecting an intersection between an arc of ${\bf \Gamma }$ and an arc of ${\bf \Gamma }^{\prime}$. (i) If the arcs of ${\bf \Gamma }^{\prime}$ form the boundary of a simply connected region, then the following can be detected: a “red-blue” intersection in time $O(\lambda _s (m) \log ^2 m+(\lambda _s (m)+n) \log (n+m))$ where $\lambda _s (m)$ is the (almost-linear) maximum length of $(m, s)$ Davenport–Schinzel sequences, and where s is a fixed parameter, depending on the shape of the given arcs. Another case where an intersection in close to linear time can be detected is when the union of the arcs of ${\bf \Gamma }$ and the union of the arcs of ${\bf \Gamma }^{\prime}$ are both connected. (ii) In the most general case, an intersection in time $O((m\sqrt {\lambda _s (n)} + n\sqrt {\lambda _s (m)} )\log ^{1.5} (m + n))$ can be detected. For several special but useful cases, in which many faces in the arrangements of ${\bf \Gamma }$ and ${\bf \Gamma }^{\prime}$ can be computed efficiently, randomized algorithms that are better than the general algorithm are obtained. In particular when all arcs in ${\bf \Gamma }$ and ${\bf \Gamma }^{\prime}$ are line segments, a randomized $O((m + n)^{{4 / 3}+\varepsilon})$ intersection detection algorithm, for any $\varepsilon > 0$, is obtained. The algorithm in (i) is applied to obtain an $O(\lambda _s (n) \log ^2 n)$ algorithm (for some small $s > 0$) for planning the motion of an n-sided simple polygon around a right-angle corner in a corridor, improving a previous $O(n^{2})$ algorithm of [Proc. 4th Annual Symposium on Computational Geometry, Association for Computing Machinery, New York, 1988, pp. 187–192], and to derive an efficient technique for fast collision detection for a simple polygon moving (translating and rotating) in the plane along a prescribed path.