Fully Retroactive Approximate Range and Nearest Neighbor Searching

Details Fully Retroactive Approximate Range and Nearest Neighbor Searching Fully Retroactive Approximate Range and Nearest Neighbor Searching

2011-09-01

arxiv.org/abs/1109.0312v1

Computer Science

Computational Geometry

24 pages, 4 figures. To appear at the 22nd International Symposium on Algorithms and Computation (ISAAC 2011)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fully Retroactive Approximate Range and Nearest Neighbor Searching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fully Retroactive Approximate Range and Nearest Neighbor Searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully Retroactive Approximate Range and Nearest Neighbor Searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687222