Nearest Neighbor Searching in a Dynamic Simple Polygon

A possible explanation for the lack of work in this dynamic domain setting is that the problems seem extremely challenging: even just adding a single line segment to the boundary of the polygon may significantly change the distances between the sites in the polygon. This severely limits what information (i.e. which distances) the data structure can store. An insertion may also structurally change the triangulation of the polygon (which is the foundation upon which, e.g., the data structure of Agarwal, Arge, and Staals [1] is built).

We overcome these challenges, and present the first dynamic data structure for the geodesic nearest neighbor problem that allows updates to both the sites $S$ and the simple polygon $P$ containing $S$. Our data structure achieves sublinear query and update time and allows the following updates on $P$ and $S$ (Fig. 1): 1. inserting a segment (barrier) between points $u$ and $v$, where $u$ on the boundary $\partial P$ of $P$ and $v\in P$ an arbitrary point, provided that the interior of this segment does not intersect $\partial P$, and 2. inserting a site $s\in P$ into $S$.

This type of barrier insertion is similar to the insertion operation considered by Ishaque and Tóth [18] and Oh and Ahn [23]. Note that in case $v$ also lies on the boundary of $P$, this actually splits the polygon into two subpolygons, which can no longer interact. Hence, we can essentially treat these subpolygons independently. In the remainder of the paper, we thus focus on the more interesting case in which $v$ lies strictly in the interior of $P$. This also slightly simplifies our presentation, since $P$ then remains an actual simple polygon.

Our data structure uses $O(n(\log \log n+\log m)+m)$ space, supports the above updates in amortized $\tilde{O}(n^{3/4}+m^{3/4})$ time, and answers queries in expected $\tilde{O}(n^{3/4}+n^{1/4}{m}^{1/2})$ time. While these query and update times are still far off from the polylogarithmic query and update times for a static domain, they are comparable to, for example, the result of Oh and Ahn for maintaining the geodesic hull in a dynamic polygon [23].

We believe it should be possible to extend our data structure to support deleting sites as well. In particular, by further incorporating the results of Agarwal, Arge, and Staals [1]. However, for ease of exposition we defer site deletions for now. Supporting deleting vertices of the polygon seems more interesting, however also much more complicated. Further ideas are likely required to support deletions of vertices as well.

Our data structure essentially consists of two independent parts, both of which critically build upon balanced geodesic triangulations [9]. So, we first review some of their useful properties in Section 2. We then give an overview of the data structure in Section 3. Section 4 describes the first part of our data structure, which can be regarded as an extension of the dynamic two-point shortest path data structure of Goodrich and Tamassia [13]. Our main technical contribution is in Section 5, which describes the second main part: a (static) data structure that can answer nearest neighbor queries in a subpolygon $Q$ of $P$ that can be specified at query time. This result may be of independent interest. Omitted proofs as well as the generalization of some of the results of Agarwal, Arge, and Staals [1] that we need for our data structure, can be found in the full version [12].

Here we shortly discuss the data structure of Goodrich and Tamassia for dynamic planar subdivisions [13]. This data structure supports both shortest-path and ray-shooting queries in $O({\log }^{2}m)$ time. Updates to the subdivision, such as inserting or deleting a vertex or edge, also take $O({\log }^{2}m)$ time. The main component is a balanced geodesic triangulation with dual tree $𝒯$. A secondary dynamic point location data structure [14] is build for this geodesic triangulation. A tertiary data structure stores, for each deltoid $\mathrm{\Delta }$, the three concave chains bounding $\mathrm{\Delta }$ in balanced tree structures. To support shortest path queries, they store for each node in $𝒯$ the tail of its geodesic triangle that is not shared by its parent in a balanced tree structure. The size of the data structure is $O(m)$. Using rotations, insertions and deletions can be performed in $O({\log }^{2}m)$ time.

We extend the dynamic shortest path data structure of Goodrich and Tamassia [13] so that we have efficient access to the vertices and edges that were inserted since the last rebuild. We call these marked vertices and edges. In the data structure of  [13], each polygonal chain is stored in a chain tree: a balanced binary tree where leaves correspond to the edges in the chain and internal nodes to the vertices of the chain. Each internal node also corresponds to a subchain and stores its length. We additionally store a boolean in each node that that is true whenever its subchain contains a marked edge, and false otherwise. Next to this dynamic data structure, we keep a list of all marked vertices. For this list, we consider the endpoint of an inserted edge to be marked, even if the vertex already existed in $\tilde{P}$.

