New dynamics in geometric data structures
Joe Simons
We study geometric data structures for spatiotemporal 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 eventbased 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 timewindowed queries for skylines in
$\mathbf{R}^d$, convex hulls in $\mathbf{R}^2$ and proximity based
queries in $\mathbf{R}^d$.

In the setdifference 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 setdifference range queries, where
answers to queries are settheoretic 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 datastreaming sketches
we call signed symmetricdifference sketches.

In the localupdate 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 sublogarithmic time on a pointer machine.