Visibility Queries in Simple Polygons

In the following, after introducing notation in Section 2, we present our near-linear space data structure in Section 3. In Section 4, we describe our new polygon decomposition, which serves as a key component for the optimal-query-time data structure in Section 5 and the quadratic-space solution in Section 6. Due to the space limit, many details and proofs are omitted, but can be found in the full paper. The boundary case is also in the full paper.

A quadratic-space solution is given in [2]. We briefly review it below as it also serves as a subroutine in some of our later algorithms.

Let $R_d$ denote the halfplane to the right of the supporting line of $d$. If $q\notin R_d$, then ${\text{Vis}}_d(q)=\mathrm{\varnothing }$, so we assume $q\in R_d$. Let ${𝒜}_d$ be the arrangement in $R_d$ formed by the supporting lines of the bounding rays of all cones in $𝒞$. By Observation 2, points $q$ in the same cell of ${𝒜}_d$ share the same (combinatorial representation of) ${\text{Vis}}_d(q)$, and ${\text{Vis}}_d(q)$ of $q$ in adjacent cells differ by at most one element of $P_{\mathrm{\ell }}$. Since there are $O(n)$ cones, ${𝒜}_d$ has $O(n^2)$ cells.

We use persistent binary search trees [26, 14] to store the combinatorial representations of ${\text{Vis}}_d(q)$ for all cells of ${𝒜}_d$ in a total of $O(n^2)$ space and $O(n^2\log n)$ preprocessing time. Additionally, we construct a point location data structure on ${𝒜}_d$ in $O(n^2)$ time and space [26, 22, 15]. Given a query point $q$, we can locate the cell of ${𝒜}_d$ containing $q$ in $O(\log n)$ time and thereby obtain access to the corresponding binary search tree that stores ${\text{Vis}}_d(q)$. This yields a data structure of complexity $O(n^2\log n,n^2,\log n)$, i.e., $O(n^2\log n)$ preprocessing time, $O(n^2)$ space, and $O(\log n)$ query time for computing $\text{Vis}(P_{\mathrm{\ell }},q)$ for any $q\in P_r$.

In the boundary case, each query point $q$ is on $\partial P\cap P_r$. In this case the cone stabbing queries become 1D interval stabbing queries on $\partial P\cap P_r$. Using persistent trees [26, 14], we obtain a data structure of complexity $O(n\log n,n,\log n)$. This result combining with the algorithmic framework given in Section 3.3 yields a data structure of complexity $O(n{\log }^{2}n,n\log n,{\log }^{2}n)$ for computing $\text{Vis}(q)$. See the full paper for details.

Our algorithm computes a collection of “canonical subsets” of $𝒞$, where each subset is represented by a binary search tree storing the cone generators in their index order. We perform a clipping operation on each tree using the cone $C_s(q)$. The elements remaining in the clipped trees of all canonical subsets collectively form the set $A_s(q)$, which consists of the elements of $P$ lying on $\partial {\text{Vis}}_s(q)$. We then sort the elements of $A_s(q)$ by their index order to obtain ${\text{Vis}}_s(q)$. Finally we build a binary search tree to store them and return this tree as the answer to the query. The details are given below.

We adapt Chan and Zhang’s data structure [5, Section 3.1] for simplex stabbing queries (given a query point $q$, compute all simplices stabbed by $q$ among a set of given simplices; each of our cones is a special simplex in 2D). The data structure has multiple levels and it is constructed using Matoušek’s simplicial partition [24]. To solve our problem, we can build the data structure on the cones of $𝒞$ with $j=2$ levels. We briefly discuss this and the reader is referred to [5, Section 3.1] for details.

