Incremental Planar Nearest Neighbor Queries with Optimal Query Time John Iacono, Yakov Nekrich Abstract In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal O ⁡ ( log ⁡ n ) O(\log n) time while supporting insertions in O ⁡ ( log 1 + ε ⁡ n ) O(\log^{1+\varepsilon}n) time. No previous data structure was known that supports O ⁡ ( log ⁡ n ) O(\log n) -time queries and polylog-time insertions. In order to achieve logarithmic queries our data structure uses a new technique related to fractional cascading that leverages the inherent geometry of this problem. Our method can be also used in other semi-dynamic scenarios. 1 Introduction In the nearest neighbor problem a set of points S is stored in a data structure so that for a query point q the point p\in S that is closest to q can be found efficiently. The nearest neighbor problem and its variants are among the most fundamental and extensively studied problems in computational geometry; we refer to e.g. [ 20 ] for a survey. In this paper we study dynamic data structures for the Euclidean nearest neighbor problem in two dimensions. We show that the optimal O(\log n) query time for this problem can be achieved while allowing insertions in time O(\log^{1+\epsilon}) . Previous Work. See Table 1 . In the static scenario the planar nearest neighbor problem can be solved in O(\log n) time by point location in Voronoi diagrams. However the dynamic variant of this problem is significantly harder because Voronoi diagrams cannot be dynamized efficiently: it was shown by Allen et al. [ 2 ] that a sequence of insertions can lead to \Omega(\sqrt{n}) amortized combinatorial changes per insertion in the Voronoi diagram. A static nearest-neighbor data structure can be easily transformed into an insertion-only data structure using the logarithmic method of Bentley and Saxe [ 3 ] at the cost of increasing the query time to O(\log^{2}n) . Several researchers [ 12 , 10 , 21 ] studied the dynamic nearest neighbor problem in the situation when the sequence of updates is random in some sense (e.g. the deletion of any element in the data structure is equally likely). However their results cannot be extended to the case when the complexity of a specific sequence of updates must be analyzed. Using a lifting transformation [ 11 ] , 2-d nearest neighbor queries can be reduced to extreme point queries on a 3-d convex hulls. Hence data structures for the dynamic convex hull in 3-d can be used to answer 2-d nearest neighbor queries. The first such data structure (without assumptions about the update sequence) was presented by Agarwal and Matoušek [ 1 ] . Their data structure supports queries in O(\log n) time and updates in O(n^{\varepsilon}) time; another variant of their data structure supports queries in O(n^{\varepsilon}) time and updates in O(\log n) time. A major improvement was achieved in a seminal paper by Chan [ 4 ] . The data structure in [ 4 ] supports queries in O(\log^{2}n) time, insertions in O(\log^{3}n) expected time and deletions in O(\log^{6}n) expected time. The update procedure can be made deterministic using the result of Chan and Tsakalidis [ 6 ] . The deletion time was further reduced to O(\log^{5}n) [ 16 ] and to O(\log^{4}n) [ 5 ] . This sequence of papers makes use of shallow cuttings, a general powerful technique, but, alas, all uses of it for the point location problem in 2-d have resulted in O(\log^{2}n) query times. Even in the case of insertion-only scenario, the direct application of the 45-year-old classic technique of Bentley and Saxe [ 3 ] remains the best insertion-only method with polylogarithmic update before this work; no data structure with o(\log^{2}n) query time and polylogarithmic update time was described previously. Query Insert Delete Bentley and Saxe 1980 [ 3 ] O(\log^{2}n) O(\log^{2}n) Not supported Agarwal and Matoušek 1995 [ 1 ] O(\log n) O(n^{\varepsilon}) O(n^{\varepsilon}) '' O(n^{\varepsilon}) O(\log n) O(\log n) Chan 2010 [ 4 ] O(\log^{2}n) O(\log^{3}n) † O(\log^{6}n) † Chan and Tsakalidis 2016 [ 6 ] O(\log^{2}n) O(\log^{3}n) O(\log^{6}n) Kaplan et al. 2020 [ 16 ] O(\log^{2}n) O(\log^{3}n) O(\log^{5}n) Chan 2020 [ 5 ] O(\log^{2}n) O(\log^{3}n) O(\log^{4}n) Here O(\log n) O(\log^{1+\varepsilon}n) Not supported Table 1: Known results. Insertion and deletion times are amortized, † denotes in expectation. Our Results. We demonstrate that optimal O(\log n) query time and poly-logarithmic update time can be achieved in some dynamic settings. The following scenarios are considered in this paper: 1. We describe a semi-dynamic insertion-only data structure that uses O(n) space, supports insertions in O(\log^{1+\varepsilon}n) amortized time and answers queries in O(\log n) time. 2. In the semi-online scenario, introduced by Dobkin and Suri [ 13 ] , we know the deletion time of a point p when a point p is inserted, i.e., we know how long a point will remain in a data structure at its insertion time. We describe a semi-online fully-dynamic data structure that answers queries in O(\log n) time and supports updates in O(\log^{1+\varepsilon}n) amortized time. The same result is also valid in the offline scenario when the entire sequence of updates is known in advance. 3. In the offline partially persistent scenario , the sequence of updates is known and every update creates a new version of the data structure. Queries can be asked to any version of the data structure. We describe an offline partially persistent data structure that uses O(n\log^{1+\varepsilon}n) space, can be constructed in O(n\log^{1+\varepsilon}n) time and answers queries in O(\log n) time. All three problems considered in this paper can be reduced to answering point location queries in (static) Voronoi diagrams of O(\log n) different point sets. For example, we can obtain an insertion-only data structure by using the logarithmic method of Bentley and Saxe [ 3 ] , which we now briefly describe. The input set S is partitioned into a logarithmic number of subsets S_{1} , \ldots , S_{f} of exponentially increasing sizes. In order to find the nearest neighbor of some query point q we locate q in the Voronoi diagram of each set S_{i} and report the point closest to q among these nearest neighbors. Since each point location query takes O(\log n) time, answering a logarithmic number of queries takes O(\log^{2}n) time. The fractional cascading technique [ 8 ] applied to this problem in one dimension decreases the query cost to logarithmic by sampling elements of each S_{i} and storing copies of the sampled elements in other sets S_{j} , ji ; this implies the last sets are equal: T_{f}=S_{f} . This sampling will be provided by the function \mathit{Sample}_{j}(k) which returns a subset of T_{j} of size O(|T_{j}|/d^{2k}) ; while it will have other important properties, for now only the size matters. We now can formally define T_{i} : T_{i}\coloneqq S_{i}\cup\bigcup_{j=i+1}^{f}\mathit{Sample}_{j}(j-i) From this definition we have several observations which we group into a lemma, the proof can be found in Appendix A : Lemma 1 . Facts about T_{i} 1. T_{f}=S_{f} 2. T_{i} is a function of the S_{j} , for j\geq i . 3. S=\cup_{i=1}^{f}T_{i} 4. \mathit{NN}(S,q)\in\bigcup_{i=1}^{f}\{\mathit{NN}(T_{i},q)\} 5. |T_{i}|=\Theta(d^{i}) 6. For any i \sum_{j=i+1}^{f}|\mathit{Sample}_{j}(j-i)|=\Theta(|T_{i}|) A note on notation. We assume the partition of S into the sets \mathcal{S}=\{S_{1},S_{2},\ldots,S_{f}\} . Any further notation that includes a subscript, such as T_{i} , is a function of the S_{j} , for j\geq i . This compact notation makes explicit the dependence of \mathit{anything}_{i} only on S_{j} , for j\geq i . This dependence in one direction only (i.e., on non-smaller indexes only) is crucial to the straightforward application of the standard Bentley and Saxe [ 3 ] rebuilding technique in the implementation of the data structure and the insertion operation described in section § 2.3 - 2.4 . Voronoi and Delaunay. Let \mathit{Vor}(P) be the Voronoi diagram of point set P , let \mathit{Cell}(P,p) be the cell of a point p in \mathit{Vor}(P) , that is the locus of points in the plane whose closest element in P is p . Thus q\in\mathit{Cell}(P,p) is equivalent to \mathit{NN}(P,q)=p . Let |\mathit{Cell}(P,p)| be the complexity of the cell, that is, the number of edges on its boundary. Let G(P) refer to the Delaunay graph of P , the dual graph of the Voronoi diagram of P ; the degree of p in G(P) is thus |\mathit{Cell}(P,p)| and each point in P corresponds to a unique vertex in G(P) . Delaunay graphs are planar. To simplify the description, we will not distinguish between points in a planar set P and vertices of G(P) . For example, we will sometimes say that a point p has degree x or say that a point p^{\prime} is a neighbor of p . We will find it useful to have a compact notation for expressing the union of Voronoi cells; thus for a set of points P^{\prime}\subseteq P , let \mathit{Cells}(P,P^{\prime}) denote \bigcup_{p\in P^{\prime}}\mathit{Cell}(P,p) . Pieces and Fringes. Given a graph, G=(V,E) , and a set of vertices V^{\prime}\subseteq V , the fringe of V^{\prime} (with respect to G ) is the subset of V^{\prime} incident to edges whose other endpoint is in V\setminus V^{\prime} . Let G=(V,E) be a planar graph. For any r , Frederickson [ 14 ] showed the vertices of G can be decomposed 1 1 1 We use the word decomposed to mean a division of a set into into a collection sets, the decomposition , whose union is the original set, but, unlike with a partition, elements may belong to multiple sets. into \Theta(|V|/r) pieces , so that: (i) Each vertex is in at least one piece. (ii) Each piece has at most r vertices in total and only O(\sqrt{r}) vertices on its fringe. (iii) If a vertex is a non-fringe vertex of a piece (with respect to G ), then it is not in any other pieces. (iv) The total size of all pieces is in \Theta(|V|) . Intuitively, the pieces are almost a partition of V where those vertices on the fringe of each piece may appear in multiple pieces. Such a decomposition of G can be computed in time O(|V|) [ 15 , 19 ] . We will apply this decomposition to T_{i} , which is both a point set and the vertex set of G(T_{i}) , for exponentially increasing sizes of r . Given integers 1\leq ki and j-i=O(\log_{d}k) . By complexity of a region, we mean the number of edges that bound this region. Lemma 2 . Given icd^{4(j-i)} , for a constant c chosen later, we will show this implies p\in T_{i} . Thus the degree of p in G(T_{j}) is greater than cd^{4(j-i)} . Consider the piece \mathit{Piece}^{\ell}_{j}(j-i) in \mathit{Pieces}_{j}(j-i) that contains p . This piece has size at most O(d^{4(j-i)}) , which is at most cd^{4(j-i)} for some c (here we choose c ). Thus in G(T_{j}) , p must have neighbors which are not in \mathit{Piece}^{\ell}_{j}(j-i) . By definition, p is thus in the fringe Sep^{\ell}_{j}(j-i) , which implies p\in\mathit{Sep}^{\ell}_{j}(j-i) . From the definition of T_{i} , T_{i}\subset\mathit{Sep}^{\ell}_{j}(j-i) and which gives p\in T_{i} . ∎ While we cannot bound the complexity of any Voronoi cell in a fringe, we can bound the complexity of \overline{Sep}_{j}^{\ell}(j-i) , the cells inside a fringe. Intuitively, each piece has the fringe cells on its exterior and non-fringe cells on its interior; imagining the fringe cells of a piece as an annulus gives two boundaries, the exterior boundary of the fringes, which is the boundary between the cells of this and other pieces, and the interior boundary of the fringes, which is the boundary between the fringe cells and the interior cells in this piece. Crucially, while the exterior boundary could have high complexity, the interior boundary does not, which we now formalize: Lemma 3 . The complexity of \mathit{Cells}(T_{j},\overline{Sep}_{j}^{\ell}(j-i)) is O(d^{4(j-i)}) . Proof. See Figure 2 . Each cell in \mathit{Cells}(T_{j},\overline{Sep}_{j}^{\ell}(j-i)) is adjacent to either other cells in \mathit{Cells}(T_{j},\overline{Sep}_{j}^{\ell}(j-i)) or cells in \mathit{Cells}(T_{j},{Sep}_{j}^{\ell}(j-i)) . The adjacency graph of these Voronoi regions is planar, and as \overline{Sep}_{j}^{\ell}(j-i)\cup{Sep}_{j}^{\ell}(j-i)={Piece}_{j}^{\ell}(j-i) , and recalling that |{Piece}_{j}^{\ell}(j-i)|=O(d^{4(j-i)}) gives the lemma. ∎ The Jump function: definition At the core of our nearest neighbor algorithm is the function Jump , defined as follows. We will find it helpful to use \mathit{NN}_{R}(q) for a range R=[l,r] to denote \mathit{NN}(\cup_{i\in[l,r]}T_{i},q) ; for example \mathit{NN}_{[1,k]}(q) is the nearest neighbor of q in T_{1},T_{2},\ldots T_{k} . Intuitively, a call to Jump(i,j,q,p_{i},e_{i}) is used when trying to find the nearest neighbor of q , and assuming we know the nearest neighbor of q in T_{1},T_{2}\ldots T_{(i+j)/2} seeks to provide information on whether there are any points that could be the nearest neighbor of q in T_{(i+j)/2+1}\ldots T_{j} . This information could be either a simple no , or it could provide the nearest neighbor of q for some prefix of these sets. Additionally, the edge of an the Voronoi cell of the currently known nearest neighbor in the direction of the query point is always passed and returned to aide the search using the combinatorial bounds from Lemma 8 , point 4 . • Input to Jump(i,j,q,p_{i},e_{i}) : – Integers i and j , where j-i is required to be a power of 2. We use m to refer to (j+i)/2 , the midpoint. – Query point q . – Point p_{i} where p_{i}=\mathit{NN}(T_{i},q) . – The edge e_{i} on the boundary of \mathit{Cell}(T_{i},p_{i}) that the ray \overrightarrow{p_{i}q} intersects. • Output : Either one of two results, Failure or a triple (j^{\prime},p_{j^{\prime}},e_{j^{\prime}}) – If Failure , this is a certificate that \mathit{NN}_{(m,\min(j,f)]}(q)\not=\mathit{NN}_{[1,\min(j,f)]}(q) – If a triple (j^{\prime},p_{j^{\prime}},e_{j^{\prime}}) is returned, it has the following properties: * The integer j^{\prime} is in the range (m,j] and \mathit{NN}_{(m,j^{\prime})}(q)\not=\mathit{NN}_{[1,j^{\prime})}(q) . * The point p_{j^{\prime}} is \mathit{NN}(T_{j^{\prime}},q) . * The edge e_{j^{\prime}} is on the boundary of \mathit{Cell}(T_{j^{\prime}},p_{j}) that the ray \overrightarrow{p_{j^{\prime}}q} intersects. We will show later that Jump runs in O(j-i) time. Implementation details are deferred to Section 2.2 . The nearest neighbor procedure. A nearest neighbor query can be answered through a series of calls to the Jump function: • Initialize i=1,j=2 , p_{1} to be \mathit{NN}(T_{1},q) , and e_{1} to be the edge of \mathit{Cell}(T_{1},p_{1}) crossed by the ray \overrightarrow{p_{1}q} ; all of these can be found in constant time as |T_{1}|=\Theta(1) . Initialize p_{\mathit{nearest}} to p_{1} . • Repeat the following while \frac{i+j}{2}\leq f : – Run Jump(i,j,q,p_{i},e_{i}) . If the result is failure: * Set j=j+(j-i) – Else a triple (j^{\prime},p_{j^{\prime}},e_{j^{\prime}}) is returned: * If d(p_{j^{\prime}},q)f and thus p_{nearest}=\mathit{NN}_{[1,\min(f,\frac{i+j}{2})]}(q)=\mathit{NN}_{[1,f]}(q)=\argmin_{p\in\{T_{k}|k\in[1,f]\text{ and }k\in\mathbb{Z}\}}d(p,q)=\mathit{NN}(S,q) Running time Lemma 4 . Given the Jump function, the running time of the nearest neighbor search function in O(\log n) . Proof. We use a potential argument. Let i_{t} and j_{t} denote the values of i and j after the loop has run t times, let a_{t} denote the runtime of the t th iteration of the loop, and let T denote the number of times the loop runs. The total runtime is thus O(1)+\sum_{t=1}^{T}a_{t} . Define \Phi_{t}\coloneqq c(2i_{t}+j_{t}) , for some constant c chosen so that a_{t}\leq\frac{c}{2}(j_{j}-i_{t}) ; as i_{0}=1 and j_{0}=2 , \Phi_{0}=4c . (recall that the runtime of Jump is O(j-i) for constant d ). We will argue that for all t , a_{t}\leq\Phi_{t}-\Phi_{t-1}+O(1) . Summing, this gives \sum_{t=1}^{T}a_{t}\leq\Phi_{T}-\Phi_{0}+O(T) . Since i , j and T are in the range [1,f] , this bounds \sum_{t=1}^{T}a_{t} by 3cf+O(f)=\Theta(\log n) . Thus all that remains is to argue that a_{t}\leq\Phi_{t}-\Phi_{t-1} for the two cases where the t th run of Jump ends in failure or returns a triple. Case 1, Jump returns failure. In the case of failure, i remains the same, thus i_{t}=i_{t-1} but j increases by j-i , thus j_{t}=2j_{t-1}-i_{t-1} . Thus the potential increases by c(j-i) . \displaystyle\Phi_{t}-\Phi_{t-1} \displaystyle=c(2i_{t}+j_{t})-c(2i_{t-1}+j_{t-1}) \displaystyle=c(2i_{t-1}+2j_{t-1}-i_{t-1})-c(2i_{t-1}+j_{t-1}) \displaystyle=c(j_{t-1}-i_{t-1}) \displaystyle\geq a_{t} Case 2, Jump returns a triple. i_{t} is set to j^{\prime} and j_{t} changes to j^{\prime}+1 . The key observation is that, due to the invariant in our correctness argument, j_{t}\geq\frac{i_{t-1}+j_{t-1}}{2} . Thus i_{t}=j^{\prime}\geq j_{t-1}\geq\frac{i_{t-1}+j_{t-1}}{2} and j_{t}=j^{\prime}+1\geq j_{t-1}+1\geq\frac{i_{t-1}+j_{t-1}}{2}+1 and the potential change is \displaystyle\Phi_{t}-\Phi_{t-1} \displaystyle=c(2i_{t}+j_{t})-c(2i_{t-1}+j_{t-1}) \displaystyle\geq c(2\cdot\frac{i_{t-1}+j_{t-1}}{2}+\frac{i_{t-1}+j_{t-1}}{2}+1)-c(2i_{t-1}+j_{t-1}) \displaystyle=\frac{c}{2}(j_{t-1}-i_{t-i})+c \displaystyle\geq a_{t} ∎ 2.2 The jump function 2.2.1 Basic geometric facts We begin with our most crucial geometric lemma, the one that we build upon to make our algorithm work. Informally, given point sets A and B which possibly have elements in common, and a query point q , if the closest point to q in B is also in A , then the closest point to q in A\cup B is in A , and not in B\setminus A . Lemma 5 . Given i,j , ii . Insertion is thus handled by the classic logarithmic method of Bentley and Saxe [ 3 ] which transforms a static construction into a dynamic structure, and which we briefly summarize. To insert, we put the new point into S_{1} and rebuild level 1. Every time a set S_{i} exceeds the upper limit of \Theta(d^{i}) , half of the items are moved from S_{i} to S_{i+1} and all levels from i+1 down to S_{1} are rebuilt. So long as the upper and lower constants in the big Theta are at least a constant factor apart, the amortized insertion cost is O(\log n) times the cost per item to rebuild a level, thus obtaining: Lemma 10 . Insertion can be performed with an amortized running time of O(\log^{3}n) . The performance of our data structure can be summarized as follows: Theorem 1 . There exists a semi-dynamic insertion-only data structure that answers two-dimensional nearest neighbor queries in O(\log n) time and supports insertions in O(\log^{3}n) amortized time. The data structure uses O(n\log^{2}n) space. Appendix A Proof of Lemma 1 Lemma 1 . Facts about T_{i} 1. T_{f}=S_{f} 2. T_{i} is a function of the S_{j} , for j\geq i . 3. S=\cup_{i=1}^{f}T_{i} 4. \mathit{NN}(S,q)\in\bigcup_{i=1}^{f}\{\mathit{NN}(T_{i},q)\} 5. |T_{i}|=\Theta(d^{i}) 6. For any i \sum_{j=i+1}^{f}|\mathit{Sample}_{j}(j-i)|=\Theta(|T_{i}|) Proof. 1. T_{f}\coloneqq S_{f}\cup\bigcup_{j=f+1}^{f}\mathit{Sample}_{j}(j-i)=S_{f} 2. Follows from the definition of T_{i} and that \mathit{Sample}_{j}(j-i) is a function of T_{j} and j-i and the fact that j>i . 3. Follows from the fact that the S_{i} are a partition of S and all T_{i} are subsets of S . 4. Follows immediately from the previous point. 5. Since |S_{i}|=\Theta(d^{i}) and |T_{f}|=|S_{f}|=\Theta(d^{f}) , this can be verified by solving this recurrence: |T_{i}|\leq cd^{i}+\sum_{j=i+1}^{f}\frac{|T_{j}|}{d^{2(j-i)}} 6. \sum_{j=i+1}^{f}|\mathit{Sample}_{j}(j-i)|=\Theta\left(\sum_{j=i+1}^{f}\frac{|T_{j}|}{d^{2(j-i)}}\right)=\Theta\left(|T_{i}|\sum_{j^{\prime}=1}^{\infty}\frac{1}{2^{j^{\prime}}}\right)=\Theta(|T_{i}|) ∎ Appendix B Faster Updates The data structure described in Theorem 1 achieves optimal query time but uses superlinear space. Superlinear space usage is needed to implement the Jump procedure: our implementation stores a poly-logarithmic number of data items for each Voronoi edge in T_{i} . In this section we explain how the data structure can be modified so that both O(n) space usage and more efficient update time are achieved. Our improvement is based on the following idea: We maintain the Voronoi diagram for an auxiliary subset T^{\prime}_{i}\subset T_{i} that contains |T_{i}|/\operatorname{polylog}(n) points. Before we start the Jump procedure, we locate q in \mathit{Vor}(T^{\prime}_{i}) and use a Voronoi cell of \mathit{Vor}(T^{\prime}_{i}) as the starting point of the Jump procedure. A detailed description of the modified data structure is provided below. Data Structure. We change the value of the parameter d and set d=\log^{\varepsilon}n for a constant \varepsilon>0 . We re-define T_{i} so that T_{i} contains at most \frac{|T_{j}|}{\log^{3}n} points from every set T_{j} , j>i : let g=\log^{6}n points, let h=\operatorname{pow2}((1/4)\log_{d}g) , and let T_{i}\coloneqq S_{i}\cup\bigcup_{j=i+1}^{f}\mathit{Sample}_{j}(\max(\operatorname{pow2}(j-i),h)) where \operatorname{pow2}(x)=2^{\lceil\log_{2}x\rceil} . Thus each T_{j} is divided into pieces so that each piece contains \Omega(\max(d^{4(j-i)},g)) points and the total number of pieces is O(\min(\frac{|T_{j}|}{d^{4(j-i)}},\frac{|T_{j}|}{g})) . The number of points that are copied from T_{j} , j>i , to T_{i} does not exceed O(\frac{|T_{j}|}{\sqrt{g}}) . Hence the set T_{i}\setminus S_{i} contains O(\frac{|T_{i}|\log n}{\sqrt{g}})=O(\frac{T_{i}}{\log^{2}n}) points. We define T^{\prime}_{i}=\mathit{Sample}_{h}(T_{i})\cup(T_{i}\setminus S_{i}) . We construct convex hulls \mathit{Hull}_{i}(j,p) for every set T^{\prime}_{i} , for every j>i , and for all p\in T^{\prime}_{i} . We also construct all auxiliary data structures for convex hull search described in Section 2.3 for every set T^{\prime}_{i} . Since T^{\prime}_{i} contains O(\frac{|T_{i}|}{\log^{2}n}) points, all data structures can be constructed in O(|T_{i}|) time and use O(|T_{i}|) space. Lemma 11 . If p_{i}=\mathit{NN}(T_{i},q) is known, we can find p^{\prime}_{i}=\mathit{NN}(T^{\prime}_{i},q) in O(\log\log n) time. Proof. For every point p\in T_{i} we store the index l such that p_{i} is in \mathit{Piece}^{l}_{i}(h) . For every set P^{l}=T^{\prime}_{i}\cap\mathit{Piece}^{l}_{i}(h) , we store its Voronoi diagram and a point location data structure. The set T^{\prime}_{i}\cap\mathit{Piece}^{l}_{i}(h) contains \operatorname{polylog}(n) points because \mathit{Piece}^{l}_{i}(h) contains \operatorname{polylog}(n) points. Hence we can find p^{l}=\mathit{NN}(T^{\prime}_{i}\cap\mathit{Piece}^{l}_{i}(h),q) in O(\log\log n) time. Suppose that p^{\prime}_{i}\not=p^{l} . Then q is in \mathit{Cell}(T^{\prime}_{i},p^{\prime}) such that the point p^{\prime} is not in \mathit{Piece}^{l}_{i}(h) . The segment \overline{qp^{\prime}} must intersect some \mathit{Cell}(T_{i},p_{s}) such that p_{s}\in\mathit{Sep}^{l}_{i}(h) . Consider an arbitrary planar point q^{\prime} on \overline{qp^{\prime}} such that q^{\prime} is in \mathit{Cell}(T_{i},p_{s}) . Since q^{\prime} is in \mathit{Cell}(T_{i},p_{s}) , dist(p_{s},q^{\prime})i . Using Lemma 11 , we find p^{\prime}_{i}=\mathit{NN}(T^{\prime}_{i},q) in O(\log\log n) time. We also find the edge e^{\prime}_{i}=\overline{v_{1}v_{2}} of \mathit{Cell}(T^{\prime}_{i},p_{i}^{\prime}) that is intersected by \overrightarrow{p_{i}q} . Using the hull data structure for the triangle \triangle(p^{\prime}_{i}v_{1}v_{2}) , we look for the smallest j^{\prime} , such that \frac{i+j}{2}\leq j^{\prime}\leq j , and q is outside of \mathit{Hull}_{i}(j^{\prime},p_{i}) . If j^{\prime} is found, we execute Steps 2-4 of the Jump procedure as described in Section 2.2 . If there is no such hull, the procedure returns failure. The total runtime of the Jump procedure is O(\log\log n+\log d(j-i))=O((j-i)\log\log n) . Using the same analysis as in Section 2.1 , the total runtime of the nearest neighbor procedure is O(\log n) : the runtime of the Jump procedure can be bounded by \frac{c}{2}\log\log n(j-i) for some constant c ; if we re-define the potential after the t -th jump to \Phi_{t}\coloneqq c\log\log n(2i_{t}+j_{t}) , then, using the same method as in Lemma 4 , we can bound the runtimes of all jump procedures by \Phi_{T}+O(T\log\log n) where T is the total number of jumps needed to answer a nearest neighbor query. Since T\leq f=O(\log_{d}n) , the overall cost of all jumps O(\frac{\log n}{\log d}\log\log n)=O(\log n) . Piece Interior Search Structure. In order to complete the Jump procedure (see Step 3 in the case when the index j^{\prime} is found), we need to find the Voronoi cell containing q provided that \mathit{Piece}^{l}_{i}(k) is known. This step must be completed in O(k\log\log n) time. To this aim, we need an additional data structure, described in the following lemma. Lemma 13 . Suppose we know the piece \mathit{Piece}^{l}_{i}(k) that contains the query point q . Then we can find the cell \mathit{Cell}(T_{i},p) containing q in time O(k\cdot\log d) . The underlying data structure uses space O(m) and can be constructed in O(m\log\log n) time, where m is the number of points in T_{i} . Proof. The set T_{i} is recursively divided into pieces Pieces_{i}(k) where k is a power of 2 such that hh . We note that k is a power of 2 . We set k_{0}=k , j=0 and repeat the following loop: We find \mathit{Cell}(\mathit{PSep}^{l}_{j}(k_{j}),p_{k_{j}}) that contains q and test whether q is in \mathit{Cell}(T_{i},p_{k_{j}}) . If this is the case, we stop. Otherwise we find the edge e^{\prime} that is hit by the ray \overrightarrow{p_{k_{j}}q} . hen we increment j and set k_{j}=k_{j-1}/2 . When e^{\prime} is known, we can identify \mathit{Piece}^{l_{j}}_{i}(k_{j}) that contains the query point q and start the next iteration of the loop. If k_{j}=h , we stop the loop and find \mathit{Cell}(\mathit{Piece}^{l_{j}}_{i}(h),p) that contains q . The j -th iteration of the loop takes O(\log(d^{k_{j}}))=O(k_{j}\log d) time. Hence a query is answered in O(k_{0}\log d)=O(k\log\log n) time. ∎ Insertions. Now we can evaluate the overall cost of constructing the level i of our data structure. The set T_{i} is updated by selecting a subset \overline{T}\subset T_{i-1} , such that \overline{T} contains d^{i-1}/2 points, and moving points p\in\overline{T} from T_{i-1} to T_{i} . We can choose the points of \overline{T} ; for example, we can select d^{i-1}/2 points from T_{i-1} with the smallest x -coordinates. Hence we can obtain the Voronoi diagram of \overline{T} in O(|T_{i}|) time. We can also merge the Voronoi diagrams of \overline{T} and T_{i} and obtain the Voronoi diagram of the updated set T_{i} in O(|T_{i}|) time using a linear-time algorithm for merging Voronoi diagrams [ 17 , 7 ] . When \mathit{Vor}(T_{i}) is available, we obtain \mathit{Sample}_{i}(k) for all k\leq(1/4)\log_{d}n such that k is a power of 2 . Each \mathit{Sample}_{i}(k) can be obtained in O(|T_{i}|) time. Hence we need O(|T_{i}|\log\log n) time to obtain all \mathit{Sample}_{i}(k) for k\leq(1/4)\log_{d}n such that k is a power of 2 . Then we re-build Voronoi diagrams for T_{j} , jj}\mathit{Sample}_{j^{\prime}}(\operatorname{pow2}(\max(j^{\prime}-j,h))) . Since this set contains O(|T_{j}|/g) points, we can construct the Voronoi diagram of T^{\mathrm{aux}}_{j} in O(|T_{j}|) time. Finally we merge \mathit{Vor}(T^{\mathrm{aux}}_{j}) and the Voronoi diagram of S_{j} and obtain \mathit{Vor}(T_{j}) in O(|T_{j}|) time. When \mathit{Vor}(T_{i}) is available, we can extract the points of T^{\prime}_{i} , construct \mathit{Vor}(T^{\prime}_{i}) and all convex hull structures in O(|T_{i}|) time. We can also construct the piece interior search structure for T_{i} in O(|T_{i}|\log\log n) time. For each j\text{height}(u)}\mathit{Sample}_{j}(j-i,u) . Thus sets T(u) can be constructed for all nodes u\in\mathcal{T} in top-to-bottom order. When T(u) is defined, we can construct T^{\prime}(u) and all auxiliary data structures necessary for the Jump procedure. Now we can find \mathit{NN}(\cup_{u\in\pi(t)}S(u),q)=\mathit{NN}(\cup_{u\in\pi(t)}T(u),q) as follows. We start in a leaf node of \pi(t) and move up along \pi(t) using the Jump procedure. Using the analysis of Lemma 4 , the total cost of all Jumps is O(\log n) . Theorem 3 . There exists an offline partially persistent data structure that answers two-dimensional nearest neighbor queries in O(\log n) time. The data structure uses O(n\log^{1+\varepsilon}n) space and can be constructed in O(n\log^{1+\varepsilon}n) time. Appendix D Semi-Online Fully-Dynamic Data Structure In this section we consider the ephemeral (non-persistent) offline scenario. In this scenario the sequence of all insertions and deletions is known in advance. However only the latest version of the data structure can be queried. We order updates and assign every update an integer timestamp. As in Section C we associate a lifespan [t_{1}(p),t_{2}(p)] with every point p ; we also maintain a tree \mathcal{T} , so that the leaves of \mathcal{T} store the insertion and deletion times of different points in sorted order. The definition of a set S(u) is changed so that every point is stored in only one set at every time. Let \mathtt{cur} denote the timestamp of the current version. The set S(u) contains all points p such that rng(u)\subseteq[t_{1}(p),t_{2}(p)] , rng(\text{parent}(u))\not\subseteq[t_{1}(p),t_{2}(p)] , and u_{\min}\leq\mathtt{cur}\leq u_{\max} . After every update, we modify our data structure as follows. We examine sets S(u) for every node u , such that u_{\max}=\mathtt{cur} . For every such node u and for each p\in S(u) , we remove p from S(u) and insert it into S(u^{\prime}) such that rng(u^{\prime})\subseteq[t_{1}(p),t_{2}(p)] , rng(\text{parent}(u^{\prime}))\not\subseteq[t_{1}(p),t_{2}(p)] , and u^{\prime}_{\min}\leq\mathtt{cur}+1\leq u^{\prime}_{\max} . If such u^{\prime} does not exist, we remove p from our data structure. When all sets S(u) are processed, we increment \mathtt{cur} by 1 . Then we examine all nodes v , such that v_{\min}=\mathtt{cur} in the decreasing order of their height. For each v we construct T(v)=S(v)\cup(\cup_{j>\text{height}(u)}\mathit{Sample}_{j}(j-i,u)) . We also construct and store all auxiliary data structures. Every point p is inserted into O(\log^{1+\varepsilon}n) different sets because there are O(\log n) nodes u , such that rng(u)\subseteq[t_{1}(p),t_{2}(p)] but rng(\text{parent}(u))\not\subseteq[t_{1}(p),t_{2}(p)] . Every set S(u) is created only once. Hence the amortized update time is O(\frac{c(n)}{n}\log^{1+\varepsilon}n)=O(\log^{1+2\varepsilon}n) , where c(n) is the construction time of the data structure. By replacing \varepsilon with \varepsilon/2 , we obtain the following result. Theorem 4 . There exists a fully-dynamic offline data structure that answers two-dimensional nearest neighbor queries in O(\log n) time. The data structure uses O(n) space where n is the total number of updates. Each update operation is supported in O(\log^{1+\varepsilon}n) amortized time. The data structure of Theorem 4 can be adjusted to the semi-online scenario. In this setting the sequence of updates is not known in advance. But we know the deletion time t_{2}(p) of each point p at the time when p is inserted. We initially create the tree \mathcal{T} with n^{\prime}=2n_{0} leaves where n_{0} is the number of points initially stored in the data structure. When a new point with lifespan [t_{1}(p),t_{2}(p)] is inserted, we set t^{\prime}_{1}(p)=t_{1}(p) and t^{\prime}_{2}(p)=\min(t_{2}(p),\mathtt{init}+n^{\prime}-1) . The variable \mathtt{init} is set to 1 when the data structure is initialized and updated every time when we re-build the tree \mathcal{T} . We insert p with lifespan [t^{\prime}_{1}(p),t^{\prime}_{2}(p)] into \mathcal{T} as described in the proof of Theorem 4 . After n_{0}/2 insertions or deletions, we set n_{0} to the current number of elements in the data structure and build a new tree with n^{\prime}=2n_{0} leaves. All points currently stored in the nodes of the old tree are moved to the new tree. For each point p , we set t^{\prime}_{1}(p)=\mathtt{cur} and t^{\prime}_{2}(p)=\min(t_{2}(p),\mathtt{cur}+n^{\prime}-1) . For simplicity, all leaves in the new tree are indexed with \mathtt{cur} , \mathtt{cur}+1 , \ldots , \mathtt{cur}+n^{\prime}-1 . Finally, we set \mathtt{init}=\mathtt{cur} and discard the old tree. The global re-building incurs O(1) insertions into the new tree per update. Hence, the amortized update cost is unchanged. Corollary 2 . There exists a fully-dynamic semi-online data structure that answers two-dimensional nearest neighbor queries in O(\log n) time. The data structure uses O(n) space where n is the total number of updates. Each update operation is supported in O(\log^{1+\varepsilon}n) amortized time. P A generic set of points with no specific meaning S The set of points currently stored n |S| dist(p,q) Distance from point p to q \triangle pqr Triangle with endpoints p , q , and r d A parameter initially set to a constant {\cal S}=\{S_{1},S_{2},\ldots S_{f}\} A partition of S , where |S_{i}|=\Theta(d^{i}) f |{\cal S}| T_{i} S_{i}\cup\bigcup_{j=i+1}^{|\mathcal{S}|}\mathit{Sample}_{j}(j-i) \mathit{Vor}(P) The Voronoi diagram of P G(P) The Delaunay graph of P \mathit{Cell}(P,p) The cell of p in \mathit{Vor}(P) \mathit{Cells}(P,P^{\prime}) For P^{\prime}\subseteq P , the union of \mathit{Cell}(P,p) for all p\in P^{\prime} . \mathit{NN}(P,q) The nearest neighbor of q in P . \mathit{NN}_{R}(q) \argmin_{p\in\{T_{k}|k\in R\text{ and }k\in\mathbb{Z}\}}dist(p,q) \begin{array}[]{c}\mathit{Pieces}_{j}(k)=\\ \{\mathit{Piece}^{1}_{j}(k),\ldots,\mathit{Piece}^{|\mathit{Pieces}_{j}(k)|}_{j}(k)\}\end{array} A division of T_{j} into \Theta(|T_{j}|/d^{4k}) subsets such that each subset has size O(d^{4k}) . \mathit{Sep}^{\ell}_{j}(k) The subset of points in \mathit{Piece}^{\ell}_{j}(k) who have neighbors in G(T_{j}) that are not in \mathit{Piece}^{\ell}_{j}(k) . \overline{Sep}_{j}^{\ell}(k) \mathit{Piece}_{j}^{\ell}(k)\setminus\mathit{Sep}_{j}^{\ell}(k) \mathit{Seps}_{j}(k) \{\mathit{Sep}_{j}^{1}(k),\mathit{Sep}^{2}_{j}(k),\ldots\mathit{Sep}^{|\mathit{Pieces}_{j}(k)|}_{j}(k)\} \mathit{Sample}_{j}(k) \bigcup_{Sep\in\mathit{Seps}_{j}(k)}Sep \mathit{Hull}_{i}(j,p_{i}) , p_{i}\in T_{i} The convex hull of \{p_{i}\}\cup(\mathit{Cell}(T_{i},p_{i})\cap\mathit{Cells}(T_{j},\mathit{Sep}_{j}(j-i))) \overline{\mathit{Hull}}_{i}(j,p_{i}) , p_{i}\in T_{i} \mathit{Cell}(T_{i},p_{i})\setminus\mathit{Hull}_{i}(j,p_{i}) Table 2: Table of notation.