ABSTRACT
Let Γ be a collection of n (possibly intersecting) “red” Jordan arcs of some simple shape in the plane and let Γ' be a similar collection of m “blue” arcs. We present several efficient algorithms for detecting an intersection between an arc of Γ and an arc of Γ'. (i) If the arcs of Γ' form the boundary of a simply connected region, then we can detect a “red-blue” intersection in time Ο (λs(m)log2 m + (λa(m) + n)log(n + m)) where λ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 we can detect an intersection in close to linear time is when the union of the arcs of Γ and the union of the arcs of Γ' are both connected. (ii) In the most general case, we can detect an intersection in time Ο ((m√λs(n) + n√λs(m))log1.5(m+n)). For several special but useful cases, in which many faces in the arrangements of Γ and Γ' can be computed efficiently, we obtain randomized algorithms which are better than the general algorithm. In particular when all arcs in Γ and Γ' are line segments, we obtain a randomized Ο((m+n)4/3+c) intersection detection algorithm.
We apply the algorithm in (i) to obtain an Ο(λs(n) log2 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 Ο(n2) algorithm of [MY86], 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.
- AS88.Pankaj Agarwal and Micha Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection, Manuscript, 1988.Google Scholar
- ASS87.P. Agarwal, M. Sharir and P. Shot, Sharp upper and lower bounds on the length of Davenport-Schinzel sequences, Tech. Rept. 332, Dept. of Computer Science, New York University, 1987.Google Scholar
- At85.M. Atallah, Some dynamic computational geometry problems, Comp. and Math. with Appls., 11 (1985), pp. 1171-1181.Google ScholarCross Ref
- BO79.J. Bentley and M. Ottmann, Algorithms for reporting and counting intersections, IEEE Transactions on Computers, C- 28 (1979), pp. 643-647.Google ScholarDigital Library
- BK87.C. Bajaj and M. Kim, Compliant motion planning with geometric models, Proc. 3ra A CM Symposium on Computational Geometry, 1987, pp. 171-180. Google ScholarDigital Library
- Ch85.B. Chazelle, Fast searching in a real algebraic manifold with applications to geometric complexity, Proc. CAAP'85, Lecture Notes in Computer Science, Springer-Verlag, Berlin 1985, pp. 145-156. Google ScholarDigital Library
- CG85.B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry, Proc. 1st A CM Symposium on Computational Geometry, 1985, pp. 135-146. Google ScholarDigital Library
- Cl87.K. Clarkson, New applications of random sampling in computational geometry, Discrete and Computational Geometry, 2 (1987): pp. 195-222.Google ScholarDigital Library
- CEGSW88.K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Complexity bounds for arrangements, In preperation, 1988.Google Scholar
- Co36.R. Courant, Differential and in~egeral calculus vol. II, Interscience Publishers, Inc. New York, 1936.Google Scholar
- EGH*88.H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink and E. Welzl, Implicitly representing arrangements of lines or segments, To appear in Proc. 4th A CM Symposium on Computational Geometry, 1988. Google ScholarDigital Library
- EGS88.H. Edelsbrunner, L. Guibas and M. Sharir, The complexity of many faces in arrangement of lines and of segments, To appear in Proc. 4tn ACM Symposium on Computational Geometry, 1988. Google ScholarDigital Library
- GHLST87.L. Guibas, J. Hershberger, D. Leven, M. Sharir and R. Tarjan, Linear time algorithms for shortest path and visibility problems, Algorithmica, 2 (1987) pp. 209-233.Google ScholarDigital Library
- GSS88.L. Guibas, M. Sharir and S. Sifrony, On the general motion planning problem with two degrees of freedom, To appear in Proc. 4th A CM Symposium on Computational Geometry, 1988. Google ScholarDigital Library
- HS86.S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes, Combinatorica, 6 (1986) pp. 151-177. Google ScholarDigital Library
- HW87.D. Haussler and E. Welzl, c-nets and simplex range queries, Discrete and Computational Geometry, 2 (1987), pp. 127-151.Google ScholarDigital Library
- KLPS86.K. Kedem, R. Livne, J. Pach and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete and Computational Geometry, 1 (1986), pp. 59-71. Google ScholarDigital Library
- Lo61.E. Lockwood, A Book of Curves, Cambridge University Press, Cambridge, 1961.Google Scholar
- MY86.S. Maddila and C. Yap, Moving a polygon around the corner in a corridor, Proc. 2'~a ACM Symposium on Computational Geometry, 1986, pp. 187-192. Google ScholarDigital Library
- PSS88.R. Pollack, M. Sharir and S. Sifrony, Separating two simple polygons by a sequence of translations, DiscreSe and Computational Geometry), 3 (1988), pp. 123-136.Google ScholarDigital Library
- Pr79.F. Preparata, A note on locating a set of points in a planar subdivision, SIAM J. Computing, 8 (1979), pp. 542-545.Google ScholarCross Ref
- SS87.J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem, Tech. Rept. 193 (revised), Dept. of Computer Science, New York University, July 1987.Google Scholar
Index Terms
- Red-Blue intersection detection algorithms, with applications to motion planning and collision detection
Recommendations
Intersection detection and separators for simple polygons
SCG '92: Proceedings of the eighth annual symposium on Computational geometryA simple algorithm is presented for detecting whether two preprocessed simple polygons intersect one another. Given a simple polygon, A, in O(n log n) time and O(n) space we preprocess A constructing an enveloping triangulation called a scaffold. To ...
Cache-Oblivious Red-Blue Line Segment Intersection
ESA '08: Proceedings of the 16th annual European symposium on AlgorithmsWe present an optimal cache-oblivious algorithm for finding all intersections between a set of non-intersecting red segments and a set of non-intersecting blue segments in the plane. Our algorithm uses $O(\frac{N}{B}\log_{M/B}\frac{N}{B}+T/B)$ memory ...
Comments