Determining whether $q$ is in a cone is equivalent to testing whether $q$ is in the intersection of two halfplanes bounded by the cone’s bounding lines. In the dual plane, this is to check whether the dual line $q^{\ast }$ of $q$ lies in the “correct” side of the two dual points of the bounding lines of the cone. We apply Matoušek’s simplicial partition [24] on the dual points of the $j$-th halfplanes of the cones of $𝒞$, with $j=2$. For each cell $\mathrm{\Delta }$ of the partition that intersects $q^{\ast }$, we recurse on the canonical subset of the dual points of $\mathrm{\Delta }$. For each cell $\mathrm{\Delta }$ lying entirely below $q^{\ast }$ (or above $q^{\ast }$, depending on which is the correct side), we recurse on the canonical subset of $\mathrm{\Delta }$ but as a level-($j-1$) problem. For each canonical subset in a level-0 problem, we build a binary search tree to store all generators of cones in the subset. Following the analysis in [5, Section 3.1], the resulting data structure is of $O(n)$ space and can be constructed in $O(n\log n)$ time.

Given a query point $q$, the query algorithm returns $O(n^{1/2+ϵ})$ canonical subsets whose union corresponds to the set of cones of $𝒞$ stabbed by $q$. For each canonical subset, we perform a clipping operation using the cone $C_q(s)$, taking $O(\log n)$ additional time. Hence, we can compute $A_s(q)$ in $O(n^{1/2+ϵ}\log n+|A_s(q)|)$ time, which simplies to $O(n^{1/2+ϵ}+|A_s(q)|)$ since the $\log n$ factor is absorbed by $n^{ϵ}$.

Once $A_s(q)$ is obtained, we must sort its elements by their index order. A straightforward comparison sort would require $O(|A_s(q)|\log |A_s(q)|)$ time, introducing an undesired logarithmic factor in the overall query time. However, since the index of each element of $A_s(q)$ is an integer in $[1,2n]$, we can perform the sorting in $O(n^{ϵ}+|A_s(q)|)$ time using radix sort in the following lemma.

Let $I$ denote the set of indices of the elements in $A_s(q)$, and our goal is to sort the integers in $I$. Since each index in $I$ is an integer in $[1,2n]$, it can be represented using at most $\log n+1$ bits. We partition these $\log n+1$ bits into $O(1)$ groups, each consisting of $ϵ\log n$ bits. We refer to each such group as a digit. Hence, each integer in $I$ has $O(1)$ digits. We apply radix sort on the integers of $I$ using these digits. Sorting $I$ by a single digit requires $O(2^{ϵ\log n}+|I|)=O(n^{ϵ}+|I|)$ time. Since there are only $O(1)$ digits, the entire sorting process takes $O(1)$ passes, resulting in a total running time of $O(n^{ϵ}+|I|)$. $◀$

After $A_s(q)$ is sorted, we obtain the combinatorial representation of ${\text{Vis}}_s(q)$. We then construct a binary search tree to store this representation in an additional $O(|{\text{Vis}}_s(q)|)$ time. Combining all the above results yields the following lemma.

We only sketch the proof here; full details can be found in the full paper.

Consider the root $v^{\ast }$ of $\mathrm{\Psi }$. For each geodesic triangle $\mathrm{△}$ in the core $P_{\text{core}}(v^{\ast })$, we build the data structure of Lemma 7 for $\mathrm{△}$ in $P_{v^{\ast }}$ (which equals $P$). We can show that this construction requires $O(n^2{\log }^{4}n)$ space and $O(n^2{\log }^{5}n)$ preprocessing time. Afterward, for any query point $q\in P$, if $q\in P_{\text{core}}(v^{\ast })$, we can compute $\text{Vis}(P_{v^{\ast }},q)$ in $O(\log n)$ time; and if $q\in P_v$ for a child $v$ of $v^{\ast }$, we can compute $\text{Vis}(P_{v^{\ast }}\setminus P_v,q)$ in $O(\log n)$ time.

In general, for each node $v\in \mathrm{\Psi }$, and for each geodesic triangle $\mathrm{△}$ in $P_{\text{core}}(v)$, we build the data structure of Lemma 7 for $\mathrm{△}$ within $P_v$. This requires $O(n_v^2{\log }^4{n}_v)$ space and $O(n_v^2{\log }^5{n}_v)$ preprocessing time, where $n_v=|P_v|$. Since the sizes of the subpolygons $P_v$ decrease geometrically along every root-to-leaf path, and since the subpolygons $P_v$ of nodes at the same level of $\mathrm{\Psi }$ are interior disjoint, the total space over all nodes of $\mathrm{\Psi }$ is $O(n^2{\log }^{4}n)$, and the total preprocessing time is $O(n^2{\log }^{5}n)$. After this preprocessing, the queries can be answered as stated in the theorem. $◀$

