KDSs

Kinetic data structures, or KDSs, maintain geometric or spatial properties of a set of objects that move continuously over time. Rather than recomputing invariants at every moment, a KDS tracks certificates—predictive conditions whose satisfaction guarantees that the invariant holds for the current motion. When a certificate is about to fail, a discrete event is generated and a local update restores the invariant and reschedules future events.

Core components include the moving objects with known trajectories, the invariant or predicate to be maintained, certificates encoding the conditions ensuring the invariant, and an event queue that stores predicted failure times. Local updating procedures adjust affected certificates; ideally only a small region of the structure is touched to preserve locality and efficiency. A KDS is correct if the invariant holds between events, and events are handled in a way that restores correctness.

Performance goals include compactness (few certificates per object), locality, and fast responsiveness. Amortized efficiency depends on the motion model and the chosen invariants; some KDSs achieve near-linear amortized cost for typical settings. The design often trades generality for robustness and simplicity.

Common examples include maintaining the order of moving points, the convex hull of moving points, or the Delaunay triangulation under motion, as well as keeping nearest-neighbor relations. KDS ideas have applications in motion planning, robotics, computer graphics, and dynamic geographic information systems.

History and scope: the concept of kinetic data structures was introduced in the computational-geometry literature in the late 1990s, providing a framework for preserving invariants under continuous motion. Limitations include designing problem-specific KDSs, numerical robustness, and scaling to high dimensions or non-smooth motion.