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.
Blelloch @cite_16 and Giora and Kaplan @cite_40 consider the problem of maintaining a fully retroactive dictionary that supports successor or predecessor queries. They both base their data structures on a structure by Mortensen @cite_22 , which answers fully retroactive one dimensional range reporting queries, although Mortensen framed the problem in terms of two dimensional orthogonal line segment intersection reporting. In this application, the @math -axis is viewed as a timeline for a retroactive data structure for 1-dimensional points. The insertion of a segment @math corresponds to the addition of an insert of @math at time @math and a deletion of @math at time @math . Likewise, the removal of such a segment corresponds to the removal of these two operations from the timeline. For this 1-dimensional retroactive data structuring problem, Blelloch and Giora and Kaplan give data structures that support queries and updates in @math time. Dickerson @cite_42 describe a retroactive data structure for maintaining the lower envelope of a set of parabolic arcs and give an application of this structure to the problem of cloning a Voronoi diagram from a server that answers nearest-neighbor queries.
@cite_40 @cite_16 @cite_42 @cite_22
2624264009 1998117630 2951132123 2003523151
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.