Red-Blue intersection detection algorithms, with applications to motion planning and collision detection

ABSTRACT

Let &Ggr; be a collection of n (possibly intersecting) “red” Jordan arcs of some simple shape in the plane and let &Ggr;' be a similar collection of m “blue” arcs. We present several efficient algorithms for detecting an intersection between an arc of &Ggr; and an arc of &Ggr;'. (i) If the arcs of &Ggr;' form the boundary of a simply connected region, then we can detect a “red-blue” intersection in time &Ogr; (&lgr;s(m)log2 m + (&lgr;a(m) + n)log(n + m)) where &lgr;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 &Ggr; and the union of the arcs of &Ggr;' are both connected. (ii) In the most general case, we can detect an intersection in time &Ogr; ((m√&lgr;s(n) + n√&lgr;s(m))log1.5(m+n)). For several special but useful cases, in which many faces in the arrangements of &Ggr; and &Ggr;' can be computed efficiently, we obtain randomized algorithms which are better than the general algorithm. In particular when all arcs in &Ggr; and &Ggr;' are line segments, we obtain a randomized &Ogr;((m+n)4/3+c) intersection detection algorithm. We apply the algorithm in (i) to obtain an &Ogr;(&lgr;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 &Ogr;(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.

REFERENCES

• AS88: Pankaj Agarwal and Micha Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection, Manuscript, 1988.
• 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.
• At85: M. Atallah, Some dynamic computational geometry problems, Comp. and Math. with Appls., 11 (1985), pp. 1171-1181.
• BO79: J. Bentley and M. Ottmann, Algorithms for reporting and counting intersections, IEEE Transactions on Computers, C- 28 (1979), pp. 643-647.
• BK87: C. Bajaj , M. Kim, Compliant motion planning with geometric models, Proceedings of the third annual symposium on Computational geometry, p.171-180, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41976]
• Ch85: B Chazelle, Fast searching in a real algebraic manifold with applications to geometric complexity, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.145-156, April 1985, Berlin, Germany
• CG85: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• Cl87: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• CEGSW88: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Complexity bounds for arrangements, In preperation, 1988.
• Co36: R. Courant, Differential and in~egeral calculus vol. II, Interscience Publishers, Inc. New York, 1936.
• EGH*88: H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73400]
• EGS88: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• 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.
• GSS88: L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73423]
• HS86: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• HW87: D. Haussler and E. Welzl, c-nets and simplex range queries, Discrete and Computational Geometry, 2 (1987), pp. 127-151.
• KLPS86: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• Lo61: E. Lockwood, A Book of Curves, Cambridge University Press, Cambridge, 1961.
• MY86: S Maddila , C K Yap, Moving a polygon around the corner in a corridor, Proceedings of the second annual symposium on Computational geometry, p.187-192, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10536]
• PSS88: R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
• Pr79: F. Preparata, A note on locating a set of points in a planar subdivision, SIAM J. Computing, 8 (1979), pp. 542-545.
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Path and circuit problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Reliability, Theory