Kinetic collision detection between two simple polygons. (Q1428461)

This paper presents a method for detecting collisions between two simple polygons moving rigidly in the plane. The method maintains a tiling of the free space between the moving polygons, which is used to certify the separation between the polygons as long as the cells in the tiling remain non-self-intersecting. The proposed tiling is easy to update when cell self-collisions occur. For two models of motion along algebraic trajectories of bounded degree (pure translation and rigid motion) the efficiency of the method is analysed in terms of bounds on the combinatorial changes to the tiling as the polygons move.