Next, we explain how to use the Dynamic Shortest Path data structure to find for a query point $q\in P$ a set of bounded nearest neighbor queries such that the nearest neighbor of $q$ is the result of one of these queries. For each bounded nearest neighbor query we return the apex $v_R$, the two other endpoints $s,t$ of the shortest paths bounding $R$, and a boolean indicating whether $R$ is a geodesic triangle or geodesic cone. In case $R$ is a geodesic cone, we order $s,t$ such that the part of $\partial P$ in $R$ is given by the clockwise traversal from $s$ to $t$ along $\partial P$. We will choose our region $R$ in such way that the paths bounding $R$ are shortest paths in both $P$ and $\tilde{P}$. In other words, there are no marked vertices (that are reflex vertices) on these shortest paths.

We first describe the partition of $P$ that will result in the $O(k)$ bounded nearest neighbor queries, and then discuss how to compute them. We partition $P$ into $O(k)$ maximal regions such that for every point in a region $R$, the path to $q$ uses the same marked vertices, see Figure 4. This can be viewed as a shortest path map for $q$, where we only consider marked vertices. Each region in this map will be a bounded nearest neighbor query together with its apex, i.e. the first marked vertex on the path from any point in the region to $q$.

To find these regions, we keep track of all points on $\partial P$ that define the boundary between two such regions in a balanced binary tree $T$ based on the order along $\partial P$. Observe that all marked vertices define such a boundary point. We thus insert all $O(k)$ marked vertices into $T$. Then, for each marked vertex $v$, we:

1. 1.

   Compute the shortest path $\pi (v,q)$.

2. 2.

   Perform a ray shooting query in the direction of the last segment of $\pi (v,q)$ to find the point $x$ where the extension of this segment hits $\partial P$.

3. 3.

   Insert $x$ into $T$.

The Dynamic Shortest Path data structure supports shortest path queries in $O({\log }^{2}m)$ time. We can also obtain the last segment on the shortest path using the chain trees representing the path. The ray shooting query that follows again takes $O({\log }^{2}m)$ time. Finally, inserting $x$ into $T$ takes just $O(\log k)$ time. As there are $O(k)=O(m)$ marked vertices, this takes $O(k{\log }^{2}m)$ time in total.

What remains is to find the bounded nearest neighbor queries using $T$. Each pair $s,t$ of consecutive points in $T$ defines such a query. If $s$ and $t$ are endpoints of the same marked edge, then their query region $R$ is a geodesic triangle, otherwise $R$ is a geodesic cone. The apex $v_R$ of the bounded nearest neighbor is the last marked vertex on $\pi (q,s)\cap \pi (q,t)$, or $q$ if there is no such vertex. We distinguish the following cases:

• $\mathrm{■}$

  If $s$ (or $t$) is a marked, then $v_R$ is the first (other) marked vertex on $\pi (s,q)$ (or $\pi (t,q)$).

• $\mathrm{■}$

  If both $s$ and $t$ are not marked, and thus included in $T$ in the ray shooting step, then $v_R$ is the second marked vertex on $\pi (s,q)$, i.e. the first vertex after the vertex used in the ray shooting step.

Note that in both cases $v_R$ is also on $\pi (t,q)$, as otherwise the ray shooting step on $v_R$ would add some point $x$ between $s$ and $t$ on $\partial P$ to $T$. Lemma 6 implies that we can find $v_R$ in $O({\log }^{2}m)$ time (to find the second marked vertex we can search the corresponding chain tree from the first marked vertex in $O(\log m)$ time). $◀$

We first prove the first part of the lemma, and then show how to find these type (a) and (b) queries efficiently. Figure 5 illustrates which nodes and edges we query. Let $(R,q)$ be a bounded nearest neighbor query. The region $R$ is either bounded by three shortest paths, or by two shortest path and part of $\partial P$. We first consider one of these shortest path that bounds $R$. Let $\pi (s,t)$ be this shortest path, and let $v(s)$ and $v(t)$ be geodesic triangles in $𝒯$ that contain $s$ and $t$ respectively. Let $\sigma$ be the subset of nodes of $𝒯$ on the paths from $v(s)$ and $v(t)$ to the root of $𝒯$. Furthermore, let $P_{\sigma }$ be the union of the geodesic triangles in $\sigma$, i.e. $P_{\sigma }={\bigcup }_{\delta \in \sigma }\delta$. We claim that $\pi (s,t)$ is contained $P_{\sigma }$. Indeed, consider a deltoid region $\mathrm{\Delta }$ that is entered by $\pi (s,t)$ of a geodesic triangle $\delta \notin \sigma$. Let $\pi (a,b)$ be the shortest path that is the boundary of $\delta$ through which $\pi (s,t)$ enters $\mathrm{\Delta }$. Note that by definition $a$ and $b$ are on $\partial P$. So, because $\pi (s,t)$ starts and ends in $P_{\sigma }$, it should at some point reenter $P_{\sigma }$ by crossing $\pi (a,b)$ again. This contradicts $\pi (s,t)$ being a shortest path.