We prove the lemma by induction. Initially, if $v$ is a child of the root $v^{\ast }$, then since $d_v$ separates $P_v$ from $P_u\setminus P_v$, $u=v^{\ast }$, and $P_{v^{\ast }}=P$, it is vacuously true that $d_v$ separates $P_v$ from $P\setminus P_v$.

We now inductively assume that $d_u$ separates $P_u$ from $P\setminus P_u$. We next argue that $d_v$ separates $P_v$ from $P\setminus P_v$. Indeed, consider two points $p$ and $p^{\prime }$ with $p\in P_v$ and $p^{\prime }\in P\setminus P_v$. It suffices to show that the geodesic path $\pi (p^{\prime },p)$ must intersect $d_v$. If $p^{\prime }$ is in $P_u$, then since $d_v$ separates $P_v$ from $P_u\setminus P_v$, then $\pi (p^{\prime },p)$ must intersect $d_v$. If $p^{\prime }\notin P_u$, then $p^{\prime }\in P\setminus P_u$. In this case, since $p\in P_v\subseteq P_u$, $d_u⊈P_v$, and $d_u$ separates $P_u$ from $P\setminus P_u$, if we traverse from $p^{\prime }$ to $p$ along $\pi (p^{\prime },p)$, we must first cross $d_u$ and then $d_v$. The lemma thus follows. $◀$

We next describe our decomposition. We will focus on explaining the children $v$ of $v^{\ast }$. Specifically, we will define the core $P_{\text{core}}(v^{\ast })$, the subpolygons $P_v$, and the gate $d_v$ for every child $v$ of $v^{\ast }$. In particular, we will argue that the following three key properties hold for each $v$: (1) $P_v$ is separated from $P\setminus P_v$ by $d_v$; (2) $d_{v^{\ast }}$ is not in $P_v$; (3) $P_v$ has no more than $n/2$ edges other than the gate $d_v$. Note that the first two properties are those required in Lemma 9. To define the whole tree $\mathrm{\Psi }$, we simply apply the same decomposition recursively on $P_v$ for each child $v$ of $v^{\ast }$.

Let $p^{\ast }=p_{n/2}$, the middle point of $\partial P$ (recall that vertices of $P$ are indexed from $p_1$ to $p_n$ clockwise around $\partial P$). We consider the geodesic triangle ${\mathrm{△}}^{\ast }$ formed by the three geodesic paths $\pi (p^{\ast },p_1)$, $\pi (p^{\ast },p_n)$, and $\pi (p_1,p_n)$. Note that $\pi (p_1,p_n)$ is the edge $d_{v^{\ast }}=\overline{p_1{p}_n}$. We first consider the general case where ${\mathrm{△}}^{\ast }$ is not empty, and we will discuss later that the empty case can be treated similarly. We add ${\mathrm{△}}^{\ast }$ to the core $P_{\text{core}}(v^{\ast })$.

Note that $d_{v^{\ast }}$ is one side of ${\mathrm{△}}^{\ast }$ and thus $p_1$ and $p_n$ are two apexes of ${\mathrm{△}}^{\ast }$. Let $b^{\ast }$ be the third apex (see Figure 6). Note that $\partial {\mathrm{△}}^{\ast }\setminus d_{v^{\ast }}$ is the union of the other two sides of ${\mathrm{△}}^{\ast }$.

