Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Dynamic nearest neighbor searching in the Euclidean plane has a long history, with early results by Agarwal and Matoušek [2]. Chan [6] was the first to achieve expected polylogarithmic update and query times. Following a sequence of improvements, the best structure at this time uses $O(m)$ space, allows for $O({\log }^{2}m)$ time queries, and for updates in deterministic, amortized $O({\log }^{4}m)$ time [15, 8]. For more general (constant complexity) distance functions, one can similarly achieve expected polylogarithmic query and update times [15, 16]. When the domain is a simple polygon $P$ with $n$ vertices, Oh and Ahn [17] presented a solution using $O(n+m)$ space achieving $O(\sqrt{m}\log (n+m))$ query time, and $O(\sqrt{m}\log m{\log }^{2}n)$ update time. Agarwal, Arge, and, Staals [1] then showed how to achieve $O({\log }^{2}n{\log }^{2}m)$ query time and expected $O(\mathrm{polylog}(nm))$ update time using $O(n+m{\log }^{3}m\log n)$ space. When the domain may have holes and the set of sites is static, there is an $O(n+m)$ space data structure that allows querying the (exact) nearest neighbor in $O(\log (n+m))$ time [14]. Constructing the data structure uses $O(n\log n)$ time. Wang [21] recently showed that if $P$ is triangulated, the shortest path map of a single site can be computed in $O(n+h\log h)$ time, where $h$ is the number of holes in $P$. Conceivably, his algorithm could be extended to handle multiple sites (as is the case in the algorithm by Hershberger and Suri). We are not aware of any results that allow updating sites. Even the case where we allow only insertions is challenging: we cannot easily apply a static-to-dynamic transformation [3] since rebuilding the static structure may require $\mathrm{\Omega }(n)$ time.

Thorup’s approach recursively partitions the domain $P$ using separators such that: each separator consists of at most three shortest paths, and the resulting subpolygons are of roughly the same size. This results in a balanced binary tree $𝒯$ of height $O(\log n)$ in which each node $\nu$ corresponds to some subpolygon $P_{\nu }$ that is further subdivided using a separator $Q_{\nu }$.

Consider the separator $Q$ of the root of this tree $𝒯$, and let $k=\lceil 1/\epsilon \rceil$. The main idea is that each polygon vertex $v$ generates a set $A_Q(v)$ of $O(k)$ so called anchor points¹¹1Thorup calls these points connections, but we use anchor points to avoid confusion with the paths connecting $v$ to these points. on $Q$, so that for any point $q\in Q$ the distance via one of these anchor points $A_Q(v)$ to $v$ is at most $(1+\epsilon )$ times the true distance $d(q,v)$. So, if a shortest path $\pi (u,v)$ between two vertices $u$ and $v$ intersects $Q$ then there is a path from $u$ to $v$ via two anchor points $a\in A_Q(u)$ and $a^{\prime }\in A_Q(v)$ (and the subcurve $Q[a,a^{\prime }]$ of $Q$) of length $(1+\epsilon )d(u,v)$. Given the anchor points (and the distances to their defining vertices) we can find the length of such a path in $O(k)$ time. If the path $\pi (u,v)$ does not intersect $Q$, it is contained in one of the subpolygons of the children of the root, and hence we can compute a $(1+\epsilon )$-approximation of the distance $d(u,v)$ in the appropriate subpolygon. As each vertex defines $O(k)$ anchor points on $Q$, and appears in $O(\log n)$ levels of the recursion. The total space used is $O(nk\log n)$.

To compute the anchor points efficiently, Thorup’s actual algorithm uses a graph $G$ in which the distance $d_G(u,v)$ between $u$ and $v$ in the graph is already an $(1+{\epsilon }_1)$-approximation of the true distance $d(u,v)$. Using the above approach with parameter ${\epsilon }_0$ then actually gives a path in $P$ with total length at most $(1+{\epsilon }_0)(1+{\epsilon }_1)d(u,v)$. Setting ${\epsilon }_0={\epsilon }_1=\epsilon /3$ then gives a $\epsilon$-approximation of the distances as desired.