Let ${\sigma }^{\prime }$ be the the union of the $\sigma$ sets for the shortest paths bounding $R$, excluding any geodesic triangles that intersect none of the shortest paths bounding $R$. Observe that for any point $p\in P$ the subgraph of nodes in $𝒯$ whose geodesic triangle contains $p$ is connected. As each pair of shortest paths bounding $R$ has a common endpoint, the subgraph of ${\sigma }^{\prime }$ is also connected. For each $\delta \in {\sigma }^{\prime }$, we perform a type (a) query. Because $𝒯$ has height $O(\log m)$, we perform $O(\log m)$ of these queries. Together, these queries find the nearest neighbor of $q$ in $R$ for all geodesic triangles whose intersection with one of the shortest paths bounding $R$ is non-empty. Clearly, any node whose deltoid region is intersected by such a shortest path is in ${\sigma }^{\prime }$. Any site that is on the boundary of a geodesic triangle intersected by such a shortest path is stored in the highest node in $𝒯$ that contains the site. As this subset of nodes is connected, some node in ${\sigma }^{\prime }$ must contain this site.

What remains is to query the geodesic triangles that are fully contained in $R$. If $R$ is a geodesic triangle, no node in $𝒯$ can be contained in the interior of $R$, as there are no vertices of $P$ in its interior, and the corners of the geodesic triangle are vertices of $P$. If $R$ is a geodesic cone, there might be $O(m)$ nodes in $𝒯$ contained inside $R$ that do not intersect the two bounding paths. Because $R$ is connected, there is an edge $(\delta ,x)$ in $𝒯$, with $\delta$ the parent of $x$, whose removal splits $𝒯$ into two subtrees, one of which contains exactly the geodesic triangles that are fully contained in $R$. If this subtree is ${𝒯}_x$ (recall that ${𝒯}_x$ is the subtree rooted at $x$), then we perform a type (b) query on $(\delta ,x)$. If the subtree is $𝒯\setminus {𝒯}_x$, then for each node on the path from $\delta$ to the root, we perform a type (a) query and a type (b) query for the incident edge not on this path.

Finally, we prove the second part of the lemma. We first compute the set ${\sigma }^{\prime }$. Consider one of the shortest paths $\pi (s,t)$ that bounds $R$. We first perform a point location query for both $s$ and $t$. This gives us two nodes $v(s),v(t)$ in $𝒯$ that contain $s$ and $t$. We then find the lowest common ancestor $w$ of $v(s)$ and $v(t)$ in $O(\log m)$ time. All nodes on the paths from $v(s)$ and $v(t)$ to $w$ are in ${\sigma }^{\prime }$. Note that the previous argument that $\pi (s,t)$ cannot cross a geodesic triangle boundary and return even implies that $\pi (s,t)$ is contained in the subpolygon correspoding to these nodes. However, there may be more nodes on the path from $w$ to the root of $𝒯$ whose boundary intersects $\pi (s,t)$. Let $\pi (p,r)$ be the shortest path that is the boundary between $w$ and its parent geodesic triangle. Lemma 10 implies that we can find the first point $a$ and the last point $b$ of $\pi (s,t)\cap \pi (p,r)$, or conclude the paths are disjoint, in $O({\log }^{2}m)$ time. Any geodesic triangle in $𝒯$ above $w$ that intersects $\pi (s,t)$ intersects either $a$ or $b$ (or both). It follows we can find the highest node of $𝒯$ that intersects $\pi (s,t)$ by a point location query on $a$ and $b$, and choosing the highest node of the returned nodes. All nodes on the path in $𝒯$ from $w$ and to this node are in ${\sigma }^{\prime }$. By following the same procedure for all shortest path bounding $R$, we can compute ${\sigma }^{\prime }$ in $O({\log }^{2}m)$ time.

If $R$ is a geodesic triangle, we are finished. If $R$ is instead a geodesic cone, we need to find the edge whose removal splits off the fully contained geodesic triangles as described earlier. Note that this edge must be incident to ${\sigma }^{\prime }$. Let $s$ and $t$ be the endpoints other than $q$ of the shortest paths that bound $R$. We first find the subsequence of polygon vertices contained in $R$ by a point location query for $s$ and $t$. By storing the boundary of $P$ in a balanced tree, we can then find the subsequence of vertices between the edges containing $s$ and $t$ in $O(\log m)$ time. For each node in ${\sigma }^{\prime }$, we check whether the incident edge that is not in ${\sigma }^{\prime }$ is contained in $R$ by checking whether its endpoints are contained in the subsequence in $O(\log m)$ time. We thus find the desired edge of $𝒯$ in $O({\log }^{2}m)$ time. The required type (a) and (b) queries can then be found by traversing the tree as described before in $O(\log m)$ time. $◀$