# Speaker: Joe Simons

##
Fully Retroactive Approximate Range
and Nearest Neighbor Searching

We describe fully retroactive dynamic data structures
for approximate range reporting
and approximate nearest neighbor reporting. We show
how to maintain, for any positive constant d, a set of n
points in R^d indexed by time such that we can perform
insertions or deletions at any point in the timeline in
O(log n) amortized time. We support, for any small constant epsilon>0,
(1+ epsilon)-approximate range reporting queries at any point in the
timeline in O(log n + k) time, where k is the output size.
We also show how to answer (1+epsilon)-approximate nearest neighbor
queries for any point in the past or present in O(log n) time.
Joint work with Michael Goodrich.