Let $B_1$ denote the boundary of $P$ from $p_1$ clockwise to $p^{\ast }$ and $B_2$ the boundary of $P$ from $p^{\ast }$ clockwise to $p_n$. We let both $B_1$ and $B_2$ contain $p^{\ast }$. Hence, $\partial P=B_1\cup B_2\cup d_{v^{\ast }}$. We say that a diagonal is a bridge if one vertex of it is in $B_1\setminus \{p^{\ast }\}$ while the other is in $B_2\setminus \{p^{\ast }\}$. By definition, if $b^{\ast }=p^{\ast }$, then $\partial {\mathrm{△}}^{\ast }\setminus d_{v^{\ast }}$ has no bridge; otherwise, $\partial {\mathrm{△}}^{\ast }\setminus d_{v^{\ast }}$ has exactly one bridge, denoted by $d^{\ast }$, which must have $b^{\ast }$ as a vertex (see Figure 6, where $d^{\ast }=\overline{a^{\ast }{b}^{\ast }}$).

For each diagonal $d$ of $\partial {\mathrm{△}}^{\ast }\setminus d_{v^{\ast }}$, if $d$ is not a bridge, then it connects two vertices either both on $B_1$ or both on $B_2$. Recall we defined in Section 4.1 that the notation $P_d({\mathrm{△}}^{\ast })$ refer to the pocket of $P$ separated by $d$ from ${\mathrm{△}}^{\ast }$ (see Figure 6). Observe that the edges of $P_d({\mathrm{△}}^{\ast })$ other than $d$ are all in $B_1$ or all in $B_2$. Hence, $P_d({\mathrm{△}}^{\ast })$ has no more than $n/2$ edges other than $d$. We create a child $v$ for $v^{\ast }$ in $\mathrm{\Psi }$ with $P_v=P_d({\mathrm{△}}^{\ast })$ and the gate $d_v=d$. In this way, $d_v$ separates $P_v$ from $P\setminus P_v$ and $d_{v^{\ast }}=\overline{p_1{p}_n}$ is not an edge of $P_v$. Hence, all three key properties hold for $v$.

If $d$ is a bridge, i.e., $d=d^{\ast }$, then $b^{\ast }\ne p^{\ast }$. In this case, $P_{d^{\ast }}({\mathrm{△}}^{\ast })$ contains vertices from both $B_1$ and $B_2$ (see Figure 6), and therefore, $P_{d^{\ast }}({\mathrm{△}}^{\ast })$ may have more than $n/2$ edges other than $d^{\ast }$. We therefore cannot simply create a child for $v^{\ast }$ as above and need to resort to other approaches as follows.

Let $a^{\ast }$ be the vertex of $d^{\ast }$ other than $b^{\ast }$ (see Figure 6). Then, $\pi (p^{\ast },a^{\ast })$ is a subpath of either $\pi (p^{\ast },p_1)$ or $\pi (p^{\ast },p_n)$. To simplify the notation, let $\mathbb{Q}=P_{d^{\ast }}({\mathrm{△}}^{\ast })$ and ${\pi }^{\ast }=\pi (a^{\ast },p^{\ast })$.

The geodesic path ${\pi }^{\ast }$ decomposes the pocket $\mathbb{Q}$ into subpockets each of which is bounded by a subpath of ${\pi }^{\ast }$ and a sequence of edges of $B_1$ or $B_2$. If a subpocket is bounded by a subpath of ${\pi }^{\ast }$ and a sequence of edges of $B_1$ (resp., $B_2$), we call it a $B_1$-bounded subpocket (resp., $B_2$-bounded subpocket); see Figure 7. For each subpocket $Q$, the subpath of ${\pi }^{\ast }$ on the boundary of $Q$ is called the base of $Q$. We say that $Q$ is closed if its base is a single edge; otherwise, it is open (see Figure 7).

For a closed subpocket $Q$, since its edges other than its base edge are either all from $B_1$ or all from $B_2$, the number of its edges other than its base is at most $n/2$, and $Q$ is separated from $P\setminus Q$ by its base edge. Hence, we create a child $v$ for $v^{\ast }$ in $\mathrm{\Psi }$ with $P_v=Q$ and $d_v$ as the base edge of $Q$. Clearly, $d_{v^{\ast }}$ is not in $P_v$. Hence, all three key properties hold for $v$.

