Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons

ABSTRACT

We describe how to construct and kinetically maintain a tessellation of the free space between a collection of k disjoint simple polygonal objects with a total of N vertices, R of which are reflex. Our linear size tessellation consists of pseudo-triangles and has the following properties: (i) it contains disjoint outer hierarchical representations of all objects where the size of the outer boundary of these representations is proportional to a minimum link separator for the objects, and (ii) any line segment in the free space intersects at most O((k + log R) log N) pseudo-triangles (each of constant size).We maintain our tessellation by using the Kinetic Data Structure (KDS) framework. Our structure is compact, maintaining an active set of certificates whose number is linear in the size of a minimum link subdivision for the objects. It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of vertices. While its efficiency is difficult to establish precisely, it is shown that at most O(k + κmaxlog R)log N events happen during straight line motion of one object A in the context of k (fixed) others, where κmax denotes the maximum size of the minimum link polygon separating object A from the rest, during the motion.Furthermore, ray shooting queries (that use point location) can be answered in O((k + log R) log N) time for rays with arbitrary direction.

REFERENCES

• 1: P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang. Deformable free space tilings for kinetic collision detection. In B. R. Donald, K. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions (Proc. 5th Workshop Algorithmic Found. Robotics), pages 83--96. A. K. Peters, 2001.
• 2: Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.102-111, January 17-19, 1999, Baltimore, Maryland, United States
• 3: B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12:54--68, 1994.
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
• 6: J. Friedman , J. Hershberger , J. Snoeyink, Efficiently Planning Compliant Motion in thePlane, SIAM Journal on Computing, v.25 n.3, p.562-599, June 1996 [doi>10.1137/S0097539794263191]
• 7: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797]
• 8: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
• 9: D. Kirkpatrick, J. Snoeyink, and B. Speckmann. Kinetic collision detection for simple polygons. Intern. Journal Comp. Geom. Appl., 2002. To appear.
• 10: David G. Kirkpatrick , Bettina Speckmann, Separation Sensitive Kinetic Separation Structures for Convex Polygons, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.222-236, November 22-25, 2000
• 11: Michel Pocchiola , Gert Vegter, Minimal tangent visibility graphs, Computational Geometry: Theory and Applications, v.6 n.5, p.303-314, Sept. 1996 [doi>10.1016/0925-7721(95)00016-X]
• 12: M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comp. Geom., 16:419--453, 1996.
• 13: B. Speckmann. Kinetic data structures for collision detection. PhD thesis, Dept. of Computer Science, Univ. of British Columbia, 2001.
• 14: Subhash Suri, Minimum link paths in polygons and related problems, 1987
• 15: G. T. Toussaint. Computing geodesic properties inside a simple polygon. Revue D'Intelligence Artificielle, 3(2):9--42, 1989. also available as technical report SOCS 88.20, School of Computer Science, McGill University.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory