KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS

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.