However, using the graph $G$ results in slightly different (generally weaker) properties compared to the ideal case sketched above. In particular, his approach now guarantees that the distances from vertex $v$ are within a factor $1+\epsilon$ of the true distance only for a discrete subset of points on $Q$. For querying the distances between pairs of vertices this is not an issue. Thorup’s data structure can handle such queries in only $O(k)$ time. To support queries between arbitrary points $s,t\in P$, his algorithm connects $s$ and $t$ to $O(k)$ vertices in $G$ each, and then queries the all these pairs. This leads to the query time $O(k^3+k\log n/\log \log n)$.

Ideally, we would treat $s$ and $t$ identical to polygon vertices, so that we get $O(k)$ anchor points on a separator $Q$. However, as such a candidate anchor point $p\in Q$ may lie anywhere on $Q$ (in particular, it is not necessarily a vertex of $G$ yet), we may not have the required ${\epsilon }_1$-approximation of the distance to such a point yet.

We will show that we can use a slightly different graph $G^Q$ that includes additional “Steiner” points on $Q$. This leads to a different set of anchor points compared to Thorup’s approach, but does guarantee that for any vertex $v$, and any point $q$ on $Q$, the distance to $v$ is at most $(1+\epsilon )d(q,v)$. Furthermore, we show that we can efficiently compute an initial set of $O(k^2)$ candidate anchor points for an arbitrary point $s$, which we then reduce to $O(k)$. This results in $O(k^2\log n)$ query time for an arbitrary pair of query points $s,t\in P$.

As in the approximate 2-point shortest path data structure above, we construct a tree $𝒯$ of separators. We associate every site $s\in S$ with a root-to-leaf path in this tree. Namely, the nodes $\nu$ for which $s$ is contained in the subpolygon $P_{\nu }$. For each node $\nu$ on this path, we will additionally maintain a set of anchor points $A_Q(s)$ on the separator $Q=Q_{\nu }$ corresponding to this node. In particular, we consider $Q$ as a one dimensional space, and maintain an additively weighted Voronoi diagram $\mathrm{𝑉𝑜𝑟}(A_Q)$ on $Q$. The set of sites $A_Q={\bigcup }_{s\in S\cap P_{\nu }}{A}_Q(s)$ is the set of all anchor points of all sites that appear in $P_{\nu }$. The weight of an anchor point $a\in A_Q(s)$ is the distance estimate from $a$ to $s$.

If a shortest path between a query point $q$ and its closest site $s^{\ast }\in S$ intersects $Q$, then there is a sufficiently short path via one of the anchor points of $s^{\ast }$ and $q$ on $Q$. We can then find a sufficiently close site $s$ by querying the Voronoi diagram $\mathrm{𝑉𝑜𝑟}(A_Q)$ with all anchor points of $q$. This leads to an overall query time of $O(k^2\log n+k\log n\log m+k{\log }^{2}m)$, as we perform such queries in $O(\log n)$ nodes in $𝒯$.

The graph of the function that expresses the distance from a site $s\in S$ to a point $p$ on $Q$ via a given anchor point $a\in A_Q(s)$ is nicely “V-shaped”. Hence, we can maintain $\mathrm{𝑉𝑜𝑟}(A_Q)$ by maintaining the lower envelope of these functions. This allows us to insert and remove sites in $O(k{\log }^2(km))$ time. This leads to an overall update time of $O(k^2\log n+k\log n\log m+k{\log }^{2}m)$. Our structure uses $O(nk\log n+mk\log n+mk\log m)$ space.

