KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
- 1 February 2002
- journal article
- conference paper
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 12 (01n02) , 3-27
Abstract
We design a simple and elegant kinetic data structure for detecting collisions between polygonal (but not necessarily convex) objects in motion in the plane. Our structure is compact, maintaining an active set of certificates whose number is proportional to a minimum-size set of separating polygons 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 object vertices. It is difficult to characterize the efficiency of our structure for lack of a canonical definition of external events. Nevertheless we give an easy upper bound on the worst case number of certificate failures.Keywords
This publication has 8 references indexed in Scilit:
- An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the PlaneDiscrete & Computational Geometry, 1997
- Efficiently Planning Compliant Motion in the PlaneSIAM Journal on Computing, 1996
- A compact piecewise-linear voronoi diagram for convex sites in the planeDiscrete & Computational Geometry, 1996
- Collision detection for interactive graphics applicationsIEEE Transactions on Visualization and Computer Graphics, 1995
- Ray shooting in polygons using geodesic triangulationsAlgorithmica, 1994
- APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHSInternational Journal of Computational Geometry & Applications, 1993
- Coordinated motion planning for two independent robotsAnnals of Mathematics and Artificial Intelligence, 1991
- A “retraction” method for planning the motion of a discJournal of Algorithms, 1985