# New dynamics in geometric data structures

## Joe Simons

We study geometric data structures for spatio-temporal data: geometric objects which change over time. In particular, we design data structures for fundamental geometric problems in the following four data models:

• In the retroactive model, we maintain a timeline for the historical sequence of updates to the data structure, and every update has an associated time stamp. Unlike the standard dynamic model, in which we only allow query and update operations against the current state of the data structure, in the retroactive model, we also allow operations to be performed in the past''. We describe fully retroactive dynamic data structures for approximate range reporting and approximate nearest neighbor reporting.
• In the windowed model, we take an event-based approach, where each geometric object corresponds to an event that occurs at an instance in time, and queries are performed with respect to an interval in the timeline. We consider time-windowed queries for skylines in $\mathbf{R}^d$, convex hulls in $\mathbf{R}^2$ and proximity based queries in $\mathbf{R}^d$.
• In the set-difference model, we maintain a dynamic set (or multiple sets) of items such that two subsets can be efficiently compared. We introduce the problem of performing set-difference range queries, where answers to queries are set-theoretic symmetric differences between sets of items in two geometric ranges. We describe a general framework for answering such queries based on a novel use of data-streaming sketches we call signed symmetric-difference sketches.
• In the local-update model, we maintain a set of geometric objects such that the speed of updates is parameterized by how dramatically the update changes the object. When the updated object is similar to the old object in size and location, we desire to surpass known lower bounds for more general updates. We study planar point location in a collection of disjoint fat regions, and investigate the complexity of local updates. We design a linear size data structure that allows for insertions, deletions, and queries in logarithmic time, and allows for local updates in sub-logarithmic time on a pointer machine.