If $Q$ is open, then we will need to further decompose it. The situation in this case becomes significantly more complicated and our main effort is to handle this case. Without loss of generality, we assume that $Q$ is $B_1$-bounded.

Define $Q^{\ast }=P\setminus \mathbb{Q}$. We consider $Q^{\ast }$ a special subpocket. Following our above definition, $Q^{\ast }$ is a closed subpocket since it has only one edge of ${\pi }^{\ast }$. To differentiate, when we say “subpockets of $P$”, we refer to all subpockets of $\mathbb{Q}$ and also $Q^{\ast }$; when we say “subpockets of $\mathbb{Q}$”, we only refer to the subpockets inside $\mathbb{Q}$. Unless otherwise stated, a subpocket of $P$ refers to any subpocket of $\mathbb{Q}\cup \{Q^{\ast }\}$.

To simplify the discussion, we assume that each edge $e$ of ${\pi }^{\ast }$ is a diagonal. Indeed, this is the most general case because if $e$ is an edge of $P$ then we can assume there is an infinitely small subpocket separated by $e$. With this assumption, $e$ is on the boundaries of two subpockets of $P$. In particular, if $p^{\ast }$ is a vertex of $e$, then one subpocket bounded by $e$ is closed while the other is open. In this case, we consider $e$ a bridge in the open subpocket but not a bridge in the closed one. In this way, we have the following observation.

To see this, since the base of $Q$ is a geodesic path (because it is a subpath of ${\pi }^{\ast }$) and $Q$ is a simple polygon, the base of $Q$ must be a concave chain, meaning that if we traverse on it, either we always make right turns or we always make left turns. Hence, the two end vertices of the base of $Q$ must be in $B_1$ while all other vertices are in $B_2$ because $Q$ is $B_1$-bounded (see Figure 7). This implies that among all edges on the base of $Q$, only the first and last edges are bridges. For other edges of $Q$ not on its base, by definition, each of them connects two vertices of $B_1$, meaning that it is not a bridge. $◀$

We say that two subpockets of $P$ are neighboring if they share a common edge of ${\pi }^{\ast }$. By definition, for two neighboring subpockets of $\mathbb{Q}$, one of them is $B_1$-bounded while the other is $B_2$-bounded. Also, a closed subpocket has exactly one neighboring subpocket while an open one has multiple. For any open subpocket $Q$, since only the first and last edges of its base are bridges, $Q$ has at most two neighboring open subpockets. The following simple observation implies that to compute $\text{Vis}(q)$ for a point $q\in Q$, it suffices to consider $Q$ and its neighboring subpockets.

Assume to the contrary $p$ is in other subpockets. Then, $\overline{pq}$ must cross two edges of ${\pi }^{\ast }$. Since ${\pi }^{\ast }$ is a geodesic path in $P$, no line segment in $P$ can cross two edges of ${\pi }^{\ast }$. We thus obtain contradiction. $◀$

With the above concepts, we next discuss how to further decompose an open subpocket $Q$ (again assume that $Q$ is $B_1$-bounded).

Let $\pi (Q)$ denote the base of $Q$. Let $p_i$ be the end vertex of $\pi (Q)$ that is closer to $a^{\ast }$ along ${\pi }^{\ast }=\pi (a^{\ast },p^{\ast })$ and $p_j$ the other end vertex (see Figure 7). By definition, . Note that if we traverse $\pi (Q)$ from $p_i$ to $p_j$, we always make right turns. For simplicity of discussion, we consider the order of vertices of $\pi (Q)$ from $p_i$ to $p_j$ as the left-to-right order so that we can use “left” and “right” to refer to the directions of $\pi (Q)$. Note that $\pi (Q)$ could be spiral. Let $B_1(Q)$ denote the portion of $B_1$ in $Q$. Hence, $p_i$ is the first vertex and $p_j$ is the last vertex of $B_1(Q)$ if we order vertices of $B_1(Q)$ along $B_1$ clockwise (and we also consider it the left-to-right order of $B_1(Q)$). Also, the union of $B_1(Q)$ and $\pi (Q)$ forms the boundary $\partial Q$ of $Q$.

