Incremental Planar Nearest Neighbor Queries with Optimal Query Time

We assume the partition of $S$ into the sets $𝒮=\{S_1,S_2,\mathrm{\dots },S_f\}$. Any further notation that includes a subscript, such as $T_i$, is a function of the $S_j$, for $j\ge i$. This compact notation makes explicit the dependence of ${\mathrm{𝑎𝑛𝑦𝑡ℎ𝑖𝑛𝑔}}_i$ only on $S_j$, for $j\ge 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.

Let $\mathrm{𝑉𝑜𝑟}(P)$ be the Voronoi diagram of point set $P$, let $\mathrm{𝐶𝑒𝑙𝑙}(P,p)$ be the cell of a point $p$ in $\mathrm{𝑉𝑜𝑟}(P)$, that is the locus of points in the plane whose closest element in $P$ is $p$. Thus $q\in \mathrm{𝐶𝑒𝑙𝑙}(P,p)$ is equivalent to $\mathrm{𝑁𝑁}(P,q)=p$. Let $|\mathrm{𝐶𝑒𝑙𝑙}(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 $|\mathrm{𝐶𝑒𝑙𝑙}(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 $\mathrm{𝐶𝑒𝑙𝑙𝑠}(P,P^{\prime })$ denote ${\bigcup }_{p\in P^{\prime }}\mathrm{𝐶𝑒𝑙𝑙}(P,p)$.

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 $\rho$, Frederickson [13] showed the vertices of $G$ can be decomposed¹¹1We use the word decomposed to mean a division of a set into into a collection of sets, the decomposition, whose union is the original set, but, unlike with a partition, elements may belong to multiple sets. into $\mathrm{\Theta }(|V|/\rho )$ pieces, so that: (i) Each vertex is in at least one piece. (ii) Each piece has at most $\rho$ vertices in total and only $O(\sqrt{\rho })$ 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 $\mathrm{\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|)$ [14, 18]. 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 $\rho$.

Given integers , let

be a decomposition of $T_j$ into $r=\mathrm{\Theta }(|T_j|/d^{4k})$ subsets such that each subset ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^l(k)$ has size $O(d^{4k})$ and a fringe of size $O(d^{2k})$ with respect to $G(T_i)$. We let

be defined such that ${\mathrm{𝑆𝑒𝑝}}_j^{\mathrm{\ell }}(k)$ denotes the fringe of ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^{\mathrm{\ell }}(k)$, and let ${\overline{Sep}}_j^{\mathrm{\ell }}(k)$ be ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^{\mathrm{\ell }}(k)\setminus {\mathrm{𝑆𝑒𝑝}}_j^{\mathrm{\ell }}(k)$. Thus each ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^{\mathrm{\ell }}(k)$ is partitioned into its fringe vertices, ${\mathrm{𝑆𝑒𝑝}}_j^{\mathrm{\ell }}(k)$, and its interior non-fringe vertices ${\overline{\mathrm{𝑆𝑒𝑝}}}_j^{\mathrm{\ell }}(k)$; note that ${\overline{\mathrm{𝑆𝑒𝑝}}}_j^{\mathrm{\ell }}(k)$ may be empty if all elements of ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^{\mathrm{\ell }}(k)$ are on its fringe.

Finally, we define ${\mathrm{𝑆𝑎𝑚𝑝𝑙𝑒}}_j(k)$ to be the union of all the fringe vertices:

thus ${\mathrm{𝑆𝑒𝑝𝑠}}_j(k)$ is a decomposition of ${\mathrm{𝑆𝑎𝑚𝑝𝑙𝑒}}_j(k)$.

For any $k\in [1..j-1]$, the decomposition of $T_j$ into ${\mathrm{𝑃𝑖𝑒𝑐𝑒𝑠}}_j(k)$, the partition of each ${\mathrm{𝑃𝑖𝑒𝑐𝑒}}_j^{\mathrm{\ell }}(k)$ into ${\mathrm{𝑆𝑒𝑝}}_j^{\mathrm{\ell }}(k)$ and ${\overline{Sep}}_j^{\mathrm{\ell }}(k)$, and the set ${\mathrm{𝑆𝑒𝑝𝑠}}_j(k)$ can all be computed in time $O(|T_j|)$ using [18] if the Delaunay triangulation is available; if not it can be computed in time $O(|T_j|\log |T_j|)$. Thus computing these for all valid $i$ takes time and space $O(|T_j|\log |T_j|{\log }_d|T_j|)$ as .

One property of this sampling technique is that points in $T_j$ with Voronoi cells in $\mathrm{𝑉𝑜𝑟}(T_j)$ of complexity at least $k$ are included in $T_i$ if $j>i$ and $j-i=O({\log }_{d}k)$. By complexity of a region, we mean the number of edges that bound this region.

At the core of our nearest neighbor algorithm is the function $Jump$, defined as follows. We will find it helpful to use ${\mathrm{𝑁𝑁}}_R(q)$ for a range $R=[l,r]$ to denote $\mathrm{𝑁𝑁}({\cup }_{i\in [l,r]}{T}_i,q)$; for example ${\mathrm{𝑁𝑁}}_{[1,k]}(q)$ is the nearest neighbor of $q$ in $T_1,T_2,\mathrm{\dots }{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\mathrm{\dots }{T}_{(i+j)/2}$ determines whether there are any points that could be the nearest neighbor of $q$ in $T_{(i+j)/2+1}\mathrm{\dots }{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.

• $\mathrm{■}$

  Input to $Jump\mathbf{(}i\mathbf{,}j\mathbf{,}q\mathbf{,}{p}_i\mathbf{,}{e}_i\mathbf{)}$:

  • –

    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=\mathrm{𝑁𝑁}(T_i,q)$.

  • –

    The edge $e_i$ on the boundary of $\mathrm{𝐶𝑒𝑙𝑙}(T_i,p_i)$ that the ray $\overrightarrow{p_{i}q}$ intersects.

• $\mathrm{■}$

  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 ${\mathrm{𝑁𝑁}}_{(m,\min (j,f)]}(q)\ne {\mathrm{𝑁𝑁}}_{[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 ${\mathrm{𝑁𝑁}}_{(m,j^{\prime })}(q)\ne {\mathrm{𝑁𝑁}}_{[1,j^{\prime })}(q)$.

    • *

      The point $p_{j^{\prime }}$ is $\mathrm{𝑁𝑁}(T_{j^{\prime }},q)$.

    • *

      The edge $e_{j^{\prime }}$ is on the boundary of $\mathrm{𝐶𝑒𝑙𝑙}(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.

A nearest neighbor query can be answered through a series of calls to the $Jump$ function:

• $\mathrm{■}$

  Initialize $i=1,j=2$, $p_1$ to be $\mathrm{𝑁𝑁}(T_1,q)$, and $e_1$ to be the edge of $\mathrm{𝐶𝑒𝑙𝑙}(T_1,p_1)$ crossed by the ray $\overrightarrow{p_{1}q}$; all of these can be found in constant time as $|T_1|=\mathrm{\Theta }(1)$. Initialize $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}$ to $p_1$.

• $\mathrm{■}$

  Repeat the following while $\frac{i+j}{2}\le 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 set $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}=p_{j^{\prime }}$

    • *

      Set $i=j^{\prime }$ and set $j=j^{\prime }+1$

• $\mathrm{■}$

  Return $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}$

We will show in the rest of this section that, given this jump function as a black box, we can correctly answer a nearest neighbor query in $O(\log n)$ time.

The loop in the jump procedure will maintain the invariants that $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}$ is ${\mathrm{𝑁𝑁}}_{[1,\min (f,\frac{i+j}{2})]}(q)$, and $j-i$ is a power of two. The latter is because $j-i$ is set to either 1 or is doubled with each iteration of the loop. As to the first invariant, before the loop runs, the invariant requires $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}=\mathrm{𝑁𝑁}(T_1,q)$, which $p_1$ and $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}$ are initialized to. During the loop we subscript $i$ and $j$ by new and old to indicate the value of variables at the beginning and at the end of the loop. Thus $p_{\mathrm{𝑛𝑒𝑎𝑟𝑒𝑠𝑡}}={\mathrm{𝑁𝑁}}_{[1,\min (f,\frac{i_{\mathrm{𝑜𝑙𝑑}}+j_{\mathrm{𝑜𝑙𝑑}}}{2})]}(q)$. Also if the loop runs, we know $\min (j_{\mathrm{𝑜𝑙𝑑}},f)=j_{\mathrm{𝑜𝑙𝑑}}$. We distinguish between two cases depending on whether the jump function returns failure or a triple.

If the jump function returns failure, we know that

Using this fact we can go from the invariant in terms of the old variables to the new ones:

Now we consider the case when a triple $(j^{\prime },p_{j^{\prime }},e_{j^{\prime }})$ is returned by the $Jump$ function. We know that ${\mathrm{𝑁𝑁}}_{(m,j^{\prime }]}(q)\ne {\mathrm{𝑁𝑁}}_{[1,j^{\prime }]}(q)$, and using the same logic as from the failure case we can conclude that the old $p_{nearest}$ is ${\mathrm{𝑁𝑁}}_{[1,j^{\prime })}(q)$. The code sets $p_{nearest}$ to the point that is closer to $q$ among the old $p_{nearest}$, equal to ${\mathrm{𝑁𝑁}}_{[1,j^{\prime })}(q)$, and $p_{j^{\prime }}$, which is $\mathrm{𝑁𝑁}(T_{j^{\prime }},q)$. Thus the new $p_{nearest}$ is equal to ${\mathrm{𝑁𝑁}}_{[1,j^{\prime }]}(q)$ (note the closed interval) which we can rewrite to get the invariant as follows, using the fact that the subscript of $\mathrm{𝑁𝑁}$ is only dependent on the integers in the given range:

When the loop finishes, we have $j>f$ and thus