Traditional computational geometry excels at processing static snapshots: finding a convex hull, building a Delaunay triangulation, or computing a Voronoi diagram for a fixed set of points. However, real-world applications—ranging from physics simulations and mobile sensor networks to robot motion planning—deal with objects that move continuously or change dynamically over time.
The naive approach to handling motion is discrete time-stepping: recomputing the geometric structure from scratch at regular intervals $\Delta t$. This approach suffers from a fundamental dilemma. If $\Delta t$ is too large, the simulation misses critical topological changes (such as collisions). If $\Delta t$ is too small, the system wastes immense computational power re-evaluating structures that haven't actually changed.
The core insight of kinetic and dynamic geometric maintenance is to shift from time-driven computation to event-driven computation. Instead of tracking the clock, we track the underlying combinatorial structure of the geometry itself.
The Core Mechanism: Certificates and Event Queues
How do we know when a geometric structure actually changes? Jeff Erickson et al. introduced a framework in Separation-Sensitive Collision Detection for Convex Objects that relies on mathematical certificates. A certificate is a local predicate—such as the orientation of three points or the intersection status of two bounding boxes—that guarantees a specific geometric relationship holds true.
By knowing the trajectories of moving objects, we can calculate the exact future timestamp when any given certificate will fail. These failure times are placed into a global priority queue (an event queue). The simulation then jumps directly from one event to the next. When a certificate expires, the system triggers a local update to repair the structure and schedules new certificates, leaving the rest of the system untouched.
This framework provides what Jeff Erickson et al. call separation-sensitivity: the frequency of updates scales naturally with how close objects are to changing their topological relationships, completely eliminating redundant updates when objects are far apart. Julien Basch et al. formalized the lower bounds of these systems in Lower Bounds for Kinetic Planar Subdivisions, identifying fundamental geometric events like a "capture"—where a moving point crosses a line segment formed by other points—as the mandatory baseline for structural updates in spatial partitions.
Taming the Complexity of Proximity and Triangulations
Maintaining continuous structures like Delaunay triangulations presents a major challenge. For points moving along predictable algebraic trajectories, the total number of combinatorial changes can theoretically reach a near-cubic bound ($O(n^3)$), as noted by Tamal K. Dey et al. in Guest Editors' Foreword. Processing this many events is often too slow for real-time applications.
To circumvent this bottleneck, researchers look for more stable subgraphs or alternative geometric representations. For instance, Pankaj K. Agarwal et al. in Kinetic stable Delaunay graphs and the authors of Stable Delaunay Graphs proposed the Stable Delaunay Graph (SDG). By filtering out highly volatile edges and retaining only $\alpha$-stable edges based on an angular stability condition, the SDG significantly reduces topological churn to a near-quadratic number of events while preserving crucial proximity properties.
Similarly, Haim Kaplan et al. demonstrated in A Kinetic Triangulation Scheme for Moving Points in The Plane that using flexible pseudo-triangulations instead of rigid triangulations minimizes the computational overhead per event, ensuring that the motion of a single point only affects a polylogarithmic number of certificates. When local updates are required, algorithms can exploit spatial coherence; Yuanfeng Zhou et al. leveraged this coherence in Fast Updating of Delaunay Triangulation of Moving Points by Bi-cell Filtering via "bi-cell filtering" to rapidly patch local regions of a triangulation rather than recomputing it from scratch.
Handling Discrete Insertions and Deletions
While kinetic structures handle continuous motion, many geometric applications must also support discrete updates, such as the sudden insertion or deletion of points and shapes.
Maintaining a dynamic convex hull under arbitrary updates typically requires logarithmic or polylogarithmic time. However, Bruce Brewer et al. showed in Dynamic Convex Hulls for Simple Paths that if updates are restricted to the endpoints of a simple or monotone path (modeled as a double-ended queue or deque), the convex hull can be maintained in worst-case constant time ($O(1)$). They achieved this by utilizing partially persistent data structures, which allow queries to access stable, consistent versions of the hull while complex merges are happening in the background.
Discrete updates also complicate spatial partitioning and matching. Timothy G. Abbott et al. designed data structures in Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane to maintain a ham-sandwich cut—a line that simultaneously bisects two disjoint convex shapes—with logarithmic update times as vertices are inserted or deleted. For point location within evolving subdivisions, Benoît Hudson et al. explored using bistellar flips in Using bistellar flips for rotations in point location structures to adaptively rebalance search structures and preserve logarithmic query times.
Tracking Global Extents and Optimization
Beyond local connectivity, event-driven structures excel at tracking global geometric properties and solving optimization problems in real-time.
Consider the problem of tracking the diameter or minimum bounding box of a moving cloud of points. Eric Veach designed a framework in Maintaining the Extent of a Moving Point Set that adapts the classic rotating calipers algorithm to a kinetic setting. By tracking antipodal pairs on a kinetic convex hull, the system monitors only the specific moments when the points defining the extent change, achieving high efficiency without continuous monitoring.
This event-driven philosophy extends to complex optimization tasks. For instance, Anastasiia Tkachenko showed in Computing Maximum Cliques in Unit Disk Graphs that for points in convex position, a maximum clique can be tracked by rotating a geometric intersection of unit disks and maintaining the enclosed point set dynamically. In mobile networks, Chien-Chun Ni et al. applied kinetic data structures to power diagrams in Capacitated Kinetic Clustering in Mobile Networks by Optimal Transportation Theory to maintain optimal, capacity-constrained user-to-base-station assignments smoothly as nodes move.
Even for complex geometric problems like facility location or minimum piercing sets, dynamic data structures enable sublinear or polylogarithmic update times. Sayan Bhattacharya et al. leveraged approximate nearest neighbor techniques and hierarchical structures in Dynamic High-Dimensional Facility Location with Low Recourse to maintain high-dimensional facility locations with low recourse, while Sujoy Bhore et al. provided fast dynamic approximation algorithms in Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching that transition these problems from static theoretical abstractions into practical tools for real-time, evolving environments.
Key Foundational Work
Voronoi Diagrams of Moving Points (1998) — contributed 6 concept elements to this direction.
Off-line Dynamic Maintenance of the Width of a Planar Point Set (1991) — contributed 2 concept elements to this direction.
Separation-Sensitive Collision Detection for Convex Objects (1998) — contributed 2 concept elements to this direction.