Points in motion

October 29, 2003
2:50pm - 4:00pm
Halligan 111


In this talk, I will present some very recent results on kinetic point sets, defined as points moving with constant speeds along linear trajectories, and kinetic graphs, defined as graphs embedded on kinetic point sets. The problems of interest include collision prediction, and maintaining non-crossing properties or other geometric embedding features such as edge directions.

The results include a combinatorial characterization of the collision events for kinetic point sets. This is done by relating them to a refined (oriented matroidal) oriented-projective view of configuration spaces (parallel redrawings) of certain types of direction newtorks (graphs with additional slope information associated to their edges) with good rigidity theoretic properties (independent in the rigidity matroid). Collisions in kinetic point sets are captured via rigid components in an associated direction network. Non-crossing kinetic graphs with parallel redrawings appear - surprisingly - as collapsed pointed pseudo-triangulation mechanisms.

An application to morphing planar shapes will conclude the talk, if time allows.