In Section 3, we define our graph $G^Q$, and prove that it allows us to accurately estimate distances between any pair of points $s,t$ whose shortest path intersects $Q$. We then use this to construct our approximate 2-point shortest path data structure in Section 4. Finally, in Section 5 we describe our lower envelope data structure and the remaining tools needed for an efficient dynamic data structure for approximate nearest neighbor searching. Omitted proofs are in the full version [20].

A balanced hierarchical subdivision [9] is a recursive subdivision of a simple polygon into subpolygons. It is a crucial ingredient to obtain efficient solutions to many problems involving simple polygons [1, 13]. As was also recently observed [12], Thorup’s approach [19] essentially provides a balanced hierarchical subdivision for polygonal domains. The following lemma summarizes this result:

Our data structure now stores the balanced hierarchical subdivision $𝒯$ from Lemma 12. We build a point location data structure [18] on the triangulation induced by the leaves of $𝒯$. Additionally, for each edge $e$ of this triangulation, let $\nu$ be the highest node in $𝒯$ for which the edge appears on a shortest path $Q\in {𝒬}_{\nu }$ (if such a node exists). We store a pointer from edge $e$ to this shortest path. We can easily compute these pointers during the construction of $𝒯$.

Consider a node $\nu$. For each of the $O(1)$ shortest paths $Q\in {𝒬}_{\nu }$ we will construct the data structure from Lemma 11 (i.e. the graph $G^Q$ and the sets of anchor points) with respect to the subpolygon $P_{\nu }$. Since the total size of all subpolygons $P_{\nu }$ on each level of the tree is $O(n)$, the total size of all of these data structures on a given level of $𝒯$ is $O(kn)$, and thus $O(nk\log n)$ in total. Similarly, the total preprocessing time is $O(n{k}^2{\log }^{2}n\log (kn))$.

Given a pair of query points $s,t$ we find the leaf triangles ${\mathrm{\Delta }}_s$ and ${\mathrm{\Delta }}_t$ that contain points $s$ and $t$, respectively. If $s$ and $t$ lie in the same triangle, we can trivially report the length $\overline{st}$ as their shortest path. Otherwise, a shortest path from $s$ to $t$ must intersect one of the shortest paths $Q\in {𝒬}_{\nu }$ for a common ancestor $\nu$ of the two leaves. In particular, let $\mu$ be the highest node of $𝒯$ for which $\pi (s,t)$ intersects a shortest path $Q\in {𝒬}_{\mu }$. It follows that the shortest path $\pi (s,t)$ lies inside $P_{\mu }$, and thus we can use the Lemma 11 data structure for $Q$ to obtain a path of length at most $(1+\epsilon )d(s,t)$. Unfortunately, we cannot easily find this node $\mu$, so we query all Lemma 11 data structures for all shortest paths $Q\in {𝒬}_{\nu }$, for all common ancestors $\nu$ of the leaves representing ${\mathrm{\Delta }}_s$ and ${\mathrm{\Delta }}_t$, and report the shortest distance found. If either $s$ or $t$ lies on an edge $e$ of the boundary of some triangle that is part of some shortest path $Q\in Q_{\nu }$, we use the pointer stored at $e$ to jump to the highest such node, and query only the common ancestors of these nodes instead. Since every query returns the length of an obstacle-avoiding path, the returned estimate $\widehat{d}(s,t)$ satisfies $d(s,t)\le \widehat{d}(s,t)\le (1+\epsilon )d(s,t)$ as desired. Since each query takes $O(k\log n+k^2)$ time, the total query time is $O(k{\log }^{2}n+k^2\log n)$.

The $O(k{\log }^{2}n)$ term in the query time is only due to computing the ray shooting queries needed to compute the sets $X_Q(s)$ for each shortest path $Q$ considered. Next, we argue that we can compute these sets in only $O(k\log n)$ time by building an additional $O(nk\log n)$ space data structure. The overall space usage thus remains the same, and the final query time becomes $O(k^2\log n)$ as claimed.

Finally, we plug in that $k=\lceil \frac{1}{\epsilon }\rceil$, which establishes Theorem 2.