We pick the middle vertex $p_k$ of $B_1(Q)$ with $k=(i+j)/2$, and connect $p_k$ to $p_i$ and $p_j$ by geodesic paths, which yields a geodesic triangle, denoted by ${\mathrm{△}}_k$. Since the base $\pi (Q)$ is a geodesic path and $p_k$ is not on $\pi$, ${\mathrm{△}}_k$ cannot be empty. One side of ${\mathrm{△}}_k$ is on $\pi (Q)$ and we call it the base side; the other two sides are called the non-base sides. Among the two non-base sides, the one that connects the leftmost vertex of the base side is called the left side while the other is called the right side (recall that we have a left-to-right order of $\pi (Q)$; since the base side is a subpath of $\pi (Q)$, we can talk about the “leftmost” and “rightmost” vertices). We add ${\mathrm{△}}_k$ to the core $P_{\text{core}}(v^{\ast })$ of the root $v^{\ast }$ of $\mathrm{\Psi }$.

Consider the left side of ${\mathrm{△}}_k$, denoted by ${\pi }_k^l$. Let $a$ be the leftmost vertex of the base side of ${\mathrm{△}}_k$. Depending on whether $a=p_i$, there are two cases.

• $\mathrm{■}$

  If $a=p_i$, then no edge of ${\pi }_k^l$ is a bridge and every edge of ${\pi }_k^l$ connects two vertices of $B_1$; see Figure 8. In this case, for each diagonal $d$ of ${\pi }_k^l$, all vertices of $Q_d({\mathrm{△}}_k)$ are in $B_1(Q)$, where $Q_d({\mathrm{△}}_k)$ is the subpolygon of $Q$ divided by $d$ that does not contain ${\mathrm{△}}_k$. Hence, $Q_d({\mathrm{△}}_k)$ has no more than $n/2$ edges other than $d$. We create a child $v$ for $v^{\ast }$ in $\mathrm{\Psi }$ with $P_v=Q_d({\mathrm{△}}_k)$ and gate $d_v=d$. Since $P_v$ does not contain $d_{v^{\ast }}$, all three key properties hold for $v$. In this case, the processing of the left side ${\pi }_k^l$ is done.

• $\mathrm{■}$

  If $a\ne p_i$, then $a$ is in $B_2$ and the edge of ${\pi }_k^l$ incident to $a$ must be a bridge (see Figure 9); let $b$ denote the other vertex of the edge. Note that none of the other edges of ${\pi }_k^l$ is a bridge. For each diagonal $d$ of ${\pi }_k^l$ with $d\ne \overline{ab}$, we create a child $v$ for $v^{\ast }$ in the same way as above. For $\overline{ab}$, the pocket $Q_{\overline{ab}}({\mathrm{△}}_k)$ now also contains vertices of $B_2$ (see Figure 9), and thus we cannot create a child for $v^{\ast }$ in the same way as above. Instead, we process $Q_{\overline{ab}}({\mathrm{△}}_k)$ recursively. The reason we can do this is the following. By definition, the union of $\pi (p_i,a)$, which is the portion of $\pi (Q)$ between $p_i$ and $a$, and $\overline{ab}$ is a subpath of $\pi (p_i,p_k)$ and thus it is the geodesic path $\pi (p_i,b)$. In fact, $\overline{ab}$ is tangent to $\pi (Q)$ at $a$. Since $Q_{\overline{ab}}({\mathrm{△}}_k)$ is a simple polygon with $\pi (p_i,b)$ on its boundary, $\pi (p_i,b)$ is also a concave chain and we can consider $\pi (p_i,b)$ as the base of $Q_{\overline{ab}}({\mathrm{△}}_k)$ (note that $\pi (p_i,b)$ also contains exactly two bridges at the two ends). Hence, $Q_{\overline{ab}}({\mathrm{△}}_k)$ has the same “structure” as $Q$ and thus we can apply the above processing recursively. Note that the number of vertices of $B_1$ in $Q_{\overline{ab}}({\mathrm{△}}_k)$ is at most $|B_1(Q)|/2$.