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 @math , a set of @math points in @math indexed by time such that we can perform insertions or deletions at any point in the timeline in @math amortized time. We support, for any small constant @math , @math -approximate range reporting queries at any point in the timeline in @math time, where @math is the output size. We also show how to answer @math -approximate nearest neighbor queries for any point in the past or present in @math time.
In this paper we consider the dynamic vertical ray shooting problem, that is the task of maintaining a dynamic set S of n non intersecting horizontal line segments in the plane subject to a query that reports the first segment in S intersecting a vertical ray from a query point. We develop a linear-size structure that supports queries, insertions and deletions in O(log n) worst-case time. Our structure works in the comparison model and uses a RAM. We describe an asymptotically optimal data-structure for dynamic point location for horizontal segments. For n line-segments, queries take O(log n) time, updates take O(log n) amortized time and the data structure uses O(n) space. This is the first structure for the problem that is optimal in space and time (modulo the possibility of removing amortization). We also describe dynamic data structures for orthogonal range reporting and orthogonal intersection reporting. In both data structures for n points (segments) updates take O(log n) amortized time, queries take O(log n+k log n log log n) time, and the structures use O(n) space, where k is the size of the output. The model of computation is the unit cost RAM. We address the problem of replicating a Voronoi diagram @math of a planar point set @math by making proximity queries, which are of three possible (in decreasing order of information content): 1. the exact location of the nearest site(s) in @math ; 2. the distance to and label(s) of the nearest site(s) in @math ; 3. a unique label for every nearest site in @math . We provide algorithms showing how queries of Type 1 and Type 2 allow an exact cloning of @math with @math queries and @math processing time. We also prove that queries of Type 3 can never exactly clone @math , but we show that with @math queries we can construct an @math -approximate cloning of @math . In addition to showing the limits of nearest-neighbor database security, our methods also provide one of the first natural algorithmic applications of retroactive data structures. We consider the two dimensional fully-dynamic orthogonal range reporting problem and the two dimensional fully-dynamic orthogonal line segment intersection reporting problem in the comparison model. We show that if n is the number of stored elements, then these problems can be solved in worst case time Θ(log n) plus time proportional to the size of the output pr. operation.