Quickest Visibility Queries in Polygonal Domains
Haitao Wang

arXiv:1703.03048v1 [cs.CG] 8 Mar 2017

Department of Computer Science
Utah State University, Logan, UT 84322, USA
haitao.wang@usu.edu

Abstract. Let s be a point in a polygonal domain P of h − 1 holes and n vertices. We consider a
quickest visibility query problem. Given a query point q in P, the goal is to find a shortest path in
P to move from s to see q as quickly as possible. Previously, Arkin et al. (SoCG 2015) built a data
structure of size O(n2 2α(n) log n) that can answer each query in O(K log2 n) time, where α(n) is the
inverse Ackermann function and K is the size of the visibility polygon of q in P (and K can be Θ(n) in
the worst case). In this paper, we present a new data structure of size O(n log h + h2 ) that can answer
each query in O(h log h log n) time. Our result improves the previous work when h is relatively small.
In particular, if h is a constant, then our result even matches the best result for the simple polygon
case (i.e., h = 1), which is optimal. As a by-product, we also have a new algorithm for a shortest-pathto-segment query problem. Given a query line segment τ in P, the query seeks a shortest path from s
to all points of τ . Previously, Arkin et al. gave a data structure of size O(n2 2α(n) log n) that can answer
each query in O(log2 n) time, and another data structure of size O(n3 log n) with O(log n) query time.
We present a data structure of size O(n) with query time O(h log nh ), which also favors small values of
h and is optimal when h = O(1).

1

Introduction

Let P be a polygonal domain with h − 1 holes and a total of n vertices, i.e., there is an outer simple
polygon containing h − 1 pairwise disjoint holes and each hole itself is a simple polygon. If h = 1,
then P becomes a simple polygon. For any two points s and t in P, a shortest path from s to t is a
path in P connecting s and t with the minimum Euclidean length. Two points p and q are visible
to each other if the line segment pq is in P. For any point q in P, its visibility polygon consists of
all points of P visible to q, denoted by Vis(q).
We consider the following quickest visibility query problem. Let s be a source point in P. Given
any point q in P, the query asks for a path to move from s to see q as quickly as possible. Such
a “quickest path” is actually a shortest path from s to any point of Vis(q). The problem has been
recently studied by Arkin et al. [1], who built a data structure of size O(n2 2α(n) log n) that can
answer each query in O(K log2 n) time, where K is the size of Vis(q). In this paper, we present a
new data structure of O(n log h + h2 ) size with O(h log h log n) query time. Our result improves the
previous work when h is relatively small. Interesting is that the query time is independent of K,
which can be Θ(n) in the worst case. Our result is also interesting in that when h = O(1), the data
structure has O(n) size and O(log n) query time, which even matches the best result for the simple
polygon case [1] and is optimal.
As in [1], in order to solve the quickest visibility queries, we also solve a shortest-path-to-segment
query problem (or segment query for short), which may have independent interest. Given any line
segment τ in P, the segment query asks for a shortest path from s to all points of τ . Arkin et
al. [1] gave a data structure of size O(n2 2α(n) log n) that can answer each query in O(log2 n) time,
and another data structure of size O(n3 log n) with O(log n) query time. We present a new data
structure of O(n) size with O(h log nh ) query time. Our result again favors small values of h and

attains optimality when h = O(1), which also matches the best result for the simple polygon
case [1,13].
Given the shortest path map of s, our quickest visibility query data structure can be built in
O(n log h + h2 log h) time and our segment query data structure can be built in O(n) time. Arkin et
al.’s quickest visibility query data structure and their first segment query data structure can both
be built in O(n2 2α(n) log n) time, and their second segment query data structure can be built in
O(n3 log n) time [1].
Throughout the paper, whenever we talk about a query related to paths in P, the query time
always refers to the time for computing the path length, and to output the actual path, it needs
additional time linear in the number of edges of the path by standard techniques (we will omit the
details about this).
1.1

Related Work

The traditional shortest path query problem has been studied extensively, which is to compute a
shortest path to move from s to “reach” a query point. Each shortest path query can be answered
in O(log n) time by using the shortest path map of s, denoted by SPM (s), which is of O(n) size.
To build SPM (s), Mitchell [28] gave an algorithm of O(n3/2+ǫ ) time for any ǫ > 0 and O(n) space,
and later Hershberger and Suri [22] presented an algorithm of O(n log n) time and space. If P is a
simple polygon (i.e., h = 1), SPM (s) can be built in O(n) time, e.g., see [17].
For the quickest visibility queries, Arkin et al. [1] also built a “quickest visibility map” of O(n7 )
size in O(n8 log n) time, which can answer each query in O(log n) time. In addition, Arkin et al. [1]
gave a conditional lower bound on the problem by showing that the 3SUM problem on n numbers
can be solved in O(τ1 + n · τ2 ) time, where τ1 is the preprocessing time and τ2 is the query time.
Therefore, a data structure of o(n2 ) preprocessing time and o(n) query time would lead to an o(n2 )
time algorithm for 3SUM.
In the simple polygon case (i.e., h = 1), better results are possible for both the quickest visibility
queries and the segment queries. For the quickest visibility queries, Khosravi and Ghodsi [24] first
proposed a data structure of O(n2 ) size that can answer each query in O(log n) time. Arkin et al. [1]
gave an improved result and they built a data structure of O(n) size in O(n) time, with O(log n)
query time. For the segment queries, Arkin et al. [1] built a data structure of O(n) size in O(n)
time, with O(log n) query time. Chiang and Tamassia [13] achieved the same result for the segment
queries and they also gave some more general results (e.g., when the query is a convex polygon).
Similar in spirit to the “point-to-segment” shortest path problem, Cheung and Daescu [12]
considered a “point-to-face” shortest path problem in 3D and approximation algorithms were given
for the problem.
1.2

Our Techniques

We first propose a decomposition D of P by O(h) shortest paths from s to certain vertices of
SPM (s). The decomposition D, whose size is O(n), has O(n) cells with the following three key
properties. First, any segment τ in P can intersect at most O(h) cells of D. Second, for each cell ∆
of D, τ ∩∆ consists of at most two sub-segments of τ . Third, after O(n) time preprocessing, for each
sub-segment τ ′ of τ in any cell of D, the shortest path from s to τ ′ can be computed in O(log n) time.
With D, we can easily answer each segment query in O(h log nh ) time by a “pedestrian” algorithm.
2

To solve the quickest visibility queries, an observation is that the shortest path from s to see q
is a shortest path from s to a window of Vis(q), i.e., an extension of the segment qu for some reflex
vertex u of P. Hence, the query can be answered by calling segment queries on all O(K) windows
of Vis(s) and returning the shortest path. This leads to the O(K log2 n) time query algorithm in
[1].
If we follow the same algorithmic scheme and using our new segment query algorithm, then we
would obtain an algorithm of O(K · h · log nh ) time for the quickest visibility queries. We instead
present a “smarter” algorithm. We propose a “pruning algorithm” that prunes some “unnecessary”
portions of the windows such that it suffices to consider the remaining parts of the windows. Further,
with the help of the decomposition D, we show that a shortest path from s to the remaining windows
can be found in O((K + h) log h log n) time. We refer to it as the preliminary result. To achieve this
result, we solve many other problems, which may be of independent interest. For example, we build
a data structure of O(n log h) size such that given any query point t and line segment τ in P, we
can compute in O(log h log n) time the intersection between τ and the shortest path from s to t in
P (or report none if they do not intersect). Our above pruning algorithm is based on a new and
interesting technique of using “bundles”.
To further reduce the query time to O(h log h log n), the key idea is that by using the extended
corridor structure of P [8,11], we show that there exists a set S(q) of O(h) candidate windows such
that a shortest path from s to see the query point q must be a shortest path from s to a window in
S(q). This is actually quite consistent with the result in the simple polygon case, where only one
window is needed for answering each quickest visibility query [1]. Once the set S(q) is computed, we
can apply our pruning algorithm discussed above on S(q) to answer the quickest visibility query in
additional O(h log h log n) time. To compute S(q), we give an algorithm of O(h log n) time, without
having to explicitly compute Vis(s). The algorithm is based on a modification of the algorithm
given in [9] that can compute Vis(q) in O(K log n) time for any point q, after O(n + h2 ) space and
O(n + h2 log h) time preprocessing.
The rest of the paper is organized as follows. In Section 2, we introduce notation and review
some concepts. In Section 3, we introduce the decomposition D of P, and present our algorithm
for the segment queries. We present our preliminary result for the quickest visibility queries in
Section 4 and give the improved result in Section 5. Section 6 concludes the paper.

2

Preliminaries

For any subset A of P, we say that a point p is (weakly) visible to A if p is visible to at least one
point of A. For any point t ∈ P, we use π(s, t) to denote a shortest path from s to t in P, and in
the case where the shortest path is not unique, π(s, t) may refer to an arbitrary such path. With a
little abuse of notation, for any subset A of P, we use π(s, A) to denote a shortest path from s to
all points of A; we use d(s, A) to denote the length of π(s, A), i.e., d(s, A) = mint∈A d(s, t).
Let V denote the set of all vertices of P.
The shortest path map SPM (s). SPM (s) is a decomposition of P into regions (or cells) such that
in each cell σ, the sequence of obstacle vertices along π(s, t) is fixed for all t in σ [22,28]. Further,
the root of σ, denoted by r(σ), is the last vertex of V ∪ {s} in π(s, t) for any point t ∈ σ (hence
π(s, t) = π(s, r(σ)) ∪ r(σ)t; note that r(σ) is s if s is visible to t). We classify each edge of a cell σ
into three types: a portion of an edge of P, an extension segment, which is a line segment extended
from r(σ) along the opposite direction from r(σ) to the vertex of π(s, t) preceding r(σ), and a
3

h

g

i
j
r

k

e

l

d
a
b

c

Fig. 1. Illustrating a planar tree T with root r: a is a base leaf and the list Ll (T, a) is a, b, c, . . . , l.

bisector curve/edge that is a hyperbolic arc. For each point t on a bisector edge of SPM (s), t is on
the common boundary of two cells and there are two different shortest paths from s to t through
the roots of the two cells, respectively. The vertices of SPM (s) include V ∪ {s} and all intersections
of edges of SPM (s). The intersection of two bisector edges is called a triple point, which has more
than two shortest paths from s. The map SPM (s) has O(n) vertices, edges, and cells [22,28].
For differentiation, we call the vertices and edges of the polygonal domain P the obstacle vertices
and the obstacle edges, respectively. The holes and the outer polygon of P are also called obstacles.
The shortest path tree SPT (s) is the union of shortest paths from s to all obstacle vertices
of P. SPT (s) has O(n) edges [22,28]. Given SPM (s), SPT (s) can be obtained in linear time. We
somethings consider a further decomposition of SPM (s) by having all edges of SPT (s) in it.
For ease of exposition, we make a general position assumption that no obstacle vertex has more
than one shortest path from s and no point of P has more than three shortest paths from s. Hence,
no bisector edge of SPM (s) intersects an obstacle vertex and no three bisector edges intersect at
the same point.
For any polygon P , we use |P | to denote the number of vertices of P and use ∂P to denote the
boundary of P .
Ray-shooting queries in simple polygons. Let P be a simple polygon. With O(|P |) time and space
preprocessing, each ray-shooting query in P (i.e., given a ray in P , find the first point on ∂P hit
by the ray) can be answered in O(log |P |) time [6,21]. The result can be extended to curved simple
polygons or splinegons [26].
The canonical lists and cycles of planar trees. We will often talk about certain planar trees in P
(e.g., SPT (s)). Consider a tree T with root r. A leaf v is called a base leaf if it is the leftmost leaf of
a subtree rooted at a child of r (e.g., see Fig. 1). Denote by L(T, v) the post-order traversal list of
T starting from such a base leaf v, and we call it a canonical list of T . The root r must be the last
node in L(T, v). We remove r from L(T, v) and make the remaining list a cycle by connecting its
rear to its front, and let C(T ) denote the circular list. Although T may have multiple base leaves,
C(T ) is unique and we call C(T ) the canonical cycle of T . We further use Ll (T, v) (e.g., see Fig. 1)
to denote the list of the leaves of T following their relative order in L(T, v) and use Cl (T ) to denote
the circular list of Ll (T, v). One reason we introduce these notation is the following. Let e be any
edge of T . All nodes of T whose paths to r in T contain e must be consecutive in L(T, v) and C(T ).
Similarly, all leaves of T whose paths to r in T contain e must be consecutive in Ll (T, v) and Cl (T ).
The following observation on shortest paths will be frequently referred to in the paper.

4

Observation 1 1. Suppose π1 and π2 are two shortest paths from s to two points in P, respectively; then π1 and π2 do not cross each other.
2. Suppose π1 is a shortest path from s to a point in P and τ is a line segment in P; then the
intersection of π1 and τ is a sub-segment of τ (which may be a single point or empty).

3

The Decomposition D and the Segment Queries

In this section, we introduce a decomposition D of P and use it to solve the segment query problem.
The decomposition D will also be useful for solving the quickest visibility queries.
We first define a set V of points. Let p be an intersection between a bisector edge of SPM (s)
and an obstacle edge. Since p is on a bisector edge, it is in two cells of SPM (s) and has two shortest
paths from s. We make two copies of p in the way that each copy belongs to only one cell (and
thus corresponds to only one shortest path from s). We add the two copies of p to V . We do this
for all intersections between bisector edges and obstacle edges. Consider a triple point p, which is
in three cells of SPM (s) and has three shortest paths from s. Similarly, we make three copies of p
that belong to the three cells, respectively. We add the three copies of p to V . We do this for all
triple points. This finishes the definition of V .
By definition, each point of V has exactly one shortest path from s. Let ΠV denote the set
of shortest paths from s to all points of V . Let TV be the union of all shortest paths of ΠV . We
consider points of V distinct although some of them are copies of the same physical point. In this
way, we can consider TV as a “physical” tree rooted at s.
Definition 1. Define D to be the decomposition of P by the edges of TV .
In the following, we assume the shortest path map SPM (s) has already been computed. We
have the following lemma about the decomposition D.
Lemma 1. 1. The size of the set V is O(h).
2. The combinatorial size of D is O(n).
3. Each cell of D is simply connected.
4. For any segment τ in P, τ can intersect at most O(h) cells of D. Further, for each cell ∆ of D,
the intersection τ and ∆ consists of at most two (maximal) sub-segments of τ .
5. After O(n) time preprocessing, for any segment τ ′ in a cell ∆ of D, the shortest path from s to
τ ′ can be computed in O(log |∆|) time, where |∆| is the combinatorial size of ∆.
6. For each cell ∆ of D, ∆ has at most two vertices r1 and r2 (both in V ∪ {s}), called “superroots”, such that for any point t ∈ ∆, π(s, t) is the concatenation of π(s, r) and the shortest
path from r to t in ∆, for a super-root r in {r1 , r2 }.
7. Given the shortest path map SPM (s), D can be computed in O(n) time.
We will prove Lemma 1 later in Section 3.2. Below we first give our data structure for answering
segment queries by using Lemma 1.
3.1

The Segment Queries

As preprocessing, we first compute the decomposition D. Then, we build a point location data
structure on D [14,25], which can be done in O(n) time and O(n) space since the size of D is O(n)
by Lemma 1(2); the data structure can answer each point location query in O(log n) time.
5

In addition, for each cell ∆ of D, by Lemma 1(3), ∆ is a simple polygon; we build a ray-shooting
data structure on ∆ [6,21]. Since the total size of all cells of D is O(n) by Lemma 1(2), the total
preprocessing time and space for the ray-shooting queries on all cells of D is O(n).
Finally, we do the preprocessing in Lemma 1(5). Hence, given SPM (s), the total preprocessing
time and space is O(n). The following lemma gives our query algorithm.
Lemma 2. Given any segment τ in P, we can compute a shortest path from s to τ in O(h log nh )
time.
Proof. Let a and b be the two endpoints of τ , respectively. Our algorithm works in a “pedestrian”
way, as follows.
By using a point location query, we find the cell ∆a of D that contains a. Then, we check
whether τ is contained in ∆a . This can be done by using a ray-shooting query as follows. We shoot
a ray ρ from a towards b and compute the first point p of ∂∆a hit by the ray. The segment τ is in
∆a if and only if b is before p on the ray.
If τ is in ∆a , then we can immediately compute the shortest path π(s, τ ) from s to τ in
O(log |∆a |) time by Lemma 1(5).
Otherwise, we compute the shortest path π(s, ap) from s to the sub-segment ap of τ in O(log |∆a |)
time by Lemma 1(5). Next, based on the edge of D containing p, we can determine in constant
time the next cell ∆ of P that the ray ρ enters. We process the cell ∆ in the similar way as the
above for ∆a . The algorithm finishes once we process a cell that contains b.
The above computes π(s, τ ′ ) for multiple sub-segments τ ′ of τ such that these sub-segments
constitute exactly τ and each sub-segment is in a single cell of D. Clearly, among all shortest paths
from s to these sub-segments, the one with the minimum length is the shortest path from s to τ .
To analyze the running time of the above algorithm, let k be the number of the above subsegments τ ′ of τ . Suppose τ1′ , τ2′ , . . . , τk′ are these sub-segments ordered from a to b. For each
1 ≤ i ≤ k, let ∆i be the cell of D that contains τi′ . First of all, the point location query for a takes
O(log n) time. For each 1 ≤ i ≤ k, determining each sub-segment τi′ needs a ray-shooting query in
∆i , which takes O(log |∆i |) time; computing the length of π(s, τi′ ) also takes O(log |∆i |) time by
P
Lemma 1(5). Hence, the total time of the algorithm is O(log n + ki=1 log |∆i |).
By Lemma 1(4), k = O(h). Also, by Lemma 1(4), each cell may contain two of the above k
sub-segments of τ , and thus it is possible that ∆i and ∆j refer to the same cell for i 6= j. Let S be
the set of the distinct P
cells of ∆i for i = 1,
P2, . . . , k. Since each cell contains at most two of the above
k
k sub-segments
of
τ
,
log
|∆
|
≤
2
·
since the cells of S are distinct, we
i
i=1
∆∈S log |∆|. Further,
P
P
have ∆∈S |∆| = O(n). Due to |S| ≤ k = O(h), we have ∆∈S log |∆| = O(h log nh ).
⊔
⊓
Therefore, the total time of the algorithm is bounded by O(h log nh ).
We summarize our result for segment queries in the following theorem.
Theorem 1. Given the shortest path map SPM (s), we can build a data structure of O(n) size in
O(n) time, such that each segment query can be answered in O(h log nh ) time.
3.2

The Decomposition D and Proving Lemma 1

In this section we provide the details for D and prove Lemma 1.
Let O denote the obstacle space, which is the complement of the free space of P. More specifically, O consists of the h − 1 simple polygonal holes of P and the (unbounded) region outside the
6

Fig. 2. Illustrating the bisector edges of shortest path map (the back area is the obstacle space): the green point is
the source s and the red curves are the bisector edges. The figure is generated by the applet in [20]

outer boundary of P. Let B denote the union of all bisector edges of SPM (s). Mitchell [27] proved
that O ∪ B is simply connected and P \ B is also simply connected (e.g., see Fig. 2). We consider
O ∪ B as a planar graph G, defined as follows.
The vertex set of G consists of all obstacles of O and all triple points of SPM (s). For any two
vertices of G, if they are connected by a chain of bisector edges in SPM (s) such that the chain does
not contain any other vertex of G, then G has an edge connecting the two vertices, and further,
we call the above chain of bisector edges a bisector super-curve (e.g., in Fig. 2, each red curve is a
bisector super-curve). We have the following observation about G.
Observation 2 G is a simple graph, i.e., G does not have a self-loop and no two vertices have
more than one edge. G has O(h) vertices, edges, and faces.
Proof. The first part of the observation can be proved easily from Mitchell’s observation in [27]
that P \ B is simply connected, as follows.
Indeed, assume to the contrary that G has a self-loop at a vertex v. According to our definition,
the self-loop corresponds to a bisector super-curve that connects the vertex v (either a triple point
or an obstacle) to itself. Let R be region bounded by bisector-super curve and v. Hence, R is closed,
which contradicts with that P \ B is simply connected.
Similarly, assume to the contrary that two vertices u and v have two edges. Then, the two edges
correspond to two bisector super-curves. Thus, the region bounded by the two bisector super-curves
and the two vertices is closed, incurring contradiction again.
To prove the second part of the observation, note that G is a planar graph.
First, it is known that the number of triple points is O(h) [15]. Since there are h obstacles in
O, the number of vertices of G is O(h).
Second, the faces of G correspond exactly to the faces of the (≤ 1) − SPM of P defined in [15],
whose total number is proved to be O(h) [15] (see Lemma 4.3 with k = 1). Therefore, the number
of faces of G is O(h).
Finally, since both the number of vertices and the number of faces of G are O(h), the number
of edges of G is also O(h).
⊔
⊓
Let V1 be the set of all triple points. It is known that |V1 | = O(h) [15]. Let V2 be the set of
intersections between obstacle edges and bisector edges of SPM (s). It is not difficult to see that
each point of V2 corresponds to an intersection between an obstacle and a bisector super-curve.
Since G has O(h) edges, there are O(h) bisector super-curves. Thus, |V2 | = O(h). Recall that V
7

consists of three copies of each point of V1 and two copies of each vertex of V2 . Since both |V1 | and
|V2 | are O(h), we have |V | = O(h). This proves Lemma 1(1).
Since |V | = O(h), ΠV is the set of O(h) shortest paths. Note that each edge of any path of
ΠV except the last edge (i.e., the one connecting a point of V ) is an edge of the shortest path tree
SPT (s). Hence, the total number of edges of the tree TV is O(n). Since D is the decomposition of
P by the edges of TV , the combinatorial size of D is O(n). This proves Lemma 1(2).
Throughout the paper, let h∗ = |V |. Hence, h∗ = O(h).
To prove the rest of Lemma 1, we introduce another decomposition D ′ as follows.
Definition 2. Define D ′ to be the decomposition of P by the edges of TV ∪ B.
By definition, D can be obtained from D ′ by removing all bisector edges of B.
Lemma 3. Each cell of D ′ is simply connected.
Proof. Let Q0 be the decomposition of P by the edges of B. Note that Q0 is exactly P \ B, which
is simply connected [27].
Let the points of V be v1 , v2 , . . . , vh∗ , ordered arbitrarily. Consider the decomposition Q1 of Q0
by the shortest path π(s, v1 ). Note that Q1 may have more than one connected cell. Recall that v1
is on a bisector edge of B. Since Q0 is simply connected, π(s, v1 ) does not cross any bisector edges
of SPM (s), and π(s, v1 ) itself does not form any cycle, each cell of Q1 is simply connected.
Similarly, consider the decomposition Q2 of Q1 by the shortest path π(s, v2 ). Again, π(s, v2 )
does not cross any bisector edge of B. Further, by Observation 1(1), π(s, v2 ) and π(s, v1 ) do not
cross each other. Hence, π(s, v2 ) does not cross any edge of Q1 . Since each cell of Q1 is simply
connected, each cell of Q2 is also simply connected.
We keep considering the rest of the paths π(s, vi ) for i = 3, 4, . . . , h∗ one by one in the same
way as above. By the similar argument we can obtain that each cell of Dh∗ , which is D ′ , is simply
connected.
⊔
⊓
It is known that P \ B is simply connected and π(s, t) is in P \ B for any point t ∈ P [27].
To simplify the discussion, together with the copies of the points of V , we consider P ′ = P \ B as
a simple polygon (with some curved edges) by making two copies for each interior point of every
bisector super-curve such that they respectively belong to the two sides of the curve. In this way,
for any point t ∈ P ′ , it has a unique shortest path π(s, t) from s in P ′ , which is also a shortest path
in P. In this way, D ′ becomes a decomposition of P ′ by the tree TV .
Consider any cell ∆′ of D ′ . Recall that V is the set of all vertices of P. We consider the points
of V ∪ V ∪ {s} on the boundary ∂∆′ of ∆′ as vertices of ∆′ . Then, the boundary portion between
any two adjacent vertices of ∆′ is an obstacle edge, an edge of TV , or a bisector super-curve. Let p
be any point of ∆′ . Let r∆′ be the point of ∆′ ∩ π(s, p) closest to s. We call r∆′ the super-root of
∆′ , which is unique (i.e., independent of p) due to the following lemma.
Lemma 4. 1. The point r∆′ is in V ∪ {s}, i.e., it is either s or an obstacle vertex.
2. π(s, r∆′ ) is a sub-path of a shortest path in ΠV .
3. For any point t ∈ ∆′ , the concatenation of π(s, r∆′ ) and the shortest path from r∆′ to t in ∆′
is the shortest path π(s, t) from s to t in P ′ .
Proof. We prove the lemma by induction in a similar way as in Lemma 3. We use the same
terminology as in the proof of Lemma 3. Let the points of V be v1 , v2 , . . . , vh∗ , ordered arbitrarily.
8

Let Q0 = P \ B. For each 1 ≤ i ≤ h∗ , let Qi denote the decomposition of Qi−1 by π(s, vi ). We let
Π0 = ∅. For each 1 ≤ i ≤ h∗ , let Πi = Πi−1 ∪ {π(s, vi )}. Hence, ΠV = Πh∗ .
Initially, consider the decomposition Q0 . Note that there is only one cell ∆′ in Q0 . Clearly,
r∆′ = s and all three statements hold for Q0 and Π0 . We assume the lemma statements hold for
Qi−1 and Πi−1 . Our goal is to prove that the lemma statements hold for Qi and Πi .
Let ∆′ be the cell of Qi−1 containing vi . By induction, π(s, vi ) is the concatenation of π(s, r∆′ )
and the shortest path π(r∆′ , vi ) from r∆′ to vi in ∆′ . Also by induction, π(s, r∆′ ) is a sub-path of
Πi−1 . Hence, π(s, vi ) does not partition any cell of Qi−1 other than ∆′ . In other words, for any cell
∆′′ of Qi−1 , if ∆′′ 6= ∆′ , then ∆′′ is still in Qi , and thus the lemma statements still hold on ∆′′ and
Πi .
For the cell ∆′ , π(r∆′ , vi ) partitions ∆′ into multiple sub-cells. Consider any sub-cell δ of ∆′ .
Our goal is to show that the lemma statements hold on δ and Πi . Depending on whether δ contains
r∆′ , there are two cases.
The case r∆′ ∈ δ. We first consider the case where δ contains r∆′ . Consider any point p in δ. Since
δ ⊆ ∆′ , r∆′ ∈ δ, and the point of ∆′ ∩ π(s, p) closest to s is r∆′ , the point of δ ∩ π(s, p) closest to s
is also r∆′ . Hence, rδ = r∆′ . By induction, the first and second statements of the lemma hold for δ
and Πi .
For the third statement, consider any point t ∈ δ. Since t ∈ ∆′ , π(s, t) is a concatenation of
π(s, r∆′ ) and π(r∆′ , t), and the latter path is in ∆′ . To prove the third statement, it sufficient to
show that π(r∆′ , t) is in δ. Indeed, assume to the contrary that π(r∆′ , t) is not in δ. Then, since δ
is a cell of the decomposition of ∆′ by π(r∆′ , vi ), π(r∆′ , t) must cross π(r∆′ , vi ). However, this is
not possible due to Observation 1(1). Hence, π(r∆′ , t) must be in δ.
The case r∆′ 6∈ δ. Suppose δ does not contain r∆′ . Let a be the point of π(r∆′ , vi ) ∩ δ closest to
r∆′ . We first show that for any point p ∈ δ, a is the point of π(s, p) ∩ δ closest to s.
Indeed, since p ∈ ∆′ , π(s, p) contains r∆′ and π(r∆′ , p) is in ∆′ . Since r∆′ is not in δ, let b be
the first point in δ we encounter if we traverse on π(r∆′ , p) from r∆′ to p. Clearly, b is not r∆′ since
otherwise r∆′ would be in δ. Since δ is a cell of the decomposition of ∆′ by π(r∆′ , vi ), b must be on
π(r∆′ , vi ). In other words, b ∈ δ ∩ π(r∆′ , vi ).
Since b is on both π(r∆′ , vi ) and π(r∆′ , p), b is also the first point in δ we encounter if we traverse
on π(r∆′ , vi ) from r∆′ to vi . Thus, b is the point of π(r∆′ , vi ) closest to r∆′ . Hence, we obtain b = a.
On the other hand, the definition of b implies that b is the point of π(s, p) ∩ δ closest to s.
Therefore, a is the point of π(s, p) ∩ δ closest to s. This implies that rδ = a.
Note that a is a vertex of π(r∆′ , vi ) and a cannot be vi . Thus, a must be either s or an obstacle
vertex (in fact, a cannot be s either due to a 6= r∆′ ), which proves the first statement of the lemma.
Since a is on π(r∆′ , vi ) and thus is on π(s, vi ), π(s, a) is a sub-path of π(s, vi ) ∈ Πi . This proves
the second statement of the lemma.
For the third statement, consider any point t ∈ δ. Since t ∈ ∆′ , by induction, π(s, t) is the
concatenation of π(s, r∆′ ) and π(r∆′ , t), and π(r∆′ , t) is in ∆′ . Using the same analysis as above,
we can show that π(r∆′ , t) must contain a. Further, the portion of π(r∆′ , t) between a and t must
be in δ, since otherwise π(r∆′ , t) would cross π(r∆′ , vi ), incurring contradiction. Hence, the portion
of π(r∆′ , t) between a and t is the shortest path from a to t in δ. Thus, π(s, t) is the concatenation
of π(s, a) and the shortest path from a to t in δ. This proves the third statement.
This proves that all lemma statements hold for δ and Πi , and thus hold for Qi and Πi .
The lemma thus follows.
⊔
⊓
9

Observation 3 Each cell ∆′ of D ′ has at most one bisector super-curve on its boundary.
Proof. Assume to the contrary there are two bisector super-curves on the boundary of ∆′ . Then,
there must exist an endpoint p of one of these two bisector super-curves such that the shortest path
π(s, p) partitions ∆′ into two cells that contain the two bisector super-curves, respectively. This
implies that π(s, p) is not in ΠV . Since the two endpoints of every bisector super-curve are in V ,
we obtain p ∈ V and π(s, p) is not in ΠV , a contradiction.
⊔
⊓
Since TV is a planar tree, we can define its canonical lists as discussed in Section 2. Let v1
be an arbitrary base leaf of TV , which can be found in O(n) time. Let the leaf list Ll (TV , v1 ) be
v1 , v2 , . . . , vh∗ , which follow the counterclockwise order along ∂P ′ .
For each 1 ≤ i ≤ h∗ , let αi denote the portion of ∂P ′ counterclockwise from vi to vi+1 (let vh∗ +1
refer to v1 ). Note that αi is either a bisector super-curve or a chain of obstacle edges. Suppose we
move a point t on αi from vi to vi+1 . The shortest path π(s, t) will continuously change with the same
topology since π(s, t) is always in P ′ (which is simply connected). Let Ri be the region of P ′ that
is “swept” by π(s, t) during the above movement of t. More specifically, let pi be the common point
on π(s, vi ) ∩ π(s, vi+1 ) that is farthest to s. Then, Ri is bounded by π(pi , vi ), π(pi , vi+1 ), and αi . For
convenience of discussion, we let Ri also contain the common sub-path π(s, pi ) = π(s, vi )∩π(s, vi+1 )
and we call π(s, pi ) the tail of Ri . We call the region bounded by π(pi , vi ), π(pi , vi+1 ), and αi the
cell of Ri . We consider π(s, vi ), π(s, vi+1 ), and αi as the three portions of the boundary ∂Ri of Ri .
The definition implies that for any point t in Ri , π(s, t) is in Ri . In fact, if t is in the cell of Ri ,
then π(s, t) is the concatenation of π(s, pi ) and the shortest path from pi to t in the cell. Clearly,
P ′ is the union of R1 , R2 , . . . , Rh∗ . Let R = {R1 , R2 , . . . , Rh∗ }. The next lemma is proved with the
help of the regions of R. The set R will also be quite useful in Section 4. Recall that each edge of
∂∆′ is either an obstacle edge, a bisector super-curve, or an edge of TV (also called a shortest path
edge).
Lemma 5. For each cell ∆′ of D ′ , there are two shortest paths of ΠV that contain all shortest path
edges of ∂∆′ .
Proof. By the definitions of the regions of R, ∆′ is contained in the cell of a region Ri of R.
Therefore, each shortest path edge of ∂D ′ belongs to either π(s, vi ) or π(s, vi+1 ).
⊔
⊓
Observe that the decomposition D can be obtain from D ′ by removing all bisector super-curves.
For any bisector super-curve α, the two cells of D ′ incident to α are merged into one cell of D. Due
to Observation 3, a cell of D ′ can be merged into at most one cell of D. Therefore, for each cell ∆
of D, either ∆ is also in D ′ or ∆ is a merged cell merged by exactly two cells of D ′ . Since every cell
of D ′ is simply connected, each cell of D is also simply connected. This proves Lemma 1(3).
Consider any line segment τ ∈ P. By Observation 1(2), τ can cross any shortest path of ΠV at
most once. Hence, τ can cross the shortest paths of ΠV at most O(h) times in total. Whenever τ
crosses the boundary of a cell of D, it must cross a shortest path of ΠV . Thus, τ can intersect O(h)
cells of D. This proves the first part of Lemma 1(4). For the second part, consider any cell ∆. By
Lemma 5, if ∆ is not a merged cell, then τ can cross the boundary of ∆ at most twice; otherwise,
τ can cross the boundary of ∆ at most four times. Therefore, the intersection τ ∩ ∆ consists of at
most two (maximal) sub-segments of τ . This proves the second part of Lemma 1(4).
In the sequel, we prove Lemma 1(5). Consider any cell ∆ of D. According to our discussion
above, ∆ is either in D ′ or a merged cell of two cells ∆1 and ∆2 of D ′ . If it is the former case,
10

then we also call r∆ the super-root of ∆; otherwise, we call r∆1 and r∆2 the two super-roots of ∆.
Lemma 4 leads to the following lemma, which proves Lemma 1(6).
Lemma 6. For any cell ∆ of D, the following hold.
1. Its two super-roots are in V ∪ {s}.
2. For each super-root r of ∆, π(s, r) is a sub-path of a shortest path in ΠV .
3. For any point t ∈ ∆, π(s, t) is the concatenation of π(s, r) and the shortest path from r to t in
∆, for a super-root r of ∆.
Proof. By Lemma 4, the proof is straightforward because either ∆ is a cell of D or a merge of two
cells of D.
⊔
⊓
Recall that for any simple polygon P and a fixed source point, each segment query can be
answered in O(log |P |) time after O(|P |) time preprocessing [1]. As preprocessing, for each cell ∆
of D, since it is a simple polygon, we compute the above segment query data structure with respect
to each super-root of ∆. This takes O(n) time and space in total by Lemma 1(2).
Consider any segment τ ′ in a cell ∆ of D. By Lemma 6, π(s, τ ′ ) is the concatenation of π(s, r)
from s to a super-root r of ∆ and the shortest path π(r, τ ′ ) from r to τ ′ in ∆. As r is in V ∪ {s} by
Lemma 6(1), π(s, r) is available from SPM (s), and π(r, τ ′ ) can be found in O(log |∆|) time. Hence,
our query algorithm works as follows. For each super-root r of ∆, we compute π(s, r) and π(r, τ ′ )
to obtain a “candidate” shortest path from s to τ ′ . Then, we return the shorter one of the at most
two candidates paths as the solution. The total time is O(log |∆|). This proves Lemma 1(5).
Remark. One may wonder why we do not use D ′ instead of D to answer the segment queries. The
reason is that the boundaries of cells of D ′ contain bisector super-curves and the query segment τ
may intersect a bisector super-curve multiple times, and thus a similar observation as Lemma 1(4)
cannot be guaranteed on D ′ .
Finally, we prove Lemma 1(7) in the following lemma.
Lemma 7. Given SPM (s), the decomposition D can be computed in O(n) time.
Proof. Let D1 be the decomposition of SPM (s) by the edges of SPT (s). As discussed before, we
can easily obtain SPT (s) from SPM (s) and thus obtain D1 in O(n) time. Further, for each point
v ∈ V , we add to D1 the last edge of the shortest path π(s, v), which is also the edge connecting v
to the root of the cell of SPM (s) containing v. Let D2 be the resulting decomposition, which can
be obtained in O(n) time. Note that each edge of TV is also an edge of D2 .
Since D is a decomposition of P by the edges of TV , D can be obtained from D2 by removing
those edges that are not in D. To this end, we first remove all bisector edges from D2 . Then, we
remove the edges of SPT (s) that are not in TV . This can be done by first marking all edges of TV in
D2 and then removing all unmarked edges of SPT (s) from D2 . Below we only discuss how to mark
all edges of TV in O(n) time since the latter step is trivial.
For each vertex v of V , we mark the edges of π(s, v) in D2 as follows. We start from v and
traverse along π(s, v) from v to s, marking every edge that has not been marked yet; we stop the
traversal either when we encounter s or we encounter an edge that has been marked. In this way,
every edge of TV is marked exactly once. Since TV has O(n) edges, the above marking algorithm
runs in O(n) time.
Thus, the decomposition D can be computed in O(n) time.
⊔
⊓
11

q
u
q(u)
Fig. 3. Illustrating a window uq(u) of q.

4

The Quickest Visibility Queries: The Preliminary Result

In this section, we give our preliminary result on quickest visibility queries, which sets the stage
for our improved result in Section 5.
For any subset A of P, a point p ∈ A is called a closest point of A (with respect to s) if
d(s, A) = d(s, p).
Given any query point q in P, our goal is to find a shortest path from s to Vis(q). Let q ∗ be a
closest point of Vis(q). To answer the query, it is sufficient to determine q ∗ . Thus we will focus on
finding q ∗ . Note that if q is visible to s, then q ∗ = s. We can determine whether s is visible to q in
O(log n) time by checking whether q is in the cell of SPM (s) whose root is s. In the following, we
assume s is not visible to q.
We define the windows of q and Vis(q), which were used for studying the visibility polygons,
e.g., [5,10]. Consider an obstacle vertex u that is visible to q such that the two incident obstacle
edges of u are on the same side of the line through q and u (e.g., see Fig. 3). Let q(u) denote the
first point on ∂P hit by the ray from u along the direction from q to u. Then uq(u) is called a
window of q; we say that the window is defined by u. Further, we call qq(u) the extended window of
uq(u).
Each window of q is an edge of Vis(q), and thus the number of windows of q is O(K), where
K = |Vis(q)|. Further, there must be a closest point q ∗ that is on a window of q [1]. Hence, as in [1],
a straightforward algorithm to compute q ∗ is to compute shortest paths from s to all windows
of s and the path of minimum length determines q ∗ . To compute shortest paths from s to all
windows, if we apply our segment queries on all windows using Theorem 1, then the total time
would be O(K · h · log nh ). In the rest of this section, we present an algorithm that can compute q ∗
in O((K + h) log h log n) time, without having to compute shortest paths to all windows. The key
idea is to prune some (portions of) windows such that q ∗ is still in the remaining windows and the
shortest paths from s to all remaining windows can be computed efficiently.
4.1

The Algorithm Overview

As the first step, we compute Vis(q), which can be done in O(K log n) time after O(n + h2 log h)
time and O(n + h2 ) space preprocessing [9]. Then, we can find all windows and extended-windows
in O(K) time. For ease of exposition, we make a general position assumption for q that q is not
collinear with any two obstacle vertices. The assumption implies that q is in the interior of P and
no two windows are collinear.
Let u0 be the root of the cell of SPM (s) containing q (if q is on the boundary of multiple cells,
then we take an arbitrary such cell). Hence, π(s, u0 )∪u0 q is a shortest path π(s, q) from s to q. Note
that u0 must define a window u0 q(u0 ) of q [27]. Let u0 q(u0 ), u1 q(u1 ), . . . , uk q(uk ) be all windows of
q ordered clockwise around q. Clearly, k = O(K). For each 0 ≤ i ≤ k, let qi = q(ui ).
12

Note that the window u0 q0 is special in the sense that u0 is in π(s, q). So we first apply our
algorithm in Theorem 1 on u0 q0 to compute the closest point q0∗ of u0 q0 . Clearly, if q ∗ ∈ u0 q0 , then
q ∗ = q0∗ . In the following, we assume q ∗ 6∈ u0 q0 . Let Q = {q, q1 , q2 , . . . , qk }. Note that Q does not
contain q0 but q. If q ∗ ∈ Q, then we can find q ∗ by computing d(s, p) for all p ∈ Q, which can be
done in O(k log n) time using SPM (s). In the following, we assume q ∗ 6∈ Q. Note that the above
assumption that q ∗ 6∈ u0 q0 ∪ Q is only for arguing the correctness of our following algorithm, which
actually proceeds without knowing whether the assumption is true or not.
For each 0 ≤ i ≤ k, let wi = qqi , i.e., the extended window of ui qi . Let W = {wi | 1 ≤ i ≤ k}.
For convenience of discussion, we assume that each wi of W does not contain its two endpoints
q and qi (but the endpoints of wi still refer to q and qi ). Since q ∗ 6∈ u0 q0 ∪ Q, q ∗ must be on an
extended window of W . Clearly, q ∗ is also a closest point of W . Since no two windows of q are
collinear, no extended-window of W contains another. We assign each window wi ∈ W a direction
from q to qi , so that we can talk about its left or right side.
Suppose q ∗ is on wi ∈ W . Since wi is an open segment, by the definition of q ∗ , the shortest path
π(s, q ∗ ) must reach q ∗ from either the left side or the right side of wi . Formally, we say that π(s, q ∗ )
reaches q ∗ from the left side (resp., right side) of wi if there is a small neighborhood of q ∗ such that
all points of π(s, q ∗ ) in the neighborhood are on the left side (resp., right side) of wi . Let wil (resp.,
wir ) denote the set of points p on wi whose shortest path from s to p is from the left (resp., right)
side of wi . Hence, q ∗ is either on wil or on wir .
Our algorithm will find two points ql∗ and qr∗ such that if q ∗ is on wil for some i ∈ [1, k], then
∗
q = ql∗ , and otherwise (i.e.,q ∗ is in wir for some i ∈ [1, k]), q ∗ = qr∗ .
In the following, we will only present our algorithm for finding ql∗ since the case for qr∗ is
symmetric. In the following discussion, we assume q ∗ is on wil for some i ∈ [1, k]. Note that this
assumption is only for arguing the correctness of our algorithm, which actually proceeds without
knowing whether the assumption is true.
The rest of this section is organized as follows. In Section 4.2, we discuss some observations,
based on which we describe our pruning algorithm in Section 4.3 to prune some (portions of)
segments of W such that q ∗ (= ql∗ ) is still in the remaining segments of W . In Section 4.5, we will
finally compute ql∗ (which will be q ∗ ) on the remaining segments of W . Some implementation details
of the algorithm are given in Sections 4.4 and 4.6. Section 4.7 summarizes the overall algorithm.
As will be clear later, our algorithm uses extended windows instead of windows because extended
windows can help us with the pruning.
4.2

Observations

For any point t ∈ P with s 6= t, and its shortest path π(s, t), we use t+ to denote a point on π(s, t)
infinitely close to t (but t+ 6= t). If t is on wil for some i ∈ [1, k], then t+ must be on the left side of
wi .
For any segment w of W , we say that w or a sub-segment of w can be pruned if it does not
contain q ∗ . Our pruning algorithm, albeit somewhat involved, is based on the following simple
observation.
Observation 4 For any point t ∈ wil for some i ∈ [1, k], if π(s, t+ ) intersects any segment w ∈ W
or an endpoint of it, then t can be pruned (i.e., t cannot be q ∗ ).
Proof. Let t′ be a point on π(s, t+ ) that is a point on any segment w ∈ W or an endpoint of it.
Clearly, t′ ∈ Vis(s) and d(s, t′ ) < d(s, t). Thus, t cannot be q ∗ .
⊔
⊓
13

f (6)
f (5)
f (4)

q5
q4
q
q2 3

f (3)

s

f (2)
f (1)

q6

q1
q

π0

Fig. 4. Illustrating the map f (·): f (1) = 1, f (2) = 2, f (3) = 5, f (4) = 4, f (5) = 6, and f (6) = 3. Note that the paths
could be “below” π0 , but for ease of exposition, we “flip” them above π0 , and this flip operation does not change the
topology of these paths.

Consider the shortest paths π(s, qi ) for i = 1, 2, . . . , k. To simplify the notation, let πi = π(s, qi )
for each i ∈ [1, k]. In particular, let π0 = π(s, q) (not π(s, q0 )). Recall that Q = {q, q1 , . . . , qk }. The
union of all paths πi for 0 ≤ i ≤ k forms a planar tree, denoted by TQ , with root at s. Consider
the canonical cycle C(TQ ) as defined in Section 2. Let CQ be the circular list of the points of Q
following their relative order in C(TQ ). We further break CQ into a list LQ at q, such that LQ
starts from q and all other points of LQ follow the counterclockwise order in CQ . Assume LQ is
{q, qf (1) , qf (2) , . . . , qf (k) }, i.e., the (i+1)-th point of the list is qf (i) ; e.g., see Fig. 4. So f (·) essentially
maps each point of Q \ {q} from its position in LQ to its position in the list {q1 , q2 , . . . , qk }. Hence,
f (1) . . . , f (k) is a permutation of 1, . . . , k, and f (i) 6= f (j) if i 6= j. The reason we introduce the
list LQ is that intuitively, for any 1 ≤ i < j ≤ k, the path πf (j) is counterclockwise from πf (i) with
respect to π0 around s. For convenience, we let f (0) = 0.
Later in Section 4.6 we will give the implementation details for the following lemma.
Lemma 8. Given SPM (s), after O(n) time preprocessing, we can compute the list LQ and thus
determine the map f (·) in O(k log n) time.
Observation 5 For any i ∈ [1, k], π0 does not contain qi and πi does not contain q.
Proof. Assume to the contrary that π0 contains qi for some i ∈ [1, k]. Since q is in π0 , by Observation 1(2), π0 = πi ∪ qi q. Recall that qq0 ∈ π0 . This implies that either qq0 contains qi or qqi contains
q0 , which further implies the two windows u0 q0 and ui qi are collinear. This incurs contradiction
since no two windows are collinear. Hence, π0 does not contain qi .
Assume to the contrary that πi contains q. Then, since both q and qi are in πi , by Observation 1(2), qqi is in πi . Hence, πi = π0 ∪qqi . Recall that u0 is the root of the cell of SPM (s) containing
q, and π0 = π(s, u0 ) ∪ u0 q. Since q is in the interior of P, u0 q and qqi must be collinear since otherwise there would be a shorter path from u0 to qi without containing qqi . Recall that ui ∈ qqi . Since
u0 q and qqi are collinear, the three points q, u0 , and ui are collinear. But this contradicts with our
general position assumption that q is not collinear with any two obstacle vertices.
⊔
⊓
Lemma 9. Suppose πj contains qi with i 6= j and i, j ∈ [1, k]. If i < j, then wj can be pruned;
otherwise, wi can be pruned.
Proof. We first discuss the case i < j. Consider the region D bounded by the closed curve that is the
union of wi , wj , and the subpath of πj between qi and qj (e.g., see Fig. 5(a)). By Observation 1(1),
14

πj

qi

qj

D

s

πj

qi

D

s
q

π0

qj
q

π0
(b)

(a)

Fig. 5. Illustrating the proof of Lemma 9: (a) the case i < j; (b) the case i > j.

πj does not cross π0 . Since i < j, wj is clockwise from wi with respect to w0 (which is the last edge
of π0 ). Hence, D must be locally on the left side of wj .
Consider any point t ∈ wjl . We show that t cannot be q ∗ . Recall that wj is an open segment,
so t is not q or qj . Since t ∈ wil , the point t+ must be in D. By the definition of D, s is not in
the interior of D. Hence, π(s, t+ ) must intersect the boundary of D. Since π(s, t+ ) cannot cross
the subpath of πj between qi and qj , π(s, t+ ) must intersect wi , wj , or a point of {q, qi , qj }. By
Observation 4, t cannot be q ∗ .
The above shows that t cannot be q ∗ . Thus, wj can be pruned.
For the case i > j, the argument is similar (e.g., see Fig. 5(b)). Since i > j, D must be locally
on the left side of wi . For any point t ∈ wil , using the similar argument as above, we can show that
t cannot be q ∗ . Thus, wi can be pruned.
⊔
⊓
Lemma 10 provides an algorithm to remove all extended-windows of W that can be pruned by
Lemma 9.
Lemma 10. Given SPM (s) and with O(n) time preprocessing, we can find in O(k log n) time all
segments of W that can be pruned by Lemma 9.
Proof. The task is to determine those indices i and j such that qi is contained in πj for i 6= j in
[1, k], after which we can determine whether wi or wj should be pruned by Lemma 9. Recall that
f (1), f (2), . . . , f (k) is a permutation of the indices of {1, 2, . . . , k}. Therefore, equivalently we can
determine those indices f (i) and f (j) such that qf (i) is contained in πf (j) for f (i) 6= f (j) in [1, k].
We actually do not need to explicitly find all such pairs, as shown below.
A key observation is that if qf (i) is contained in a path πf (j) with f (j) 6= f (i), then it must be
that j < i and qf (i) is contained in πf (m) for any m ∈ [j, i]. Indeed, if qf (i) is contained in a path
πf (j) with f (j) 6= f (i), then the subpath of πf (j) from s to qf (i) is πf (i) . According to the definition
of the map f (·), i.e., the list {qf (1) , qf (2) , . . . , qf (k) }, qf (i) must be after qf (j) in the list, i.e., j < i.
Further, for any m ∈ [j, i], qf (i) is in the path of the tree TQ from qf (m) to the root s, which is the
shortest path πf (m) .
Based on the above observation, our algorithm works as follows. We consider the points qf (i)
in the order of i = 1, 2, . . . , k. Suppose we are about to process qf (i) . The algorithm maintains a
stack S of indices in [1, i − 1] in increasing order (from bottom to top of S) such that for each
j ∈ [1, i − 1], if j 6∈ S, then wf (j) has been pruned. Initially we set S = ∅ before we process qf (1) .
In general, our algorithm processes qf (i) for any i ≥ 1 as follows.
If S = ∅, then we push i on top of S and proceed to process qf (i+1) . Otherwise, we first check
whether qf (i) is contained in πf (m) , where m is the top index on S.
1. If qf (i) 6∈ πf (m) , then qf (i) is not in any path πf (j) with j < m by the above observation. We
push i on top of S and then proceed on processing qf (i+1) .
15

2. If qf (i) ∈ πf (m) , then depending on whether f (i) < f (m), there are two cases.
(a) If f (i) < f (m), then by Lemma 9, we prune wf (m) and pop m from S. Then, we repeat the
same algorithm as above (i.e., first check whether S = ∅, and if not, check whether qf (i) is
contained in πf (m) , where m is the new top index of S).
(b) If f (i) > f (m), then by Lemma 9, we prune wf (i) and proceed on processing qf (i+1) .
The algorithm finishes once qf (k) has been processed. It is not difficult to see that if we can
check whether qf (i) is in πf (m) in O(c) time, then the algorithm runs in O(k ·c) time since each index
of [1, k] can be pushed or popped from S at most once. In the following, we show that c = O(log n)
after O(n) time preprocessing, and this will prove the lemma.
First of all, if both qf (i) and qf (m) are in the same cell σ of SPM (s), then qf (i) ∈ πf (m) if and
only if qf (i) ∈ r(σ)qf (m) , where r(σ) is the root of σ. Otherwise, if qf (i) is not in any edge of the
shortest path tree SPT (s), then qf (i) cannot be in πf (m) . Otherwise, suppose qf (i) is on an edge e
of SPT (s). We can find the edge e in O(log n) time by a point location query on the decomposition
of SPM (s) by the edges of SPT (s). Let v be an endpoint of e, and thus v is a node of SPT (s). Let
r be the root of the cell of SPM (s) containing qf (m) . Then, qf (i) is in πf (m) if and only if v is an
ancestor of r in SPT (s). Note that v is an ancestor of r if and only if the lowest common ancestor
of v and r is v. We can build a data structure on SPT (s) in O(n) time such that given any two
nodes of the tree, the lowest common ancestor can be found in constant time [3,18].
Hence, we can determine whether qf (i) ∈ πf (m) in O(log n) time after O(n) time preprocessing.
The lemma thus follows.
⊔
⊓
We apply the algorithm in Lemma 10 to prune the segments of W . But to simplify the notation,
we assume that none of the segments of W is pruned since otherwise we could re-index all segments
of W . So now W has the following property.
Observation 6 For any i ∈ [1, k], qi is not contained in any πj with j ∈ [0, k] and j 6= i.
Proof. Suppose to the contrary that qi is contained in πj for some j ∈ [0, k] and i 6= j. On the one
hand, due to Observation 5, j 6= 0. On the other hand, if j ∈ [1, k], then by Lemma 9 either wi or
wj would have already been removed from W .
⊔
⊓
For each i ∈ [1, k], since π0 does not cross πi , π0 ∪ πi ∪ wi forms a closed curve that separates
the plane into two regions, one locally on the left of wi and the other locally on the right wi . We
let Di denote the region locally on the left side of wi including π0 ∪ πi ∪ wi as its boundary (it is
possible that Di is unbounded). If π0 ∩ πi is a sub-path including at least one edge, then it is also
considered to be in Di . We have the following observation for Di .
Observation 7 If q ∗ ∈ wil , then π(s, q ∗ ) must be in Di .
Proof. Let t = q ∗ that is on wil . Then, t+ is in the interior of Di . By Observation 4, π(s, t+ ) cannot
intersect wi . Also, π(s, t+ ) cannot cross either π0 or πi , and s is on the boundary of Di . Hence,
π(s, t+ ) must be inside Di . Thus, π(s, q ∗ ) is in Di .
⊔
⊓
Our pruning algorithm mainly relies on the following lemma, whose proof in turn boils down
to Observation 4.
Lemma 11. Suppose i and j are two indices with 1 ≤ i < j ≤ k.
16

πf (j)

qf (j)

s

πf (i)

s
q

qf (i)

qf (i)

qf (j)

πf (i)
π0

πf (j)

πf (j)

qf (i)

s
q

π0

(a)

πf (i)

qf (j)

p
q

π0
(c)

(b)

Fig. 6. Illustrating Lemma 11.

1. If f (i) < f (j), then πf (i) does not cross wf (j) and πf (j) does not cross wf (i) , and further, Df (i)
is contained in Df (j) (e.g., see Fig. 6(a)).
2. If f (i) > f (j), then either πf (i) crosses wf (j) or πf (j) crosses wf (i) . Further, in the former
case (e.g., see Fig. 6(b)), wf (i) can be pruned, and in the latter case (e.g., see Fig. 6(c)), the
sub-segment qp of wf (i) can be pruned, where p is the point at which πf (j) crosses wf (i) .
Proof. Suppose f (i) < f (j). We first show that qf (j) cannot be in the interior of the region Df (i) .
Assume to the contrary that qf (j) is in the interior of Df (i) . Let pf (j) be a point on wf (j)
arbitrarily close to q (but pf (j) 6= q). Since f (i) < f (j), wf (j) is clockwise from wf (i) with respect
to w0 . Since q is not in πf (i) by Observation 5, pf (j) is not in Df (i) . Since qf (j) is in the interior of
Df (i) , πf (i) must cross wf (j) at a point p with p 6= qf (j) (e.g., see Fig. 7).

πf (i)

qf (i)

qf (j)
p

s
q

π0

Fig. 7. Illustrating the scenario where qf (j) is in the interior of Df (i) .

Depending on whether p ∈ πf (j) , there are two cases.
1. If p ∈ πf (j) , then since p ∈ wf (j) , we obtain πf (j) = π(s, p) ∪ pqf (i) by Observation 1(2). Since
qf (j) is in the interior of Df (i) , we further obtain that πf (i) is counterclockwise from πf (j) with
respect to π0 . Thus, we have i > j, a contradiction.
2. If p 6∈ πf (j) , then since i < j and πf (j) is counterclockwise from πf (i) with respect to π0 ,
πf (j) must cross an interior point p′ of qp before reaching qf (j) . This implies that πf (j) =
π(s, p′ ) ∪ p′ qf (j) by Observation 1(2), and thus, πf (j) contains p since p ∈ p′ qf (i) . Hence, we
again obtain contradiction.
This proves that qf (j) cannot be in the interior of the region Df (i) .
By Observations 5 and 6, qf (j) cannot be in π0 or πf (i) . Since no segment of W contains another,
qf (j) cannot be in wf (i) . Hence, qf (j) cannot be on the boundary of Df (i) . Therefore, qf (j) is outside
Df (i) . Next we show that πf (i) does not cross wf (j) .
Indeed, since both qf (j) and pf (j) are outside Df (i) , in order for πf (i) to cross wf (j) , πf (i) must
cross wf (j) at least twice, which is not possible by Observation 1(2). Similarly, in order for πf (j) to
cross wf (i) , it would have to cross wf (i) at least twice, which is not possible.
17

s
q

π0

Fig. 8. The thick (red) segments are the remaining parts of the segments of W after the pruning algorithms (so that
ql∗ must be on the left side of a red segment). Note that the paths could be “below” π0 , but for ease of exposition,
we “flip” them above π0 , and this flip operation actually does not change the topology of these paths.

This proves that πf (i) does not cross wf (j) and πf (j) does not cross wf (i) . Since wf (j) is clockwise from wf (i) and πf (j) does not cross wf (i) , wf (i) is contained in Df (j) . Further, since πf (j) is
counterclockwise from πf (i) and πf (i) does not cross wf (j) , Df (i) must be contained in Df (j) .
This proves the first part of the lemma.
For the second part of the lemma, we assume f (i) > f (j). By the same analysis as above, qf (i)
cannot be on the boundary of Df (j) . Depending on whether qf (i) is in the interior of Df (j) or outside
it, there are two cases.
1. If qf (i) is outside Df (j) , then since i < j, πf (j) is counterclockwise from πf (i) with respect to
π0 . Further, since πf (i) and πf (j) do not cross each other and πf (i) does not contain q (by
Observation 5), πf (i) must cross wf (j) . Let p be the point of wf (j) where πf (i) crosses. Let D be
the open region bounded by wf (i) , qp, and the subpath π ′ of πf (i) between p and qf (i) .
Consider any point t on wfl (i) (if any). The point t+ must be in the interior of D. Clearly, s is
not in D. Hence, π(s, t+ ) must cross the boundary of D. Since π(s, t+ ) cannot cross π ′ , it must
cross either pq or wf (i) . By Observation 4, t can be pruned. Thus, wf (i) can be pruned.
2. If qf (i) is in the interior of Df (j) , let pf (i) be a point on wf (i) infinitely close to q. Since f (i) > f (j),
by the same analysis as before, pf (i) is not in Df (j) . Since qf (i) is in the interior of Df (j) , qf (i) pf (i)
must intersect the boundary of Df (j) at a point p. Since qf (i) pf (i) does not intersect π0 or wf (j) ,
p is on πf (j) . This proves that πf (j) crosses wf (i) .
Consider the region D bounded by qp, wf (j) , and the subpath of πf (j) between p and qf (j) .
Consider any point t on qp ∩ wfl (i) . By the similar argument as above, we can show that t can
be pruned. Thus, qp can be pruned.
⊔
⊓

The lemma thus follows.

For any 1 ≤ i < j ≤ k, we say πi and πj are consistent if f (i) < f (j). By Lemma 11, if πi
and πj are not consistent, then we can do some pruning, based on which we present our pruning
algorithm in Section 4.3. Figure 8 gives an example showing the remaining parts of the segments
of W after the pruning algorithm.
18

f (15)

f (16)

f (20)

f (13)
f (8)
f (7)
f (6)

s

f (4)
f (3)

q

π0

Fig. 9. Illustrating the shortest paths corresponding to the indices in the current bundle sequence B =
{{3}, {4}, {{{6}, {7}}, {8}}, {{13}, {{15}, {16}}, {20}}}, where each underline indicates a bundle of B. For example, the last bundle is a composite bundle consisting of three children bundles with 20 as its wrap index. In the figure,
the indices of the paths are labeled. Note that the paths could be “below” π0 , but for ease of exposition, we “flip”
them above π0 , and this flip operation actually does not change the topology of these paths.

4.3

A Pruning Algorithm for Pruning the Segments of W

We process the paths πf (1) , πf (2) , . . . , πf (k) in this order. Assume that πf (i−1) has just been processed
and we are about to process πf (i) . Our algorithm maintains a sequence of bundles, denoted by
B = {B1 , B2 , . . . Bg }. Each bundle B ∈ B is defined recursively as follows. Essentially B is a list of
sorted indices of a subset of {1, 2, . . . , i − 1}, but the indices are grouped in a special and systematic
way.
There are two types of bundles: atomic and composite. If B has only one index, then it is an
atomic bundle. Otherwise, B is a composite bundle consisting of a sequence of at least two bundles
B1′ , . . . , Bg′ ′ (with g′ ≥ 2) such that the last bundle Bg′ ′ must be atomic (others can be either atomic
or composite), and we call the index contained in Bg′ ′ the wrap index of B. We consider the bundles
B1′ , . . . , Bg′ ′ as the children bundles of B.
Let fmin (B) and fmax (B) denote the smallest and largest f (j) of all indices j of B, respectively.
If B is composite, then B further has the following three bundle-properties. (1) The indices of B
are distinct and sorted increasingly by their order in B. (2) For any 1 ≤ b < g′ − 1, fmax (Bb′ ) <
′
). (3) If j is the wrap index of B, then fmin (B) = f (j) and πf (j) crosses wf (j ′ ) for every
fmin (Bb+1
′
j ∈ B \ {j} (intuitively, πf (j) “wraps” the point qf (j ′ ) , and this is why we call j a “wrap” index).
Refer to Fig. 9 for an example.
For convenience, if the context is clear, we also consider a bundle B as a set of sorted indices.
So if an index j is in B, we can write “j ∈ B”.
Remark. We use the word “bundle” because each index j of B refers to the shortest path πf (j) .
Therefore, B is a “bundle” of shortest paths.
In addition, the bundle sequence B = {B1 , B2 , . . . , Bg } maintained by our algorithm has the
following two B-properties. (1) The indices in all bundles are distinct in [1, i − 1] and are sorted
increasingly by their order in the sequence. (2) For any 1 ≤ b < g, fmax (Bb ) < fmin (Bb+1 ).
19

qf (r)
s

π0

qf (i)
D
q

p

qf (j)

Fig. 10. Illustrating the proof of Lemma 12.

Observation 8 1. For any 1 ≤ b < b′ ≤ g and any indices j ∈ Bb and j ′ ∈ Bb′ (both Bb and Bb′
are from B), the two shortest paths πf (j) and πf (j ′ ) are consistent (e.g., see Fig. 9).
2. For any composite bundle B = {B1′ , . . . , Bg′ ′ }, for any 1 ≤ b < b′ ≤ g′ − 1 and any indices j ∈ Bb′
and j ′ ∈ Bb′ ′ , the two shortest paths πf (j) and πf (j ′ ) are consistent (e.g., see Fig. 9).
Proof. We only prove the first part since the second part is similar.
Since b < b′ , it holds that j < j ′ . Clearly, f (j) ≤ fmax (Bb ) and fmin (Bb′ ) ≤ f (j ′ ). Since
b < b′ , we have fmax (Bb ) < fmin (Bb′ ). Therefore, we obtain f (j) < f (j ′ ). Thus, πf (j) and πf (j ′ ) are
consistent.
⊔
⊓
In the following, we discuss our algorithm for processing the shortest path πf (i) , during which B
will be updated. Initially when i = 1, we simply set B to contain the only atomic bundle B = {1}
and this finishes our processing for πf (1) . In general when i > 1, we do the following.
We first find the index β such that fmax (Bβ ) < f (i) < fmax (Bβ+1 ). Later in Section 4.4 we will
give a data structure to maintain the bundle sequence B such that β can be found in O(log n) time.
If β = g (so Bβ+1 does not exist in this case), then we add a new atomic bundle Bg+1 = {i} to
the rear of B and we are done with processing πf (i) . Note that the two B-properties are maintained.
Otherwise, we check whether fmin (Bβ+1 ) < f (i). We have the following lemma.
Lemma 12. If fmin (Bβ+1 ) < f (i), then the extended-window wf (i) can be pruned.
Proof. Assume that fmin (Bβ+1 ) < f (i). Since f (i) < fmax (Bβ+1 ), we have fmin (Bβ+1 ) < f (i) <
fmax (Bβ+1 ), which also implies that Bβ+1 is a composite bundle. Let r be the wrap index of Bβ+1 .
Due to f (r) = fmin (B), it follows that f (r) < f (i). Since every index of B is smaller than i, r < i.
By Lemma 11, πf (r) does not cross wf (i) .
Consider the index j ∈ B with f (j) = fmax (B). Hence, f (j) > f (i). By the third bundleproperty, πf (r) crosses wf (j) , say, at a point p (e.g., see Fig. 10). Consider the region D bounded
by wf (r) , pq, and the subpath of πf (r) between p and qf (r) . Since r < i and f (r) < f (i) < f (j),
qf (i) must be in D since otherwise πf (r) would cross wf (i) , contradicting with Lemma 11(1). Also,
by Observation 6, qf (i) is not on πf (r) . Therefore, qf (i) is in the interior of D. This implies that
the shortest path from s to any point t of wf (i) must intersect wf (r) , wf (j) , or their endpoints.
Therefore, no point of wf (i) can be q ∗ . Thus, wf (i) can be pruned.
⊔
⊓
By Lemma 12, if fmin (Bβ+1 ) < f (i), we simply ignore πf (i) and finish the processing of πf (i) .
In the following, we assume f (i) < fmin (Bβ+1 ) (note that f (i) = fmin (Bβ+1 ) is not possible
since i 6∈ B). Next, we are going to find all such indices j of B that πf (j) crosses wf (i) . To this end,
the following two lemmas are crucial.
Lemma 13. 1. For any index j in Bb for any b ∈ [1, β], πf (j) does not cross wf (i) .
20

qf (i)
p
s

qf (j)

qf (j ′ )

π0
q

Fig. 11. Illustrating the proof of Lemma 13.

2. For any index j in Bb for any b ∈ [β + 1, g], if πf (j) crosses wf (i) , then wf (j) can be pruned;
otherwise, πf (i) must cross wf (j) .
3. If j is in Bb for some b ∈ [β + 2, g] and πf (j) crosses wf (i) , then πf (j ′ ) crosses wf (i) for any
j ′ ∈ Bb′ and any b′ ∈ [β + 1, b − 1].
4. If j is in Bb for some b ∈ [β + 1, g − 1] and πf (j) does not cross wf (i) , then πf (j ′ ) does not cross
wf (i) for any j ′ ∈ Bb′ and any b′ ∈ [b + 1, g].
Proof. We prove the four parts of the lemma separately.
1. If j is in a bundle B of {B1 , B2 , . . . , Bβ }. Note that j < i. Since f (j) ≤ fmax (B) and fmax (B) ≤
fmax (Bβ ) < f (i), we obtain f (j) < f (i). Consequently, by Lemma 11(1), πf (j) does not cross
wf (i) .
2. If j is in a bundle B of {Bβ+1 , Bβ+2 , . . . , Bg }, then f (j) > f (i). Since j < i, according
to Lemma 11(2), either πf (j) crosses wf (i) or πf (i) crosses wf (j) . If πf (j) crosses wf (i) , by
Lemma 11(2), wf (j) can be pruned. Otherwise, πf (i) must cross wf (j) .
3. Let j and j ′ be the indices as in the lemma statement. Our goal is to show that πf (j ′ ) crosses
wf (i) .
Clearly, j ′ < j and f (j ′ ) < f (j). By Lemma 11(1), Df (j ′ ) is contained in Df (j) (e.g., see Fig. 11).
Since f (i) < f (j ′ ) and f (i) < f (j), if we move from q to qf (i) along wf (i) , we will enter the
interior of both Df (j) and Df (j ′ ) . If we keep moving, note that we cannot encounter any point in
either wf (j ′ ) or wf (j) . Since πf (j) crosses wf (i) , if we move as above on wf (i) , we will encounter
a point on πf (j) , which is part of the boundary of Df (j) . Since Df (j ′ ) is contained in Df (j) , the
above moving will also encounter a point p on Df (j ′ ) (e.g., see Fig. 11). Due to Observation 6,
p cannot be qf (i) . Hence, πf (j ′ ) must cross wf (i) at p.
4. This part is equivalent to the above third part.
⊔
⊓
For any bundle B in {Bβ+1 , Bβ+2 , . . . , Bg }, if B has two indices j and j ′ such that wf (i) crosses
πf (j) but does not cross πf (j ′ ) , then we say that B is a mixed bundle, which is necessarily a composite
bundle.
Lemma 14. For any mixed bundle B = {B1′ , B2′ , . . . , Bg′ ′ }, the following holds.
1. The path πf (r) must cross wf (i) , where r is the wrap index of B, i.e., Bg′ ′ = {r}.
2. If an index j is in Bb′ for some b ∈ [2, g′ − 1] and πf (j) crosses wf (i) , then πf (j ′ ) crosses wf (i)
for any j ′ ∈ Bb′ ′ and any b′ ∈ [1, b − 1].
3. If an index j is in Bb′ for some b ∈ [1, g′ − 2] and πf (j) does not cross wf (i) , then πf (j ′ ) does not
cross wf (i) for any j ′ ∈ Bb′ ′ and any b′ ∈ [b + 1, g′ − 1].
4. If a bundle B ′ of B has two indices j and j ′ such that wf (i) crosses πf (j) but does not cross
πf (j ′ ) , then we also say that B ′ is a mixed bundle. This lemma applies to B ′ recursively.
21

D

qf (i)
s

qf (i)

qf (r) qf (j)
p

π0
q

s

(a)

qf (r) qf (j)
p

π0
q
(b)

Fig. 12. Illustrating the proof of Lemma 14(1): the path πf (i) is marked with red color in (b).

Proof. 1. Suppose j is an index of B such that πf (j) crosses wf (i) . If j = r, then we are done with
the proof. In the following, we assume j 6= r. Hence, f (j) > f (r).
Assume to the contrary that πf (r) does not cross wf (i) . Since r is the wrap index, πf (r) crosses
wf (j) , say, at a point p (e.g., see Fig. 12(a)). Consider the region D bounded by πf (j) , pqf (j) , and
the subpath of πf (r) between s and p, such that D is on the right side of the directed segment
pqf (j) from p to qf (j) . Since f (i) < f (r) < f (j) and wf (i) crosses πf (j) but does not cross πf (r) ,
qf (i) must be in the region D. Since i > j and i > r, if we go from qf (i) to s along πf (i) , we will
get out of D by crossing pqf (j) , after which we get into the interior of the region Df (j) since
πf (i) cannot cross πf (r) (e.g., see Fig. 12(b)). If we keep moving towards s along πf (i) , before
reaching s we will need to get out of the interior of Df (j) through wf (j) again. However, due
to Observation 1(2), since πf (i) already crosses wf (j) somewhere on pqf (j) , it cannot intersect
wf (j) again. Thus, we obtain contradiction.
2. This part follows the similar proof as the third part of Lemma 10 and we omit the details.
3. This part is equivalent to the second part of the lemma.
4. Using the same analysis, we can prove that the same lemma applies to B ′ recursively.
⊔
⊓
In light of the preceding two lemmas, in the following we will find the indices j of B such that
πf (j) crosses wf (i) and then prune wf (j) by Lemma 13(2) (i.e., remove j from B); we say that such
an index j is prunable.
Before describing our algorithm, we first discuss an operation that will be used in the algorithm.
Consider a composite bundle B = {B1′ , B2′ , . . . , Bg′ ′ } of B. Let r be a wrap index of B, i.e., Bg′ ′ = {r}.
Suppose wf (i) crosses πf (r) . Our algorithm will remove r from B and thus from B. This is done by
a wrap-index-removal operation. Further, suppose B is the j-th bundle of B, i.e., B = Bj . After r
is removed, the operation will implicitly insert the bundles B1′ , B2′ , . . . , Bg′ ′ −1 into the position of B
in the bundle list B, i.e., after the operation, B becomes B1 , . . . , Bj−1 , B1′ , . . . , Bg′ ′ −1 , Bj+1 , . . . , Bg .
Note that this new bundle list still has the two B-properties. Indeed, fmax (Bj−1 ) < fmin (B) =
f (r) < fmin (B1′ ) and fmax (Bg′ ′ −1 ) ≤ fmax (B) < fmin (Bj+1 ). Later in Section 4.4 we will give a
data structure to maintain the bundles of B so that each wrap-index-removal operation can be
implemented in O(log n) time.
Another operation that is often used in the algorithm is the following. Given any i, j ∈ [1, k], we
want to determine whether wf (i) crosses πf (j) . We call it the shortest path segment intersection (or
SP-segment-intersection) query. Later in Section 4.6 we will present an algorithm that can answer
each such query in O(log h log n) time, after O(n log h) time and space preprocessing.
We are ready to describe our algorithm for removing all prunable indices from B. By Lemma 13(1),
each bundle Bb of B for 1 ≤ b ≤ β does not contain any prunable index. For each bundle B of
Bβ+1 , Bβ+2 , . . . , Bg in order, we call a procedure prune(B) until the procedure returns “false”.
22

If all indices of B are prunable, then prune(B) will return “true” and the entire bundle B will
be removed from B. Otherwise, the procedure will return false. Further, if B is a mixed bundle,
then all prunable indices of B will be removed (and the procedure returns false).
The procedure prune(B) works as follows (see Algorithm 1 for the pseudocode). It is a recursive
procedure, which is not surprising since the bundles are defined recursively. As a base case, if B
is an atomic bundle {j}, then we call an SP-segment-intersection query to check whether πf (j)
crosses wf (i) . If yes, we remove the bundle B and return true; otherwise, we return false. If B is a
composite bundle {B1′ , B2′ , . . . , Bg′ ′ } with r as the wrap index (i.e., Bg′ ′ = {r}), then we first call an
SP-segment-intersection to check whether πf (r) crosses wf (i) . If not, by Lemma 14(1), B does not
have any prunable index and thus we simply return false. If yes, then we call a wrap-index-removal
operation to remove Bg′ ′ . Afterwards, for each b′ = 1, 2, . . . , g′ − 1 in order, we call prune(Bb′ ′ )
recursively. If prune(Bb′ ′ ) returns false, then we return false (without calling prune(Bb′ ′ +1 )). If it
returns true, we remove Bb′ ′ (in fact all children bundles of Bb′ ′ have been removed by prune(Bb′ ′ )).
If b′ = g′ − 1, then we return true (since all children bundles of B have been removed); otherwise,
we proceed on calling prune(Bb′ ′ +1 ).

Algorithm 1: The procedure prune(B)
Input: A bundle B
Output: remove all prunable indices of B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

18

if B is an atomic bundle {j} then
if πf (j) crosses wf (i) then
remove B;
return true;
else
return false;

/* call an SP-segment-intersection query */

else
Let B = {B1′ , B2′ , . . . , Bg′ ′ } and Bg′ ′ = {r};
if πf (r) does not cross wf (i) then
return false;
else
remove Bg′ ′ ;
for b′ ← 1 to g ′ − 1 do
if prune(Bb′ ′ ) = false then
return false;
else
remove Bb′ ′ ;

/* call an SP-segment-intersection query */

/* perform a wrap-index-removal operation */

return true;

If prune(Bb ) returns true for every b with β + 1 ≤ b ≤ g, then we add a new atomic bundle {i}
at the end of B, which now becomes {B1 , B2 , . . . , Bβ , {i}}. This also finishes our preprocessing for
πf (i) . Otherwise, prune(Bb ) returns false for some b with β + 1 ≤ b ≤ g. In this case, as a final step,
we create a new composite bundle B, consisting of all bundles of B after Bβ (not including Bβ ) and
the atomic bundle {i} as the last child bundle of B. This is done by a bundle-creation operation.
We will show in Section 4.4 that this operation can be implemented in O(log n) time. Afterwards,
23

the new bundle sequence B becomes {B1 , B2 , . . . , Bβ , B}. The following lemma shows that the new
bundle B is a “valid” composite bundle and the updated B maintains the two B-properties.
Lemma 15. The new bundle B has the three bundle properties and the updated B has the two
B-properties.
Proof. Let B = {B1′ , B2′ , . . . , Bg′ ′ }, where Bg′ ′ = {i}. We show that B has the three properties of
composite bundles as follows.
1. Indeed, recall that every index of the original B is smaller than i. Note that although some
indices have been removed from B, we never change any relative order of two indices of B.
Further, i is the last index of B. Therefore, the indices of B are sorted increasingly by their
order in B. Hence, B has the first property.
2. To show the second property, again the bundles B1′ , B2′ , . . . , Bg′ ′ −1 , which are from the original B, never change their relative orders. By the recursive definition of bundles, it holds that
fmax (Bb′ ′ ) < fmin (Bb′ ′ +1 ) for any 1 ≤ b′ < g ′ − 1. Thus, the second property also holds on B.
3. For the third property, recall that f (i) < fmin (Bβ+1 ). Since each Bb′ ′ with 1 ≤ b′ ≤ g′ − 1
is a “descendent” bundle of Bb ∈ B (we consider Bb a descendent bundle of itself) for some
b ∈ [β + 1, g], it holds that fmin (Bβ+1 ) ≤ fmin (Bb ). Since f (i) < fmin (Bβ+1 ), f (i) < fmin (Bb ).
Therefore, fmin (B) = f (i). Further, for each j ∈ B \ {i}, since j is not prunable (otherwise j
would have already been pruned), πf (j) does not cross wf (i) (by Lemma 13(2)). By Lemma 13(2),
πf (i) must cross wf (j) . Hence, the third property holds on B.
To see that the updated bundle sequence B maintains the two B-properties, by using the similar
analysis as above, the first property holds. For the second property, we have proved above that
fmin (B) = f (i). Further, recall that fmax (Bβ ) < f (i). Therefore, we obtain fmax (Bβ ) < fmin (B).
Consequently, the second property also holds on B.
⊔
⊓
To analyze the running time of the above algorithm, let m be the number of indices that have
been removed from B. Then, the algorithm makes at most m + 1 SP-segment-intersection queries.
To see this, once the query discovers an index j that is not prunable, the algorithm will stop without
making any more such queries. On the other hand, each wrap-index-removal operation removes an
index, and thus the number of such operations is at most m. Further, observe that for each bundle
B, whenever we make a recursive call on a child bundle of B, the wrap index of B is guaranteed to
be removed. Therefore, the number of total recursive calls is at most m as well. Hence, the running
time of the algorithm is O((m + 1) log h log n).
This finishes our algorithm for processing the path πf (i) . The total time for processing πf (i) is
O((m + 1) log h log n). Since once an index is removed from B, it will never be inserted into B again,
the sum of all such m in the entire algorithm for processing all paths πf (i) for i = 1, 2, . . . , k is at
most k. Hence, the total time of the entire algorithm is O(k log h log n).
Again, Fig. 8 gives an example showing the remaining parts of the segments of W after the
pruning algorithm.
4.4

The Data Structure for Maintaining the Bundles

In this section, we give a data structure for maintaining the bundle sequence B such that our
algorithm runs in the time as claimed above. In particular, we show that during our algorithm for
24

γ

3

8

4
6

20
7

13

16
15

Fig. 13. Illustrating the bundle tree TB for the bundle sequence in Fig. 9.

processing πf (i) each of the following operations can be performed in O(log k) (= O(log n)) time:
inserting a new bundle {i} at the end of B, the bundle-creation operation, the wrap-index-removal
operation, and finding the index β.
We first present our data structure and then discuss the operations.
4.4.1

The Data Structure

Let B = {B1 , B2 , . . . , Bg }. It is not difficult to see that the bundles of B naturally form a tree
structure. So we use a bundle tree TB to represent it, as follows. The tree TB has a root γ, whose
children from left to right are exactly the bundles B1 , B2 , . . . , Bg in this order. For each such bundle
B, if B is atomic, then B is a leaf of TB and the index of B is stored at the leaf. Otherwise, suppose
B = {B1′ , B2′ , . . . , Bg′ ′ }. Then, we store the wrap index of B at the node B and B has g′ − 1
children from left to right corresponding to B1′ , B2′ , . . . , Bg′ ′ −1 in this order. If one of these bundles
is composite, then its subtree is defined recursively. Refer to Fig. 13 for an example.
For each node µ of TB , let TB (µ) denote the subtree rooted at µ. It is easy to see that if µ is
a leaf, then TB (µ) represents an atomic bundle; otherwise, TB (µ) represents a composite bundle.
Each node of the tree except the root stores an index. Further, the post-order traversal of each
subtree TB (µ) gives exactly the sequence of indices in the bundle represented by TB (µ).
We implement the bundle tree TB as follows. In general, consider any internal node µ. We let µ
have two pointers f ront and rear pointing to the leftmost and rightmost children of µ, respectively.
In this way, from µ, we can access its leftmost and rightmost children in O(1) time. All children
of µ are organized by a doubly linked list: Each child of µ maintains a left (resp., right) pointer
pointing to its left (resp. right) sibling, so that we can remove a node in constant time; the left
(resp., right) pointer of the leftmost (resp., rightmost) child is empty. In this way, from the leftmost
child of µ, we can visit all children of µ in order from left to right in linear time.
In order to compute the index β in O(log k) time, we use another balanced binary search tree
Tf to maintain the ranges [fmin (B), fmax (B)] of the bundles B of B. The tree Tf has g leaves
corresponding to the bundles of B from left to right. For each leave v ∈ Tf , let Bv denote the
bundle of B corresponding to v; we associate with v the range [fmin (Bv ), fmax (Bv )]. By the second
property of B, the ranges of the leaves from left to right are sorted by either the minimum values
or the maximum values of the ranges. Clearly, the height of Tf is O(log k). In addition, each leave
v is associated with a cross pointer pointing to the node of TB corresponding to the bundle Bv ,
so that once we have the access to v in Tf we can locate Bv in TB in constant time. Finally, each
internal node v of Tf maintains the minimum range value of the leftmost leave in the subtree of Tf
rooted at v, which is used for searching.
25

This completes our data structure for maintaining the bundles of B, which consists of two trees
TB and Tf . In the following, we show how to use our data structure to implement the operations
on B needed in our algorithm for processing πf (i) .
4.4.2

Performing Operations

First of all, finding the index β can be easily done in O(log k) time by searching the tree Tf .
Further, by using the cross pointer, we can immediately access the node µ of TB whose subtree
TB (µ) represents Bβ .
If β = g, then our algorithm adds B = {i} at the end of B. To implement it, we first insert B
to Tf as the rightmost leaf with the range [f (i), f (i)], which can be done in O(log k) time. Then,
we add the atomic bundle B to the rear of B by adding a leaf to TB as the rightmost child of the
root γ. The tree TB can be updated in constant time with the help of the rear pointer of γ.
If β 6= g, then we check whether fmin (Bβ+1 ) < f (i) (note that we can find the leaf for Bβ+1 in
Tf in O(log k) time). If fmin (Bβ+1 ) < f (i), then we are done for processing πf (i) . In the following,
we assume fmin (Bβ+1 ) > f (i).
Our algorithm first calls the procedure prune(Bβ+1 ). To implement it, note that Bβ+1 is represented by the subtree TB (µ′ ), where µ′ is the right sibling of µ. Since we already have the access to
µ, by using the right pointer of µ, we can access µ′ in constant time. The procedure prune(Bβ+1 )
begins with checking whether Bβ+1 is atomic, which can be done in constant time by checking
whether µ′ is a leaf.
If yes, then the procedure stops after an SP-segment-intersection query. Further, if Bβ+1 needs
to be removed, then we simply remove the leaf µ′ , which can be done in constant time (recall that
the children of any node of TB are organized by a doubly linked list). Further, we also remove the
corresponding leaf from Tf in O(log k) time.
If Bβ+1 is not atomic, let Bβ+1 = {B1′ , B2′ , . . . , Bg′ ′ }. We can obtain the wrap index of Bβ+1 in
constant time since it stored at the node µ′ . To implement wrap-index-removal operation, essentially,
we need to replace the node µ′ by its children. This can be done in constant time by using the left,
right, front, and rear pointers of µ′ . Depending on whether µ′ is the leftmost or rightmost child
of γ, we may also need to update the front or rear pointer of γ, which can also be easily done in
constant time. We omit these details.
Next, our algorithm calls the procedure prune(B1′ ). We can access the node of TB whose subtree
represents B1′ in constant time after the above wrap-index-removal operation (i.e., by following the
front pointer of µ′ ). The algorithm then works recursively. Note that B1′ now becomes a bundle of
B. Hence, the above algorithm description on Bβ+1 applies to B1′ recursively.
The algorithm stops when either we are at the end of B or the procedure prune(B ′ ) returns
false for a bundle B ′ in the current B. In the former case, we add {i} to the rear of the current list
B in the same way as before. In the latter case, we preform a bundle creation operation by creating
a composite bundle B including all bundles of the current B after Bβ as well as {i} in the rear of
B. We implement this bundle creation operation as follows.
Note that we have the access of the node µ1 whose subtree represents B ′ after prune(B ′ ) returns
false. Let µ2 be the rightmost child of γ, which can be accessed in constant time from the root γ.
Next, in constant time, we construct a subtree T representing the bundle B and use T to replace
the subtrees of γ from µ1 to µ2 (e.g., see Fig. 14), as follows. First, we create a new node µ3 storing
the single index i. Second, we set the front pointer of µ3 to µ1 and set the rear pointer of µ3 to
µ2 . Third, if µ1 has a left sibling, denoted by µ4 , then we set the left pointer of µ3 to µ4 and set
26

γ
µ4

······
B1

B2

Bβ

γ

µ1

······

µ2

B′

B1

B2

µ3

µ4

······

µ1

Bβ

T

······

µ2

B′

Fig. 14. Illustrating the bundle creation operation. Left: the bundle tree before the operation. Right: the bundle tree
after the operation (the subtree T represents the bundle B).

the right pointer of µ4 to µ3 ; otherwise, we set the front pointer of γ to µ3 . Fourth, we set the rear
pointer of γ to µ3 . Fifth, we set the left pointer of µ1 to empty.
Finally we update the tree Tf as follows. Recall that the algorithm stops when either we are at
the end of B or prune(B ′ ) returns false for a bundle B ′ in the current B. In the former case, we
let B = {i}, and in the latter case, we let B denote the new bundle created by the bundle creation
procedure. In either case, we update as Tf as follows. Note that the original B is {B1 , B2 , . . . , Bg }
and the updated B is {B1 , B2 , . . . , Bβ , B}. Essentially, the bundles {Bβ+1 , Bβ+2 , . . . , Bg } have been
replaced by B. So we first remove the leaves corresponding to the bundles {Bβ+1 , Bβ+2 , . . . , Bg }
from Tf . Since they are consecutive in Tf , the remove can be done in O(log k) time. Next, we insert
B into Tf as the rightmost leave. In the former case (i.e., B = {i}), fmin (B) = fmax (B) = f (i). In
the latter case, fmin (B) = f (i) and fmax (B) = fmax (Bg ), which can be obtained in O(log k) time
from the original Tf . Hence, in either case the total time for updating Tf is O(log k). In addition,
we set the cross pointer of the new leaf to the node µ′′ of TB whose subtree represents B, which is
done in constant time since we have the access of µ′′ after TB is updated (e.g., µ′′ is µ3 in the case
of Fig. 14).
4.5

Computing the Closest Point q ∗

Recall that we have assumed that q ∗ is on wil for some i ∈ [1, k], i.e., q ∗ = ql∗ . According to our
pruning algorithm for computing the bundle sequence B, the point q ∗ must be on wfl (j) for some
index j ∈ B. In this section, we will compute q ∗ by using the bundle sequence B. For example, in
Fig 8, our goal is to compute q ∗ on the left sides of those (red) thick segments.
Recall that we have defined in Section 3.2 that Ri is the region of P bounded by π(s, vi ),
π(s, vi+1 ), and αi , where αi is either a bisector super-curve whose endpoints are vi and vi+1 or a
chain of obstacle edges. Also recall that Ri consists of a tail and a cell.
Let τ be any segment in P such that Ri contains π(s, τ ). With the help of the decomposition D
proposed in Section 3, we propose a region-processing algorithm to compute π(s, τ ) in the following
lemma.
Lemma 16. Suppose τ is a segment of P such that Ri contains π(s, τ ) and Ri is known. Then
π(s, τ ) can be computed in O(log h log n) time, after O(n log h) time and space preprocessing.
Proof. We first present our region-processing algorithm for computing π(s, τ ), and then argue its
correctness. Finally, we will analyze the running time of the algorithm.
27

The algorithm. For each of π(s, vi ), π(s, vi+1 ), and αi , we check whether it crosses τ . Note that
this step is not necessary for αi if αi is a chain of obstacle edges since τ cannot cross any obstacle
edge. By Observation 1(2), τ intersect π(s, vi ) (resp., π(s, vi+1 )) at most once.
To avoid the tedious case analysis, by Observation 1(2), we assume that if τ intersects π(s, vi )
or π(s, vi+1 ), then the intersection is a single point (i.e., not a general sub-segment of τ ). Let a
(resp., b) be the intersection between τ and π(s, vi ) (resp., π(s, vi+1 )); if there is no intersection,
we simply let a (resp., b) refer to ∅. In general, if αi is a bisector super-curve, τ may intersect αi
multiple times, and we let c be an arbitrary such intersection; similarly, if there is no intersection
let c refer to ∅.
If a = b and a 6= ∅, then a is a point on the tail of Ri . By Observation 1(2), τ can only intersect
the tail once. By the definition of Ri , for any point t in the cell of Ri , d(s, a) ≤ d(s, t). This implies
that π(s, a) is π(s, τ ). So we can finish the algorithm in this case.
Otherwise (i.e., a 6= b or a = b = ∅), if at least one element of {a, b, c} is not ∅, then for each
point p of {a, b, c} and p 6= ∅, we do the following. Observe that p is not on the tail of Ri . By the
definition of the decomposition D, regardless of whether p is on π(s, vi ), π(s, vi+1 ), or αi , there is a
cell ∆p of D such that ∆p contains p and ∆p is in Ri . By Lemma 1(4), ∆p ∩ τ consists of at most
two maximal sub-segments τ1 and τ2 . Since ∆p is a simple polygon, we can build a ray-shooting
data structure on each of the inside and the outside of ∆p . Then, we can compute τ1 and τ2 in
O(log n) time by using ray-shooting queries. Next, we compute π(s, τ1 ) and π(s, τ2 ) in O(log n)
time by Lemma 1(5). In this way, we obtain at most six candidate paths (for the at most three
non-empty points of {a, b, c}) and return the shortest one as π(s, τ ).
The remaining case is when every element of {a, b, c} is ∅, i.e., τ does not cross any of the three
parts of ∂Ri . In this case, τ is contained in a single cell ∆ of D. We can determine ∆ by locating
the cell of D that contains an arbitrary endpoint of τ . Then, we compute π(s, τ ) by Lemma 1(5).
The correctness. Recall that Ri contains π(s, τ ). Let t a closest point of τ (i.e., π(s, τ ) = π(s, t)).
Thus, Ri contains t. If t is on the tail of Ri , then our algorithm correctly computes π(s, τ ) as
discussed above. Otherwise, if τ is in Ri , then τ must be in a single cell of D. Clearly, our algorithm
correctly computes π(s, τ ) in this case. If τ is not in Ri , then since Ri contains t, τ must cross the
boundary of Ri . Suppose we move from t along τ until we cross the boundary of Ri at a point p.
Let ∆p be the cell of D that is in Ri and contains p. Be definition, ∆p also contains t. If p is on
π(s, vi ) (resp., π(s, vi+1 )), then since τ intersects π(s, vi ) (resp., π(s, vi+1 )) at a single point, our
algorithm correctly computes π(s, τ ). If p is on αi , then all intersections between τ and αi are in
∆p since αi is contained in ∆p . Hence, our algorithm also correctly computes π(s, τ ).
The time analysis. The algorithm needs at most six calls of Lemma 1(5), which take O(log n) time.
It also has at most two SP-segment-intersection queries for computing the intersections of τ with
π(s, vi ) and π(s, vi+1 ). Again, we will show that each such query can be answered in O(log h log n)
time with O(n log h) time and space preprocessing.
In addition, if αi is a bisector super-curve, our algorithm also needs to compute an intersection
between τ and αi . This can be done in O(log n) time after linear time preprocessing on αi using
the ray-shooting data structure on curved simple polygons or splinegons [26] (indeed, each bisector
edge of αi is convex, and thus it is straightforward to make αi a splinegon [26], e.g., by the standard
technique as detailed in the proof of Lemma 20). Thus, the total preprocessing time on all such
curves αi for i = 1, 2, . . . , h∗ is O(n).
28

qf (j)
q∗

qf (i) D

s

q

π0

Fig. 15. Illustrating Observation 9.

Also, we have mentioned before that we need a constant number of ray-shooting queries on the
cells ∆p to determine the at most two sub-segments of ∆p ∩ τ . The query time is O(log n) and the
total preprocessing time on all cells of D is O(n).
Hence, our region-processing algorithm runs in O(log h log n) time, and the total preprocessing
time and space is O(n log h).
⊔
⊓
Recall that R = {R1 , R2 , . . . , Rh∗ }. Due to our general position assumption that q is not collinear
with any two obstacle vertices, none of {q, q1 , . . . , qk } is an obstacle vertex. Then, for each k′ ∈ [0, k],
there is a unique region Ri of R whose cell contains qf (k′ ) , such that the shortest path πf (k′ ) is
contained in Ri , and we let z(k′ ) refer to the index i of Ri . Computing z(0), z(1), . . . , z(k) can be
done in O(k log n) time by point location queries on the cells of the regions of R.
For any two indices k1 and k2 in [1, h∗ ], if k1 ≤ k2 , then let [k1 , k2 ]R denote the set of all integers
′
k ∈ [k1 , k2 ]; otherwise, let [k1 , k2 ]R denote the set of all integers k′ ∈ [k1 , h∗ ] ∪ [1, k2 ]. Recall that
the regions R1 , R2 , . . . , Rh∗ are counterclockwise around s. We actually use [k1 , k2 ]R to refer to the
set of indices of the regions of R from Rk1 to Rk2 counterclockwise around s.
Next we compute q ∗ on wfl (j) for j ∈ B, by using our region-processing algorithm in Lemma 16.
Consider the bundles of B = {B1 , B2 , . . . , Bg }. For each b with 1 ≤ b ≤ g, we call a procedure
path(Bb , z(i)), where i is the last index of Bb−1 if b ≥ 2 and i = 0 otherwise. Note that given the
access of Bb , we can obtain i in constant time by using our data structure in Section 4.4. Also note
that i < j for any index j ∈ Bb . The procedure path(Bb , z(i)) works as follows.
Depending on whether Bb is atomic or composite, there are two cases.
The atomic case. If Bb is atomic, let j be the only index of Bb . According to the bundle-properties,
i < j and f (i) < f (j). So πf (j) and πf (i) are consistent. By Lemma 11(1), Di is contained in Dj .
Let D be Dj minus the interior of Di . We have the following observation.
Observation 9 If q ∗ is on wfl (j) , then π(s, q ∗ ) must be in D (e.g., see Fig. 15).
Proof. Suppose q ∗ is on wfl (j) . Let t = q ∗ . By definition, the point t+ is in the interior of D. Since
t = q ∗ , π(s, t+ ) does not intersect any point of wf (i) or wf (j) and it does not contain q either. Also,
π(s, t+ ) cannot cross either πf (i) or πf (j) . Hence, π(s, t) must be in D.
⊔
⊓
Observation 9 leads to the following lemma.
Lemma 17. If q ∗ is on wfl (j) , then π(s, q ∗ ) is in Rk′ for some index k′ ∈ [z(i), z(j)]R , and further,
any shortest path π(s, wf (j) ) from s to wf (j) is π(s, q ∗ ).
Proof. Suppose q ∗ is on wfl (j) . Since q ∗ is also a closest point of wf (j) , π(s, wf (j) ) must be π(s, q ∗ ).
Note that π(s, q ∗ ) must be contained in a region of R. By Observation 9, π(s, q ∗ ) is in D. Hence,
πf (j) is counterclockwise from π(s, q ∗ ) with respect to πf (i) around s. Since πf (j) is in Rz(j) , and
29

D

qf (j)

qf (j ′ )

qf (i)

s

q

π0

Fig. 16. j is the wrap index of Bb and j ′ is another index of Bb with j ′ 6= j; πf (j ′ ) is in the region D.

πf (i) is in Rz(i) , there is a region Rk′ ∈ R that contains π(s, q ∗ ) such that Rz(j) is counterclockwise
⊔
⊓
from Rk′ with respect to Rz(i) around s, which implies that k′ ∈ [z(i), z(j)]R .
For each k′ ∈ [z(i), z(j)]R , we apply our region-processing algorithm on Rk′ and wf (j) to obtain
a path, and we keep the shortest path π among all such paths; let qfl (j) be the endpoint of π on
wf (j) . According to Lemma 17, if q ∗ is on wfl (j) , then q ∗ must be qfl (j) .
For the purpose of analyzing the total running time of our algorithm, as will be seen later, for
each k′ ∈ [z(i), z(j)]R with k′ 6= z(i) and k′ 6= z(j), the region-processing algorithm will not be
called on Rk′ again in the entire algorithm for computing ql∗ . On the other hand, we charge the
two algorithm calls on Rk′ for k′ = z(i) and k′ = z(j) to the index j of B. In this way, the total
number of calls to the region-processing procedure in the entire algorithm is O(h∗ + k) since the
total number of indices of B is at most k and the total number of regions Rk′ is h∗ .
The composite case. If Bb is composite, the algorithm is more complicated. Let j be the wrap index
of Bb . Observation 9 and Lemma 17 still hold on j. However, since now the region D also contains
a portion of wf (j ′ ) for each j ′ ∈ Bb and j ′ 6= j (e.g., see Fig. 16), D may also contain the shortest
path from s to wf (j ′ ) . In order to avoid calling the region-processing procedure on the same region
of R too many times, we use the following approach to process wf (j) .
For any two different indices of k′ and k′′ in a range [k1 , k2 ]R of indices of the regions of R, we
say that k′′ is ccw-larger than k ′ if [k′ , k′′ ]R is a subset of [k1 , k2 ]R (e.g., if k1 < k2 , then k′ < k′′ ).
Define zij to be the ccw-largest index in [z(i), z(j)] such that wf (j) crosses ∂Rzij (if no such
index exists, then let zij = z(i)). We first compute zij (to be discussed later). Then, we call the
region-processing procedure on Rk′ for all k′ ∈ [z(i), zij ] and return the shortest path π that is
found; let qfl (j) be the endpoint of π on wf (j) . By the following lemma, if q ∗ is on wfl (j) , then qfl (j)
is q ∗ .
Lemma 18. If q ∗ is on wfl (j) , then π(s, q ∗ ) is in Rk′ for some index k′ ∈ [z(i), zij ]R , and further,
any shortest path π(s, wf (j) ) from s to wf (j) is π(s, q ∗ ).
Proof. By Lemma 17, the lemma statement holds for some k′ ∈ [z(i), z(j)]R . In the following we
show that k′ is in [z(i), zij ]R .
Assume to the contrary that k′ is not in [z(i), zij ]R . Then, k′ is ccw-larger than zij and wf (j)
does not cross ∂Rk′ . This implies that wf (j) and q are in Rk′ . Since i < j, πf (j) is counterclockwise
from π(f (i)) with respect to π0 = π(s, q). This implies that z(i) ∈ [z(0), z(j)]R . But wf (j) ∈ Rk′
implies that z(0) = z(j) = k ′ . Thus, we have z(i) = z(j) = k′ . Since zij ∈ [z(i), z(j)]R , we obtain
zij = k′ . But this contradicts with that k′ is not in [z(i), zij ]R .
The lemma thus follows.
⊔
⊓
30

qf (j)
t

s
π0

qf (i)

qf (j ′ )
q∗
D1 p
q

Fig. 17. j is the wrap index of Bb and j ′ is another index of Bb with j ′ 6= j; πf (j ′ ) is in the region D.

j′

The following lemma makes sure that when we process wf (j ′ ) for any other index j ′ of Bb with
6= j, we do not need to consider the regions Rk′ for k′ ∈ [z(i), zij − 1] if zij 6= z(i).

Lemma 19. Suppose zij 6= z(i). If q ∗ is on wfl (j ′ ) for some j ′ ∈ Bb and j ′ 6= j, then π(s, q ∗ ) is in
Rk′ for some k′ ∈ [zij , z(j ′ )]R .
Proof. Consider any such j ′ as in the lemma statement. Since j is the wrap index of Bb , πf (j) crosses
wf (j ′ ) at a point p (e.g., see Fig. 17). By Lemma 11(2), the portion qp of wf (j ′ ) can be pruned, i.e.,
q ∗ cannot be on qp. Let D 1 be the region bounded by qp, wf (j) , and the subpath π(p, qf (j) ) of πf (j)
between p and qf (j) . Note that D 1 ⊆ Df (j ′ ) .
Since q ∗ ∈ wfl (j ′ ) , π(s, q ∗ ) must be in Df (j ′ ) . We claim that π(s, q ∗ ) is in D 2 = Df (j ′ ) \ D 1 (e.g.,
see Fig. 17). To see this, D 2 is one of the two sub-regions of Df (j ′ ) partitioned by wf (j) ∪ π(p, qf (j) ).
Since q ∗ is not on qp, q ∗ must be in the interior of pqf (j ′ ) , which is in D 2 . Hence, to prove that
π(s, q ∗ ) is in D 2 , it is sufficient to show that π(s, q ∗ ) does not cross either wf (j) or π(p, qf (j) ).
Indeed, π(s, q ∗ ) does not cross π(p, qf (j) ). On the other hand, π(s, q ∗ ) does not intersect wf (j) since
otherwise q ∗ would not be a closest point of Vis(q). This shows that π(s, q ∗ ) is in D 2 .
Since z(i) 6= zij , zij is ccw-larger than z(i). By the definition of zij , wf (j) crosses ∂Rzij , say,
at a point t (e.g., see Fig. 17). Hence, the region Rzij contains a shortest path π(s, t) from s to t.
Further, since zij ∈ [z(i), z(j ′ )]R , π(s, t) is also in D 2 . Since both s and t are on the boundary of
D 2 , π(s, t) partitions D 2 into two sub-regions and one of them, denoted by D 3 , contains q ∗ . Since
π(s, q ∗ ) does not cross π(s, t), π(s, q ∗ ) is in D 3 , which implies that π(s, q ∗ ) must be in some region
Rk′ with k′ ∈ [zij , z(j ′ )]R .
This proves the lemma.
⊔
⊓
In order to compute the index zij , we will use a R-region range query. Namely, given the index
range [z(i), z(j)]R as well as wf (j) , the query can be used to compute zij . In Section 4.6 we will
give a data structure that can answer each such query in O(log h log n) time (after O(n log h) time
and space preprocessing).
After wf (j) is processed as above, qfl (j) is computed. By Lemma 19, to process wf (j ′ ) for other
indices j ′ of Bb \ {j}, we only need to consider the indices of the regions of R after zij . Let
B1′ , B2′ , . . . , Bg′ ′ −1 be the bundles in Bb other than the last one. For each 1 ≤ b′ ≤ g′ − 1, if b′ = 1,
we call path(Bb′ ′ , zij ) recursively; otherwise, we call path(Bb′ ′ , z(i′ )) recursively, where i′ is the last
index of Bb′ ′ −1 .
Remark. For the procedure path(B1′ , zij ), the above algorithm still works by replacing z(i) by zij .
To argue the correctness, the region D in Observation 9 and Lemma 17 should be defined to be
the region D 3 in the proof of Lemma 19 (with respect to j ′ ); then all observations above (after
replacing z(i) by zij ) still hold for path(B1′ , zij ).
31

After wf (j) is processed for each j ∈ B, qfl (j) is computed for every j ∈ B; among these at most
k points, we return the point q ′ whose value d(s, q ′ ) is the smallest as ql∗ , which is q ∗ based on
our above analysis (and also due to our assumption that q ∗ is on wil for some i ∈ [1, k]). The total
number of calls on the region-processing procedures is O(k + h∗ ). The total number of R-region
range queries is O(k) since each such query is for a composite bundle and there are at most k
bundles in total. Hence, the total time of the algorithm is O((h + k) log h log n). Recall that k ≤ K.
4.6

The Algorithm Implementation

In this section, we discuss some implementation details left out above. Specifically, we will give our
algorithm for computing the map f (·), and give our data structures for answering the SP-segmentintersections queries and the R-region range queries.
4.6.1

Computing the Map f (·)

Recall the definitions of Q, CQ , and LQ in Section 4.2. Computing the map f (·) is to compute the
list LQ = {q, qf (1) , . . . , qf (k) }. Intuitively, we want to order the paths π1 , . . . , πk counterclockwise
around s with respect to π0 . Our goal is to prove Lemma 8.
We begin with our preprocessing algorithm. Let Σ(s) denote the decomposition of SPM (s) by
the edges of SPT (s), which can be constructed in O(n) time after SPM (s) is given. For each cell
σ of Σ(s), we pick an arbitrary point in the interior of σ as the representative point of σ. Let X
denote the set of all such representative points. Let TX be the tree that is the union of the shortest
paths from s to all points of X, and let s be the root of TX . Clearly, TX has O(n) nodes and can
be computed in O(n) time once we have Σ(s). The points of X are exactly the leaves of TX . We
find a base leave p∗ of TX in O(n) time. Then, we compute in O(n) time the list Ll (TX , p∗ ) of all
leaves and the cycle Ll (TX ). To simplify the notation, let LX = Ll (TX , p∗ ) and let CX = Ll (TX ).
This finishes our preprocessing, which takes O(n) time.
In the sequel, we discuss our algorithm for computing the list LQ in O(k log n) time. It is
sufficient to compute the circular list CQ since we can obtain LQ from CQ in O(k) time by breaking
the cycle at q.
Let q0 = q (temporarily only for the discussion in this subsection). Recall that for each point
qi ∈ Q with 0 ≤ i ≤ k, ui is the root of the cell of SPM (s) that contains qi and determines the
shortest path πi , and note that qi ui is in a cell of Σ(s), denoted by σi (which can be determined in
O(log n) time by a point location in Σ(s)). If all cells σ0 , σ1 , . . . , σk are distinct, then the order of
the points of Q following the relative order of the representative points of the cells σ0 , σ1 , . . . , σk in
CX is exactly CQ , which can be computed in O(k log n) time with help of the circular list CX .
If σ0 , σ1 , . . . , σk are not distinct, then we first compute the circular list of the cells by the above
algorithm. To simplify the notation, let σ0 , σ1 , . . . , σk be the circular list. Then, two cells are the
same only if they are adjacent in the list. Hence, we can determine in O(k) time the cycle of unique
cells σ0′ , σ1′ , . . . , σk′ ′ for k′ < k, and further, for each cell σi′ , the set Q(σi′ ) of points of Q in σi′ can
also be determined. Consider a cell σi′ and let u′i be the root. Let T (σi′ ) be the union of the segments
u′i q ′ for all q ′ ∈ Q(σi′ ), and we consider T (σi′ ) as a tree rooted at u′i . Since u′i is an obstacle vertex,
u′i is a node in TX . If u′i is not s, then let p be the parent of u′i in TX ; otherwise let p be the child
of s in TX that is an ancestor of the base leave p∗ (we compute that particular child of s in the
preprocessing). Starting from the counterclockwise first child of u′i in T (σi′ ) with respect to u′i p, and
let L(σi′ ) be the list of the children of u′i in T (σi′ ) ordered counterclockwise. It can be verified that
32

the concatenation of L(σ0′ ), L(σ1′ ), . . . , L(σk′ ′ ) is exactly the circular list CQ . Following the above
description, the circular list CQ can be computed in O(k log n) time.
This proves Lemma 8.
4.6.2

The SP-segment-intersection Queries

In this section, we present our data structure for answering the SP-segment-intersection queries.
Specifically, given any i, j ∈ [1, k], we want to determine whether wf (i) crosses πf (j) , and if yes,
compute an intersection. Here we consider a more general problem. Given a point t and a segment
τ in P, we want to compute an intersection between τ and the shortest path π(s, t) (or report none
if they do not intersect). In the case where t has multiple shortest paths (and thus π(s, t) is not
unique), the root r of a cell of SPM (s) should also be provided so that π(s, t) refers to the one that
contains rt. But to simplify the discussion, we assume t always has a unique shortest path (the
other case can be solved by our algorithm too).
We will show that with O(n log h) time and space preprocessing (with a given SPM (s)), each
such query can be answered in O(log h log n) time. When h = O(1), the result is optimal.
Recall the definitions of V , Π, TV , and the list Ll (TV , v1 ) = {v1 , v2 , · · · , vh∗ } in Section 3. In the
following, we build up our data structure incrementally: We will first show how to answer queries
when t is in V , then show how to answer queries when t a vertex of TV , and finally discuss the
general case where t can be any point in P.
We build a complete binary search tree T1 as follows. The leaves of T1 from left to right correspond to the points v1 , v2 , . . . , vh∗ of V in this order. In the following we will consider the points
of V and the leaves of T1 interchangeably. Note that each point of V is also a leaf in the tree TV .
Consider any node u of T1 . We maintain a path P (u) of edges of TV , defined as follows. Let T1 (u)
be the subtree of T1 rooted at u and let S(u) be the set of the leaves of T1 (u). If u is the root, then
P (u) is the common sub-path (i.e., the intersection) of the shortest paths π(s, p) for all p ∈ S(u)
(note that π(s, p) is also the path of TV from p to the root s). Otherwise, P (u) is the portion of
the common sub-path of π(s, p) for all p ∈ S(u) that is not stored in P (u′ ) for any ancestor u′ of u.
In this way, for each leave vi , the edges of P (u) of all nodes u in the path of T1 from vi to the root
are pairwise disjoint and comprise exactly π(s, vi ). Further, for each node u of T1 , since P (u) is a
path of edges, we build a ray-shooting data structure on P (u) by standard techniques as detailed
in the following lemma.
Lemma 20. For the path P (u) of each node u of T1 with m = |P (u)|, we can build a data structure
of O(m) size in O(m) time such that given any ray ρ in the plane, we can compute in O(log m)
time the first intersection (if any) between ρ and P (u).
Proof. This can be easily done by using the ray-shooting data structure for simple polygons [6,21].
We provide the details below.
Let R be a big rectangle in the plane that contains all edges of P (u). Let p be the topmost
point of P (u). We shoot a ray from p upwards until it hits ∂R at a point p′ . Then, we can consider
P (u), pp′ , and R bounds a simple polygon P . We build a ray-shooting data structure in P in O(m)
size and space [6,21].
Consider any ray-shooting query for P (u). Given a ray ρ, we compute the first point a of ∂P
hit by ρ in O(log m) time by using the ray-shooting data structure on P . If a is on P (u), then we
are done and return a as the answer. If a is on ∂R, then we are also done and report that there is
33

no intersection between ρ and P (u). If a is on pp′ , then we keep shooting the ray after a and using
the ray-shooting data structure again to compute the next point a′ ∈ ∂P hit by the ray. Similarly
as above, if a′ is on P (u), then we are done and return a′ . If a′ is on ∂R, then we report that there
is no intersection. Note that a′ cannot be on pp′ . Hence, we can answer the ray-shooting query on
P (u) in O(log m) time by making at most two ray-shooting queries on P .
⊔
⊓
We call the information associated with each node u of T1 the auxiliary data structure at u.
Lemma 21. The size of T1 is O(n log h) and T1 can be built in O(n log h) time.
Proof. Recall that the number of edges of TV is O(n). In the following, we first show that each edge
e of TV is stored in P (u) of at most two nodes u in each level of T1 .
Assume to the contrary that there are three such nodes u in the same level of T1 that all store
the same edge e of TV in P (u). Let the three nodes be u1 , u2 , u3 from left to right. If u1 , u2 , u3 are
consecutive, then two of them, say, u1 and u2 , must share the same parent u. Since e is in both
P (u1 ) and P (u2 ), by definition, e should be in P (u′ ) for an ancestor u′ of u (including u itself).
Thus, e should not be in either P (u1 ) or P (u2 ), incurring contradiction.
In the following we assume u1 , u2 , u3 are not consecutive. If two of them share the same parent,
then we can apply the same argument as above. Otherwise, we show below that the sibling u′ of u2
(i.e., u and u′ share the same parent) has P (u′ ) including e. Consequently, the above proof applies.
Let Ve be the set of points of V whose paths from s in TV contain the edge e. Note that Ve
consists of exactly the leaves in the subtree of TV separated by e. By the definition of Ll (Tv , v1 ),
the points of Ve are consecutive in Ll (Tv , v1 ) = {v1 , v2 , . . . , vh∗ }. According to the definition of T1 ,
the leaves of T1 corresponding to the points of Ve are consecutive in T1 . Since e is in both P (u1 )
and P (u3 ), all leaves of the subtrees of T1 (u1 ) and T2 (u3 ) are in Ve . Since u2 is between u1 and u3 ,
u′ is also between u1 and u2 . Thus, all leaves of T1 (u′ ) must also be in Ve , implying that e is in the
common sub-path of π(s, p) for all p ∈ S(u′ ). Since e is in P (u2 ), e is not in P (u′′ ) for any proper
ancestor u′′ of u2 . Because u′ and u2 share the same parent, we obtain that e is also in P (u′ ).
This proves that each edge e of TV is stored in at most two nodes in each level of T1 . Since T1
has O(log h∗ ) levels and h∗ = O(log h), each edge e is stored in O(log h) nodes. Hence, the size of
T1 is O(n log h).
In the following, we construct the tree T1 in O(n log h) time. The key is to compute P (u) for
each node u of T1 , after which constructing the ray-shooting data structure on P (u) can be done
in linear time by Lemma 20.
For each edge e of TV , we compute the range [le , re ] ⊆ [1, h∗ ] that consists of all indices i such
that e is contained in the path from vi to s in TV . This can be done in O(n) time as follows. For
each vertex v of TV , we define the range [lv , rv ] as the set of all indices i such that v is contained in
the path from vi to s in TV . We first compute the ranges for all vertices of TV . This can be easily
done a post-order traversal of TV starting from the leaf v1 . Specifically, during the traversal for
each vertex v, if v is a leaf containing vi ∈ V , we set lv = i and rv = i; otherwise, all children of v
have been visited and we set lv (resp., rv ) to be the smallest (resp., largest) lv′ of all children v ′ of
v. After the traversal, the ranges for all vertices of TV are computed. Then, for each edge e of Π,
it is not difficult to see that the range of e is the same as that of v, where v is the endpoint of e
such that the path from s to v in TV contains e.
Next we compute P (u) for all nodes u of T1 as follows. We consider the edges of TV following the
post-order traversal from v1 . For each edge e, by using the range [le , re ], we find those nodes u of T1
whose P (u) contains e. This can be done in the similar way as the standard insertion operation in
34

segment trees [4]. Specifically, for each node u of T1 , let [lu , ru ] be the range consists of all indices i
such that vi is S(u). Starting from the root of T1 , for each node u, if [lu , ru ] ⊆ [le , re ], then we insert
e to P (u); otherwise, for each child u′ of u, if [le , re ]∩[lu′ , ru′ ] 6= ∅, then we proceed on u′ recursively.
As the standard insertion operations on segment trees, each edge e is processed in O(log h) time
since the height of T1 is O(log h). Hence, the total time of the algorithm is O(n log h). Note that
since we consider the edges of TV by following the post-order traversal from v1 , whenever we insert
an edge e to P (u), e is always the edge adjacent to the first edge of the current P (u) and e is then
appended to P (u) as the new first edge. After the algorithm finishes, the sub-path P (u) is readily
available by following the edges in the order they have been inserted and the first edge is the one
closest to s.
This proves the lemma.
⊔
⊓
We show how to answer SP-segment-intersection queries by using the tree T1 . We begin with
a special case where the query point t is in V , say t = vi for some i ∈ [1, h∗ ]. Our goal is to
compute an intersection between τ and π(s, vi ). To answer the query, we follow the path of T1 from
the root to the leaf vi . For each node u in the path, we use a ray-shooting query to compute an
intersection between P (u) and τ . If we find an intersection, then we report the intersection and
stop the algorithm; otherwise, we proceed on the next node. The correctness of the algorithm is
based on the fact that the union of P (u) of all nodes u in the above path is exactly π(s, vi ). The
query time is O(log h log n) since each ray-shooting query takes O(log n) time and the height of T1
is O(log h).
We then consider a more general case where the query point t is a vertex v of TV (v is not
necessarily in V ). To answer the query, we first pick an arbitrary leave vi in the subtree of TV
rooted at v (for this, in the preprocessing step we need to associate with v ′ an arbitrary leaf in
its subtree for each node v ′ of TV ). Clearly, v must be in the path π(s, vi ). We follow the path of
T1 from the root to the leaf vi . For each node u in the path, we compute an intersection between
P (u) and τ by using a ray-shooting query. If there is an intersection p, we check whether p is in
the sub-path of π(s, vi ) between s and v (see below for more details about this). If yes, then we
report p and stop the algorithm. Otherwise, since τ can only cross π(s, vi ) once, there cannot be
any intersection between τ and π(s, v); thus, in this case we simply return none. If there is no
intersection between τ and P (u), then we proceed on the next node in the path. If we do not find
any intersection after we reach vi , then we report none.
It remains to discuss how to determine whether p is between s and v. The point p is on an edge
e of π(s, vi ), which is also in TV . Let v ′ be the endpoint of e that is farther to s in TV . Observe that
p is between s and v if and only if v ′ is between s and v. To determine the latter, observe that v ′ is
between s and v if and only if v ′ is after v in the canonical list L(TV , v1 ), which can be determined
in O(log n) time (e.g., by binary search) after L(TV , v1 ) is computed in the preprocessing.
Hence, the total time for answering the query is O(log h log n).
In the following, by making use of the above result, we consider the most general case where t
can be any point in P. We first present the result for the simple polygon case.
Lemma 22. For any simple polygon P of m vertices and a source point s in P , after O(m) time
preprocessing, we can answer each SP-segment-intersection query in O(log m) time.
Proof. Given any query segment τ and a point t in P , the query asks for the intersection between
τ and the shortest path π(s, t) from s to t in P (or report none if there is no intersection).
35

s
rc
ve r
b
e
b
τ
ue

ra
a
rt
t

Fig. 18. Illustrating an example where π(s, rt ) intersects the interior of τ .

In the preprocessing, we compute the shortest path tree SPT (s) and shortest path map SPM (s)
from s in P , which can be done in O(m) time [17]. We then build a point location data structure
on SPM (s) in O(n) time [14,25]. Further, we compute the canonical cycle C(SPT (s)) in O(m) time.
Let rt be the root of the cell of SPM (s) containing t such that π(s, t) contains rt t. We first check
whether rt t intersects τ . If yes, we return the intersection. Otherwise, we proceed to compute the
intersection between τ and the shortest path π(s, rt ) from s to rt .
Let a and b be the two endpoints of τ , respectively. We first check whether a is on π(s, rt ), as
follows. If a ∈ π(s, rt ), then a must be on an edge e of π(s, rt ) ⊆ SPT (s), and further, rt must be a
descendent of ve , where ve is the endpoint of e farther to s in π(s, rt ). Therefore, to check whether
a is on π(s, rt ), we can use the following approach. First, we determine whether a is on an edge
of SPT (s), which can be done in O(log m) time by a point location query on the decomposition of
SPM (s) by the edges of SPT (s). If a is not on an edge of SPT (s), then we know that a cannot be
in π(s, rt ). Otherwise, we proceed on determining whether rt is a descendent of ve . To this end,
observe that rt is a descendent of ve if and only if the lowest common ancestor of ve and rt in
SPT (s) is ve , which can be computed in O(1) time after O(m) time preprocessing on SPT (s) [3,18].
Hence, we can check whether a is in π(s, rt ) in O(log m) time. Similarly we can check whether b
is in π(s, rt ) in O(log m) time. If either a or b is on π(s, rt ), then we stop the algorithm and return
it as an intersection of τ and π(s, t). Below, we assume neither a nor b is in π(s, rt ). Thus, our goal
is to compute the intersection between π(s, rt ) and the interior of τ .
Let ra be the root of the cell of SPM (s) containing a. Define rb similarly. Let rc be the lowest
common ancestor or ra and rb in SPM (s) (e.g., see Fig. 18), which can be found in constant time
by a lowest common ancestor query. Let F denote the funnel that is the region of P bounded by
π(rc , a), π(rc , b), and ab. Note that both π(rc , a) and π(rc , b) are convex with the convexity towards
the interior of F . We assume that if we traverse from rc counterclockwise around ∂F we will be on
π(rc , a) before arriving at τ (otherwise we exchange the notation a and b). Observe that π(s, rt )
intersects the interior of τ if and only if there is an edge e of π(s, rt ) such that e intersects the
interior of τ and one endpoint of e is in F and the other one is outside F (e.g., see Fig. 18). Let
ve be the endpoint of e in F and ue be the endpoint of e outside F . Observe that such an edge e
exists if and only if rt is between ra and rb counterclockwise in the circular list C(SPT (s)), which
can be determined in O(log m) time by binary search on the list.
Further, if such an edge e = ue ve exists, then we further compute the intersection e ∩ τ . To
determine the edge e, we first find the vertex ve as follows. We find the lowest common ancestor of
rt and ra , denoted by v1 . If v1 is not rc , then v1 must be on π(rc , ra ) and ve is v1 . Otherwise, the
36

lowest common ancestor of rt and rb is ve . After ve is found, e is the first edge in the shortest path
π(ve , rt ) from ve to vt , which can be found in O(log m) time using a two-point shortest path query
on the vertex pair (ve , rt ) with O(m) time preprocessing [16,19].
⊔
⊓
Combining all our results above, the following lemma gives our final result.
Lemma 23. Given SPM (s), we can build a data structure of O(n log h) size in O(n log h) time
that can answer each SP-segment-intersection query in O(log h log n) time.
Proof. In the preprocessing, we build the tree T1 , which takes O(n log h) time and space. For each
cell ∆ of the decomposition D, since it is a simple polygon, we build the data structure in Lemma 22
with respect to each super-root of ∆; this takes O(n) time and space in total.
Given τ and t, our query algorithm works as follows. We first determine the cell ∆ of D that
contains t. We also determine the super-root r of ∆ such that π(s, t) = π(s, r) ∪ π(r, t). All this can
be done in O(log n) time. Note that r is a vertex in TV . Hence, we can compute an intersection
between τ and π(s, r) in O(log h log n) time using the tree T1 . If there is an intersection, we return
it and stop the algorithm. Otherwise, we compute an intersection between τ and π(r, t) in the cell
∆. To this end, we first compute the at most two sub-segments of τ ∩ ∆ by using the ray-shooting
queries inside and outside ∆. For this, in the preprocessing, for each cell ∆ of D, we compute
ray-shooting data structures on both the inside and outside of ∆ (e.g., by the similar techniques
as in Lemma 20). Computing these ray-shooing data structure on all cells of D takes O(n) time.
Then, for each sub-segment τ ′ of τ ∩ ∆, we compute the intersection (if any) between τ ′ and π(r, t)
in O(log n) time by Lemma 22. Hence, the overall query algorithm runs in O(log h log n) time.
The lemma thus follows.
⊔
⊓
4.6.3

The R-Region Range Queries

In the following, we give our data structure for answering the R-region queries. Specifically, given
a range [i, j]R of indices of the regions of R and an extended-window τ ∈ W , the query asks for the
ccw-largest index r ∈ [i, j]R such that τ crosses the region boundary ∂Rr (or report none if such
an index does not exist). We actually consider a more general query where τ can be any segment
in P (not necessarily in W ). Our goal is to show the following result.
Lemma 24. Given SPM (s), we can build a data structure in O(n log h) time and space such that
each R-region range query can be answered in O(log h log n) time.
Recall that for each region Rr ∈ R, its boundary ∂Rr consists of three portions: π(s, vr ),
π(s, vr+1 ), and αr .
Recall that Ll (Tv , v1 ) = {v1 , v2 , . . . , vh∗ }. We build a complete binary search tree T2 as follows.
Like T1 in Section 4.6.2, the leaves of T2 from left to right correspond to v1 , v2 , . . . , vh∗ . For each
node u of T2 , we construct the same auxiliary data structure P (u) as in T1 . In addition, we build
another auxiliary data structure U (u) for each internal node u of T2 as follows.
We use T2 (u) to denote the subtree of T2 rooted at u and use S(u) to denote the set of the
leaves of T2 (u). As in T1 in Section 4.6.2, each point of V corresponds to a leaf of S(u) and is
also a leaf of TV . Let pu be the point of the path P (u) in TV that is farthest from s. In the case
where P (u) is empty, let pu be pu′ for the parent u′ of u if u 6= s and pu = s otherwise. Note that
pu is a node of TV . Let U be the union of the paths of TV from pu to all leaves of S(u) in TV ,
37

excluding the sub-path from s to pu in TV . It is not difficult to see that U is actually a subtree of
TV . Recall that the points of S(u) are consecutive in the list Ll (Tv , v1 ) = {v1 , v2 , . . . , vh∗ }. Let S(u)
be va , va+1 , . . . , vb with 1 ≤ a ≤ b ≤ h∗ . If a < b (i.e., u is not a leaf), for each c ∈ [a, b − 1], recall
that αc belongs to ∂Rc and αc is either a bisector super-curve or a chain of obstacle edges, and we
add αc to U if αc is a bisector super-curve. The resulting U is U (u). Note that U (u) is connected
since every point of U (u) has a path on U (u) connecting to the point pu . We consider U (u) as a
subdivision of the plane by all edges of U (u), without considering the obstacles of P.
We claim that each cell (excluding the outer unbounded one) of U (u) is simply connected.
Indeed, if U (u) does not contain any bisector super-curve αc , then U (u) is a connected subtree of
TV and thus there is only one cell, which is the outer unbounded one. If U (u) contains a bisector
super-curve αc for some c ∈ [a, b − 1], then αc along with π(pu , vc ) (which is also the path from pu
to vc in TV and is in U (u)) and π(pu , vc+1 ) forms a closed cell C of U (u). Note that C is also a cell
in the decomposition D ′ . Also, for any closed cell C ′ of U (u) (i.e., C ′ is not the outer unbounded
one), C ′ must be formed by a bisector super-curve in U (u) as discussed above. Therefore, each
closed cell of U (u) is simply connected.
For each closed cell C of U (u), we build a ray-shooting data structure. Although C has a
bisector super-curve, which consists of hyperbolic curves instead of line segments, Melissarators
and Souvaine [26] showed that we can still build a ray-shooting data structure for C in linear time
and space such that each query can be answered in logarithmic time1 .
For the outer cell C of U (u), we can use the similar approach as Lemma 20 to preprocess it in
linear time such that each ray-shooting query on C can be answered in logarithmic time.
In addition, recall that αh∗ connects vh∗ and v1 . If αh∗ is a bisector super-curve, then we build
a ray-shooting data structure for αh∗ [26].
This finishes the description of our data structure T2 .
Lemma 25. The space of T2 is O(n log h) and T2 can be built in O(n log h) time.
Proof. First of all, the auxiliary data structures P (u) on all nodes u of T2 can be built in O(n log h)
time and space as in Lemma 21. In the following, we focus on the second auxiliary data structure
U (u). To analyze the total space, we first show that each edge e of TV can be in U (u) for at most
two nodes u in each level of T2 .
Indeed, assume to the contrary that there are three such nodes. Since the points of V whose
paths from s in TV that contain e must be consecutive in the list {v1 , v2 , . . . , vh∗ } (and thus in the
consecutive leaves of T2 ), by the similar analysis as in Lemma 21, we can find two nodes u1 and u2
sharing the same parent such that e is contained in both U (u1 ) and U (u2 ). But this implies that e
must be stored in P (u) for a proper ancestor u of u1 (or u2 ). This further implies that e cannot be
stored in either U (u1 ) or U (u2 ).
Hence, each edge e of TV can be in U (u) for at most two nodes u in the same level of T2 .
Consequently, each edge of TV is contained in U (u) for at most O(log h) nodes u of T2 , as the
height of T2 is O(log h).
Next we show that for each bisector super-curve αc , it is stored in U (u) for at most O(log h)
nodes u of T2 . Recall that the two endpoints of αc are two leaves vc and vc+1 of T2 . Notice that αc
is in U (u) if and only if [c, c + 1] ⊆ [lu , ru ], where lu (resp., ru ) is the index of the leftmost (resp.,
rightmost) leaf in the subtree T2 (u). Clearly, [c, c + 1] ⊆ [lu , ru ] if and only if u is in the path from
the root to the lowest common ancestor of vc and vc+1 , and there are O(log h) such nodes u.
1

In fact, since each bisector edge of SPM (s) is a convex curve, C is naturally a splinegon [26].

38

Since the total size of all bisector super-curves is O(n), the space of U (u) in T2 used to store
the bisector super-curves is O(n log h).
Combining the above discussions, the size of T2 is O(n log h).
For each node u of T2 , constructing U (u) can be done in linear time in the size of U (u) as
follows. Let va , va+1 , . . . , vb be the leaves in T2 (u). We consider the paths from pu to these leaves
in TV one by one in a bottom-up manner. Initially we let U (u) contain the only path π(pu , va ). In
general, suppose π(pu , vc−1 ) has been considered (initially, c − 1 = a). Then we process π(pu , vc ) as
follows. We traverse on π(pu , vc ) from vc to pu in TV until we meet an obstacle vertex that is on
the current U (u), and then add all traversed edges of π(pu , vc ) to U (u). We continue the algorithm
as above until π(pu , vb ) is processed. Finally, for each c ∈ [a, b − 1] (if a < b), if αc is a bisector
super-curve, then we add αc to U (u). The above algorithm constructs U (u) in linear time.
Then, we construct the ray-shooting data structures for the cells of U (u), which can also be
done in linear time in the size of U (u).
Since the total size of U (u) of all nodes u of T2 is O(n log h), the total time for constructing
the second auxiliary data structures is O(n log h). Therefore, T2 can be computed in O(n log h)
time.
⊔
⊓
By using the tree T2 , the following lemma gives our query algorithm, which proves Lemma 24.
Lemma 26. Each R-region range query can be answered in O(log h log n) time.
Proof. Given a range [i, j]R of indices of the regions of R and a segment τ ∈ P, we want to compute
the ccw-largest index r ∈ [i, j]R such that τ crosses the boundary ∂Rr (if no such index r exists,
then we return none). Let r ∗ be the sought index.
Recall that both i ≤ j and i > j are possible. We first consider the case where i ≤ j. In this
case, [i, j]R consists of {i, i + 1, . . . , j}. We begin with finding the lowest common ancestor of the
two leaves vi and vj in T2 , denoted by w. Our algorithm consists of four procedures.
The first procedure. The first procedure considers the nodes in the path of T2 from the root to w.
For each node u in the path, we check whether τ crosses P (u) by a ray-shooting query. If yes, then
τ crosses the shortest path π(s, vj ) and thus crosses ∂Rj . Hence, we can simply return r ∗ = j and
stop the algorithm. Otherwise, we proceed on the next node until w is considered.
After w is considered, if r ∗ is not found, then we go to the second procedure.
The second procedure. The second procedure considers the nodes in the path of T2 from uj up to
w in a bottom-up fashion. For each node u, there are three cases.
1. If u = w, we stop the second procedure and go to the third procedure.
2. If u = uj , then we check whether whether τ intersects P (u) by calling a ray-shooting query. If
there is an intersection, we return r ∗ = j. Otherwise, we proceed on the parent of u.
3. Suppose u is neither uj nor w.
If uj is in the left sub-tree of u, then we check whether τ intersects P (u) by a ray-shooting
query. If there is an intersection, then we return r ∗ = j. Otherwise, we proceed on the parent
of u.
If uj is in the right sub-tree of u, then we first check whether τ intersects P (u). If yes, then we
return r ∗ = j. Otherwise, let u′ be the left child of u (if u does not have a left child, then we
proceed on the parent of u). We proceed as follows.
39

We check whether τ intersects P (u′ ). If yes, we return r ∗ as the rightmost index of the leaves
in the subtree T2 (u′ ). Otherwise, we check whether τ intersects U (u′ ) by first locating the cell
C of U (u′ ) containing an endpoint of τ and then calling a ray-shooting query on C. If not, we
proceed on the parent of u (not u′ ). Otherwise, we set u = u′ and go to the fourth procedure.
The third procedure. In this procedure, we consider the vertices on the path of T2 from the left
child of w down to ui , which is symmetric to the second procedure. For each node u, there are two
cases.
1. If u 6= ui , we first check whether τ intersects P (u) by a ray-shooting query. If yes, we return
the index of the rightmost leaf of T2 (u) as r ∗ . Otherwise, if ui is at the right subtree of u, then
we proceed on the right child of u.
If ui is at the left subtree of u, let u′ be the right child of u (if u does not have a right child,
then we proceed on the left child of u). We first check whether τ intersects P (u′ ). If yes, we
return the index of the rightmost leaf of T2 (u′ ) as r ∗ . Otherwise, we check whether τ intersects
U (u′ ). If not, we proceed on the left child of u. Otherwise, we set u = u′ and go to the fourth
procedure.
2. If u = ui , then we check whether τ intersects P (u). If yes, we return r ∗ = i. Otherwise, we
return none, i.e., τ does not intersect ∂Rr for any r ∈ [i, j]R .
The fourth procedure. In the fourth procedure, we have a vertex u of T2 such that τ does not
intersect P (u) but intersects U (u). Starting from u, the procedure works as follows. If u is a leaf,
then we simply return the index of the leaf as r ∗ . Otherwise, let u′ be the right child of u. If τ
intersects P (u′ ), then we return r ∗ as the index of the rightmost leaf of T2 (u′ ). Otherwise, we check
whether τ intersects U (u′ ). If yes, we set u to u′ and proceed as above. Otherwise, we set u to the
left child of u and proceed as above.
For the running time of the algorithm, observe that the algorithm only visits O(log h) vertices
of T2 and makes O(log h) ray-shooting queries as the height of T2 is O(log h). Each ray-shooting
query is either on P (u) or U (u) for some node u of T2 , which runs in O(log n) time. Hence, the
total time of the algorithm is O(log h log n).
The above gives the query algorithm for the case i ≤ j. If i > j, then the index range [i, j]R
consists of {i, i + 1, . . . , h∗ , 1, 2, . . . , j}. For this case, we first apply the above query algorithm on
the range [1, j]R . If the query does not return none, then we return r ∗ as the answer to the original
query on [i, j]R . Otherwise, if αh∗ is a bisector super-curve, then we check whether τ intersects αh∗
by a ray-shooting query; if there is an intersection, then we return r ∗ = h∗ . Otherwise, we apply
the above query algorithm on the range [i, h∗ ], and the result of the query is the answer to the
original query on [i, j]R . The total time of the query algorithm is still O(log h log n).
The lemma thus follows.
⊔
⊓
4.7

Wrapping Things Up

We summarize our overall result in the following theorem.
Theorem 2. Given SPM (s), we can build a data structure of O(n log h + h2 ) size in O(n log h +
h2 log h) time, such that each quickest visibility query can be answered in O((K + h) log h log n)
time, where K is the size of the visibility polygon of the query point q.
40

Proof. In the preprocessing, we compute the visibility polygon query data structure in [9] for
computing Vis(q), which is of O(n + h2 ) size and can be built in O(n + h2 log h) time. The rest of
the preprocessing work includes building the decomposition D and the segment query data structure
as in Section 3, performing the preprocessing in Lemmas 8, 10, 16, 23, and 24; these work takes
O(n log h) time and space in total.
Given any query point q, we first compute Vis(q) in O(K log n) time by the query algorithm in
[9]. Then, we obtain the extended window set W . Let k = |W |, which is O(K). Next, we compute a
closest point q ∗ on a segment of W in O(k log h log n) time. To this end, we compute a set S of O(k)
candidate points as follows. We first add q, q1 , . . . , qk to S. Then, we compute the closest point q0∗
of u0 q0 and add q0∗ to S. Next we compute the point ql∗ in O((k + h) log h log n) time by using our
pruning algorithm in Sections 4.3 and 4.5. By a symmetric algorithm, we can also compute qr∗ . We
add both ql∗ and qr∗ to S. By our analysis, q ∗ must be one of the points of S. Since |S| = O(k), we
can find q ∗ in S in additional O(k log n) time by using the shortest path map SPM (s).
⊔
⊓
In fact, we have the following more general result, which might have independent interest.
Corollary 1. Given SPM (s), we can build a data structure of O(n log h) size in O(n log h) time,
such that given k = O(n) segments in P intersecting at the same point, we can compute a shortest
path from s to all these segments in O((k + h) log h log n) time.
Proof. The preprocessing step is the same as in Theorem 2 except that the visibility polygon query
data structure [9] is not necessary any more. Hence, the total preprocessing time and space is
O(n log h).
Given a set S of k segments intersecting at the same point, denoted by p, we break each segment
at p to obtain two segments and we still use S to denote the new set of at most 2k segments. Next
we compute a closest point p∗ on the segments of S. To do so, we can apply the same algorithm as
in Theorem 2 for computing q ∗ on the extended-windows of W . Indeed, the only key property of
the segments of W we need is that all segments of W have a common endpoint at q. Now that all
segments of S have a common endpoint p, the same algorithm still works (some degenerate cases
may happen, but can be handled easily).
⊔
⊓

5

The Quickest Visibility Queries: The Improved Result

In this section, we reduce the query time of Theorem 2 to O(h log h log n), independent of K. The
key idea is the following. First, we show that for any query point q, there exists a subset S(q) of
O(h) windows such that a closest point q ∗ is on a segment of S(q). Second, we give an algorithm that
can compute S(q) in O(h log n) time, without computing Vis(q). Our idea relies on the extended
corridor structure [8,9,11] and modifying the query algorithm for computing Vis(q) in [9].
Below we first review the extended corridor structure in Section 5.1. We then introduce the set
S(q) in Section 5.2. Finally we present our algorithm for computing S(q) in Section 5.3.
5.1

The Extended Corridor Structure

The corridor structure has been used for solving shortest path problems, e.g., [7,23]. Later some
new concepts such as “bays,” “canals,” and the “ocean” were introduced, e.g., [8,11], referred to as
the “extended corridor structure”. We review it here for the completeness of this paper and also
for introducing the notation that will be needed later.
41

e

b

e

b

d
c
bay(cd)

x
f
z

d
y
a

Fig. 19. Illustrating a triangulation of the free space
among two obstacles and the corridors (with red solid
curves). There are two junction triangles indicated by the
large dots inside them, connected by three solid (red)
curves. Removing the two junction triangles results in
three corridors.

f

canal(x, y)

a

Fig. 20. Illustrating an open hourglass (left) and a closed
hourglass (right) with a corridor path connecting the
apices x and y of the two funnels. The dashed segments
are diagonals. The paths π(a, b) and π(e, f ) are marked
by thick solid curves. A bay with gate cd (left) and a canal
with gates xd and yz (right) are also shown.

Let Tri(P) denote an arbitrary triangulation of P. Each edge of Tri(P) that is not an obstacle
edge of P is called a (triangulation) diagonal. Let G(P) be the (planar) dual graph of Tri(P) (i.e.,
each triangle defines a node and two triangles that share a diagonal define an edge). The degree of
each node in G(P) is at most three. Using G(P), we compute a planar 3-regular graph, denoted by
G3 (the degree of each node in G3 is three), possibly with loops and multi-edges, as follows. First,
remove every degree-one node from G(P) together with its incident edge; repeat this process until
no degree-one node remains. Second, remove every degree-two node from G(P) and replace its two
incident edges by a single edge; repeat this process until no degree-two node remains. The resulting
graph is G3 (see Fig. 19), which has O(h) faces, nodes, and edges [23]. Each node of G3 corresponds
to a triangle of Tri(P), which is called a junction triangle. Removing all junction triangles results
in O(h) corridors (defined below), each of which corresponds to an edge of G3 .
The boundary of a corridor C consists of four parts (see Fig. 20): (1) A boundary portion of
P from a point a to a point b; (2) a diagonal of a junction triangle from b to e; (3) a boundary
portion of P from e to a point f ; (4) a diagonal of a junction triangle from f to a. The above (1)
and (3) are called the two sides of C. The corridor C is a simple polygon.
Let π(a, b) (resp., π(e, f )) be the shortest path from a to b (resp., e to f ) in C. The region HC
bounded by π(a, b), π(e, f ), and the two diagonals be and f a is called an hourglass, which is open if
π(a, b) ∩ π(e, f ) = ∅ and closed otherwise (see Fig. 20). If HC is open, then both π(a, b) and π(e, f )
are convex chains and are called the sides of HC ; otherwise, HC consists of two “funnels” and a
path πC = π(a, b) ∩ π(e, f ) joining the two apices of the two funnels, called the corridor path of C.
Each side of every funnel is also a convex chain.
The triangulation Tri(P) can be computed in either O(n log n) time or O(n + h log1+ǫ h) time
for any constant ǫ > 0 [2]. After Tri(P) is produced, computing all corridors and hourglasses takes
O(n) time.
Let M be the union of all O(h) junction triangles, open hourglasses, and funnels. We call M
the ocean, which is a subset of P. Since the sides of open hourglasses and funnels are all convex,
the boundary ∂M of M consists of O(h) convex chains with a total of O(n) vertices.
The space of P not in M, i.e., P \ M, consists of two types of regions: bays and canals, defined
as follows. Consider the hourglass HC of a corridor C.
We first discuss the case where HC is open (see Fig. 20). The boundary of HC has two sides.
Let c and d be any two consecutive vertices on one side of HC such that cd is not an obstacle edge
42

g
q

A
u

q(u)

Fig. 21. Illustrating an outer-bay window wu = uq(u), where q is in a bay A (g is the gate).

(see the left figure in Fig. 20). Both c and d must be on the same side of the corridor C. The region
enclosed by cd and the side of C between c and d is called a bay. We call cd the gate of the bay,
which is a common edge of the bay and M.
If the hourglass HC is closed, let x and y be the two apices of its two funnels. Consider two
consecutive vertices c and d on a side of a funnel such that cd is not an obstacle edge. If c and d
are on the same side of the corridor C, then cd also defines a bay. Otherwise, one of c and d must
be a funnel apex, say, c = x, and we call xd a canal gate (see Fig. 20). Similarly, there is also a
canal gate at the other funnel apex y, say yz. The region of C bounded by the two canal gates xd
and yz that contains the corridor path is the canal of HC .
Each bay or canal is a simple polygon. While the total number of all bays is O(n), the total
number of all canals is O(h) since the number of corridors is O(h). The two obstacle vertices of
each bay/canal gate are called gate vertices.
5.2

Defining the Window Set S(q)

We consider the source point s as an obstacle and build the extended corridor structure. This means
that s is on the boundary of the ocean M and thus is not in any bay or canal.
Consider any query point q. For any bay, if q is not in the bay, since the bay has only one gate,
q cannot see any point outside the bay “through” its gate. Although a canal has two gates, the
next lemma, proved in [11], gives an important property that if q is outside a canal, then q cannot
see any point outside the canal through the canal (and its two gates).
Lemma 27. [11] (The Opaque Property) For any canal, for any line segment pq in P (i.e., p is
visible to q) such that neither p nor q is in the canal. Then pq cannot contain any point of the canal
that is not on its two gates.
Consider any window wu = uq(u) of q defined by u, i.e., q(u) is the first point on ∂P hit by the
ray from u along the direction from q to u. Clearly, the extended-window qq(u) is locally tangent
at u, i.e., the two incident obstacle edges to u must be on the same side of the supporting line of
qq(u). In the following, we partition all windows of q into different types.
Recall that ∂M is comprised of O(h) convex chains. We call wu an ocean window if u is a vertex
of a convex chain of ∂M such that qq(u) is outer tangent to that convex chain at u. Since q has at
most two extended-windows outer tangent to each convex chain, q has O(h) ocean windows.
Suppose wu is not an ocean window. If qu \ {u} does not contain any point in M, then qu is
in a bay/canal A. In this case, we say wu is an outer-bay/outer-canal window defined by A (we use
“outer” because it is possible that wu = uq(u) contains points outside A); e.g., see Fig. 21.
If qu \ {u} contains a point q ′ in M, then q ′ 6= u. Depending on whether u is on ∂M , there are
two cases.
43

If u is on ∂M, then q ′ u is in M this is because q ′ u cannot traverse through the interior of a
canal due to the opaque property of Lemma 27. If we move from q ′ to q(u) on qq(u), since wu is
not an ocean window, after we pass u, we must move into the inside of a bay/canal A, and further,
regardless of whether A is a bay or a canal, we will never get out of A due to the opaque property,
which implies that wu = uq(u) must be in A. In this case, we say that wu is an inner-bay/inner-canal
window defined by A (we use “inner” because wu is in A).
If u is not on ∂M, then u is a non-gate vertex of a bay/canal A. This implies that if we move
from q ′ to u on qq(u), we must cross a gate of A. Again, regardless of whether A is a bay or a canal,
wu = uq(u) must be in A. In this case, we also call wu an inner-bay/inner-canal window (e.g., see
Fig. 22 and Fig. 23).
As a summary, a window wu may be an ocean window, an outer-bay/canal window, or an
inner-bay/canal window.
A window of q is called a closest window if it contains a closest point q ∗ of Vis(q).
The set S(q) is defined as follows. We first add all O(h) ocean windows to S(q). We will show
several observations. First, no inner-bay window can be a closest window. Second, among all innercanal windows defined by the same canal, there are at most two that can be closest windows and we
add them to S(q). Since there are O(h) canals, S(q) has O(h) inner-canal windows. Third, among
all outer-bay windows, there are at most two that can be closest windows; we add them to S(q).
Fourth, among all outer-canal windows, there are at most four that can be closest windows; we
add them to S(q). This finishes the definition of S(q). In summary, S(q) has O(h) ocean windows,
O(h) inner-canal windows, at most two outer-bay windows, and at most four outer-canal windows.
Thus, the size of S(q) is O(h).
For a window wu = uq(u), we assume it is directed from u to q(u) and also assume qq(u) is
directed from q to q(u).
Observation 10 Suppose wu is a closest window, i.e., q ∗ ∈ wu . If the two obstacle edges incident
to u are on the left (resp., right) side of qq(u), then the shortest path from s to q ∗ must be from the
left (resp., right) side of wu .
Proof. As discussed before, π(s, q ∗ ) is either from the left or from the right side of wu . Without
loss of generality, we assume that the two obstacle edges incident to u are on the left side of qq(u).
Assume to the contrary that π(s, q ∗ ) is from the right side of wu . Let p be a point on π(s, q ∗ )
infinitely close to q ∗ but p 6= q ∗ . Since the two obstacle edges incident to u are on the left side of
qq(u), p is visible to q, i.e., p ∈ Vis(q). Since d(s, p) < d(s, q ∗ ), q ∗ cannot be a closest point of Vis(q),
a contradiction.
⊔
⊓
Lemma 28. None of the inner-bay windows is a closest window.
Proof. Suppose wu = uq(u) is an inner-bay window defined by a bay A. By definition, wu is in A.
Assume to the contrary that wu is a closest window.
Without loss of generality, assume the two obstacle edges of P incident to u is on the left side
of qq(u) (e.g., see Fig. 22). Since both u and q(u) are on the boundary of A, wu partitions A into
two sub-polygons and one of them contains the only gate g of A. Let A′ be the sub-polygon that
does not contain g. Observe that A′ must be locally on the left side of wu . By Observation 10, since
q ∗ ∈ wu , π(s, q ∗ ) must be from the left side of wu , implying that p must be in the interior of A′ ,
where p is a point on π(s, q ∗ ) infinitely close to q ∗ . Clearly, s is not in A′ . Thus, π(s, p) must cross
wu , but this is not possible since q ∗ is on wu . Thus, wu cannot be an closest window.
⊔
⊓
44

q

d
′

uA
x
q(u)

g
q(u)
A′

A
u

q

A

z
y

Fig. 22. Illustrating an inner-bay window wu = uq(u) in Fig. 23. Illustrating an inner-canal window wu = uq(u)
a bay A.
defined by a canal A with two gates xd and yz.

Lemma 29. For any canal A that defines an inner-canal window wu , if u is not an endpoint of
the corridor path of A, then wu cannot be a closest window.
Proof. Since wu is an inner-canal window defined by A, wu must be in A and both u and q(u) are
on the boundary of A. Further, qu(q) has a point q ′ ∈ M and q ′ u crosses a gate g of A. Let g = xd
such that x is the endpoint of the corridor path of A on g (e.g., see Fig. 23). Let C be the corridor
that defines the canal A.
Assume without loss of generality that the two obstacle edges of P incident to u are on the
left side of qq(u). Since u is not x, according to the results in [11] (see the proof of Lemma 3)
that u and q(u) must be on the same side of C that contains d (e.g., see Fig. 23). This implies
that wu partitions A into two sub-polygons one of which contains both gates of A, and let A′ be
the sub-polygon that does not contain the gates. Then, as in the proof of Lemma 28, A′ must be
locally on the left side of wu , and by the similar analysis we can show that wu cannot be a closest
window.
⊔
⊓
Since each canal has one corridor path, the preceding lemma implies that every canal can define
at most two inner-canal windows that are possibly closest windows.
Consider a bay A with gate g that defines an outer-bay window wu . By definition, qu is in A.
Let u1 be the vertex of A such that qu1 is in the shortest path in A from q to an endpoint of g;
similarly, define u2 with respect to the other endpoint of g.
Lemma 30. If wu is an outer-bay window defined by A and u is neither u1 nor u2 , then wu cannot
be a closest window.
Proof. By the definitions of u1 and u2 , since A is a simple polygon and u is neither u1 nor u2 , q(u)
must be in ∂A \ {g}. Hence, the window wu partitions A into two sub-polygons and one of them
contains g. Let A′ be the sub-polygon that does not contain g. Then, by using the same analysis
as in Lemma 28, wu cannot be a closest window.
⊔
⊓
Consider a canal A that defines an outer-canal window wu . This case is similar to the above
bay case except that we need to consider both gates of A. Again, qu is in A. Define u1 , u2 , u3 , and
u4 similarly as in the bay case but with respect to the four gate vertices of A, respectively.
Lemma 31. If wu is an outer-bay window defined by A and u is not in {u1 , u2 , u3 , u4 }, then wu
cannot be a closest window.
45

Proof. By the definitions of ui for 1 ≤ i ≤ 4, since A is a simple polygon and u 6∈ {u1 , u2 , u3 , u4 },
q(u) must be in ∂A and q(u) is not on a gate of A. Further, it can be verified that the window
wu partitions A into two sub-polygons and one of them contains both gates of A. Let A′ be the
sub-polygon that does not contain the gates of A. Then, by using the same analysis as in Lemma 28,
wu cannot be a closest window.
⊔
⊓
The above discussions lead to the following lemma.
Lemma 32. Given any query point q, there is a set S(q) of windows of q such that |S(q)| = O(h)
and S(q) contains a closest window.
5.3

Computing the Window Set S(q)

In this section we present our algorithm for computing S(q), by modifying the query algorithm in
[9] for computing Vis(q). Our result is summarized in the following lemma.
Lemma 33. With O(n + h2 log h) time and O(n + h2 ) space preprocessing, given any query point
q in P, we can compute the set S(q) in O(h log n) time.
We first do the same preprocessing as in [9], which takes O(n + h2 log h) time and O(n + h2 )
space. In the following, we give our query algorithm for computing S(q). Depending on whether q
is in the ocean M, a bay, or a canal, there are three cases. In each case, we will first briefly review
the algorithm in [9] for computing Vis(q) and then modify it to compute S(q).
5.3.1

The Ocean Case

Suppose q is in M. The algorithm in [9] first computes the region of M that is visible to q, denoted
by Vis(q, M), which is also the visibility polygon of q in M due to the opaque property of canals.
Then, the algorithm computes the region in all bays and canals visible to q. To this end, it traverses
on the boundary of Vis(q, M). If a gate g of a bay/canal A is encountered, then the region of A
visible to q through e is computed, where e is a maximal portion of g on the boundary of Vis(q, M).
The visible regions computed above for all such e’s are pairwise disjoint. Hence, Vis(q) is a trivial
union of Vis(q, M) and the visible regions in all bays and canals.
We modify the above algorithm to compute S(q), as follows.
The algorithm in [9] computes Vis(q, M) by using the visibility complex [29,30]. More specifically, it uses the approach of crossing faces [30] such that all rays originating from q in the plane
define a curve γ in the visibility complex and each intersection of γ and the boundary of a cell
of the visibility complex corresponds to an outer tangent in M from q to a convex chain of ∂M.
Note that such tangents correspond exactly to our ocean windows. If we traverse the curve γ in the
visibility complex, each such intersection can be computed in O(log n) time. Hence, if there are h′
convex chains of ∂M that are visible to q, then the endpoints of the maximal sub-chains ξ of these
convex chains that are visible to q can be computed in O(h′ log n) time by using the approach of
crossing faces. Note that h′ = O(h) [9]. After this, all ocean windows are computed.
Remark. Traversing each such sub-chain ξ can explicitly construct Vis(q, M). But for our problem
of computing S(q), we can avoid this step; indeed, this is part of the reason our algorithm avoids
the Ω(K) time.
46

Next, we compute other windows of S(q). Since q is in M, S(q) does not have outer-bay/outercanal windows, and we only need to compute the inner-canal windows, as follows.
The above has computed the endpoints of each such sub-chain ξ that is visible to q. If ξ does
not contain any portion of any canal gate, then we simply ignore ξ. Otherwise, we need to compute
the inner-canal windows through g for each canal gate g that has a portion in ξ. To this end, we
need to first find these canal gates. For this, in the preprocessing step, for each convex chain C of
M, we maintain a list of canal gates on C by a balanced binary search tree such that given the
two endpoints a and b of ξ, we can determine whether ξ contains any portion of any canal gate
in O(log n) time, and if yes, report all these portions in O(k + log n) time, where k is the number
of these portions. The number of such k in the entire algorithm is O(h) since the total number of
canal gates is O(h). For each such canal gate portion e, we compute the corresponding inner-canal
window (if any) as follows.
Let g be the canal gate containing e and let A be the canal. Let x be the endpoint of the corridor
path of A at g. If x is not on e, then we ignore e. Otherwise, x is visible to q and x defines an
inner-canal window wu with u = x. Our goal is to compute q(u). This can be easily done by using
a ray-shooting query in A as follows. Consider the ray originating from x with direction from q to
x. Using a ray-shooting query on A, we find the first point p on the boundary of A that is hit by
the ray. Again, due to the opaque property of canals, p must be on an obstacle edge of P, and thus
q(u) = p. For answering each ray-shooting query in A in O(log n) time, we need to preprocess each
canal for ray-shooting queries in linear time since a canal is a simple polygon, and this requires
O(n) time in total for all canals.
Since the number of all visible sub-chains is O(h), we can compute all inner-canal windows in
O(h log n) time.
In summary, we can compute the set S(q) in O(h log n) time for the ocean case.
5.3.2

The Bay Case

If q is in a bay A, then the algorithm in [9] for computing Vis(q) first computes the region of A that
is visible to q, denoted by Vis(s, A). If the gate g of A does not have any point on the boundary of
Vis(s, A), then g is not visible to q, which further implies that no point outside the bay is visible
to q and thus Vis(s) = Vis(s, A). If g has a sub-segment g′ on the boundary of Vis(s, A), then the
points of P \ A visible to q are all visible to q through g′ . Next, the region Vis(q, M) of M that
are visible to q through g′ is computed. After Vis(q, M) is computed, the rest of the algorithm is
the same as the ocean case. Namely, by traversing the boundary of Vis(q, M), other regions of P
in bays and canals visible to q can be computed.
Next we modify the above algorithm to compute S(q).
Since q is in A, we first compute the (at most two) outer-bay windows. Let a and b be the two
endpoints of g, respectively. In the preprocessing, we compute the shortest path maps of a and b in
A, respectively. We also compute a ray-shooting data structure in A. The total such preprocessing
takes O(n) time for all bays. Then, using the shortest path maps of a and b, the two vertices u1
and u2 as defined before can be computed in O(log n) time.
If u1 = u2 , then consider the ray ρ originating from u1 along the direction from q to u1 . Let p
be the first point on the boundary of A hit by ρ. Since u1 = u2 , p must be on an obstacle edge of
A (i.e., p is not on the gate g of A), and thus u1 p is an outer-bay window. In fact, in this case u1 p
is the only window in S(q), and thus we can stop our algorithm.
47

If u1 6= u2 , then for each ui with i = 1, 2, the intersection of g with the supporting line of qui
is an endpoint of g′ [17]. Hence, g′ can be determined immediately once u1 and u2 are available.
Similarly as in the above ocean case, the algorithm in [9] uses the approach of crossing faces to
compute Vis(q, M) through g′ , which is actually a “cone” visibility query since the visibility of q
in M is delimited by the cone bounded by the ray from q to u1 and the ray from q to u2 . All
rays from q in the cone define a segment γ ′ of the curve γ (discussed in the ocean case) in the
visibility complex. To use the approach of crossing faces, the algorithm in [9] first finds the cell σ
of the visibility complex that contains an endpoint of γ ′ , which is done in O(log n) time by a point
location data structure on the visibility complex. After this, the rest of the algorithm is the same
as the ocean bases. This is also the case for our problem for computing S(q). After locating the
cell σ, we can use the crossing face approach to compute the O(h) maximal sub-chains ξ of the
convex chains of ∂M that are visible to q through g′ . As in the ocean case, this will also compute
all ocean windows of S(q). After that, we use the same approach as in the ocean case to compute
all inner-canal windows. The total time is O(h log n).
Finally, we compute the two outer-bay windows defined by u1 and u2 . Namely, we need to
compute q(u1 ) and q(u2 ). For each i = 1, 2, let ρi be the ray originating from q and along the
direction from q to ui . The above algorithm for computing the sub-chains will also determine the
point pi on ∂M first hit by ρi . If pi is on an obstacle edge of P, then pi is q(ui ). Otherwise, pi is
on a bay/canal gate gi of a bay/canal A. Then, we use a ray-shooting query on A to find the first
point p′i on the boundary of A hit by ρi . Regardless of whether A is a bay or a canal, p′i is always
on an obstacle edge, and thus p′i is q(ui ). Since the ray-shooting query on A takes O(log n) time,
the two outer-bay windows can be computed in O(log n) time.
In summary, the window set S(q) can be computed in O(h log n) time for the bay case.
5.3.3

The Canal Case

If q is in a canal A, then the algorithm is similar to the bay case with the difference that we apply
the same algorithm on the two gates of the canal separately. Specifically, let g = ab be a gate of
A. We first compute the vertices u1 and u2 with respect to a and b, respectively. Then, we apply
exactly the same algorithm as in the bay case. After that, we consider the other gate of A and
apply the same algorithm. Then S(q) is computed and the total time is O(h log n) time.
This proves Lemma 33. After S(q) is computed, we can apply the query algorithm of Theorem 2
(or Corollary 1) on the windows of S(q) to compute q ∗ . Thus we can obtain the following result.
Theorem 3. Given SPM (s), we can build a data structure of O(n log h + h2 ) size in O(n log h +
h2 log h) time, such that each quickest visibility query can be answered in O(h log h log n) time.

6

Conclusions

In this paper, we present a new data structure for answering quickest visibility queries. Our result
is particularly interesting when h, the number of holes of P, is relatively small. For example, when
h = O(1), our result matches the best result for the simple polygon case (i.e., h = 1) and is optimal.
To achieve the result, we also solve many other problems that may be interesting in their own right.
We highlight some of them below. We assume that the shortest path map SPM (s) of the source
point s has been given.
48

1. We present an algorithm that can compute a shortest path from s to τ in O(h log nh ) time for
any query segment τ ∈ P, after O(n) time and space preprocessing.
2. We present an algorithm that can compute in O(log h log n) time an intersection between τ and
the shortest path π(s, t) for any segment τ and any point t in P, after O(n log h) time and space
preprocessing.
3. We present an algorithm that can answer each R-region range query in O(log h log n) time, after
O(n log h) time and space preprocessing.
4. We present an algorithm that can compute in O((k + h) log h log n) time a shortest path from s
to any set of k = O(n) segments in P that intersect at a same point, after O(n log h) time and
space preprocessing.
These results are particularly interesting when h is relatively small, and at least the first three
results are optimal when h = O(1).
In addition, the decomposition D of P, the regions of R, and some other techniques proposed
in the paper (e.g., bundles) may find other applications as well.

References
1. E.M. Arkin, A. Efrat, C. Knauer, J.S.B. Mitchell, V. Polishchuk, G. Rote, L. Schlipf, and T. Talvitie. Shortest
path to a segment and quickest visibility queries. Journal of Computational Geometry, 7:77–100, 2016.
2. R. Bar-Yehuda and B. Chazelle. Triangulating disjoint Jordan chains. International Journal of Computational
Geometry and Applications, 4(4):475–481, 1994.
3. M. Bender and M. Farach-Colton. The LCA problem revisited. In Proc. of the 4th Latin American Symposium
on Theoretical Informatics, pages 88–94, 2000.
4. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry — Algorithms and Applications. Springer-Verlag, Berlin, 3rd edition, 2008.
5. P. Bose, A. Lubiw, and J.I. Munro. Efficient visibility queries in simple polygons. Computational Geometry:
Theory and Applications, 23(3):313–335, 2002.
6. B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting
in polygons using geodesic triangulations. Algorithmica, 12(1):54–68, 1994.
7. D.Z. Chen and H. Wang. A nearly optimal algorithm for finding L1 shortest paths among polygonal obstacles
in the plane. In Proc. of the 19th European Symposium on Algorithms (ESA), pages 481–492, 2011.
8. D.Z. Chen and H. Wang. L1 shortest path queries among polygonal obstacles in the plane. In Proc. of 30th
Symposium on Theoretical Aspects of Computer Science (STACS), pages 293–304, 2013.
9. D.Z. Chen and H. Wang. Visibility and ray shooting queries in polygonal domains. Computational Geometry:
Theory and Applications, 48:31–41, 2015.
10. D.Z. Chen and H. Wang. Weak visibility queries of line segments in simple polygons. Computational Geometry:
Theory and Applications, 48:443–452, 2015.
11. D.Z. Chen and H. Wang. Computing the visibility polygon of an island in a polygonal domain. Algorithmica,
77:40–64, 2017.
12. Y.K. Cheung and O. Daescu. Approximate point-to-face shortest paths in R3 . arXiv:1004.1588, 2010.
13. Y.-J. Chiang and R. Tamassia. Optimal shortest path and minimum-link path queries between two convex
polygons in the presence of obstacles. International Journal of Computational Geometry and Applications, 7:85–
121, 1997.
14. H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on
Computing, 15(2):317–340, 1986.
15. S.D. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, and H. Yıldız.
Geometric k shortest paths. In Proc. of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1616–1625, 2015.
16. L.J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and
System Sciences, 39(2):126–152, 1989.
17. L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan. Linear-time algorithms for visibility and
shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209–233, 1987.

49

18. D. Harel and R.E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing,
13:338–355, 1984.
19. J. Hershberger. A new data structure for shortest path queries in a simple polygon. Information Processing
Letters, 38(5):231–235, 1991.
20. J. Hershberger, V. Polishchuk, B. Speckmann, and T. Talvitie. Geometric kth shortest paths: the applet. In
Video/multimedia of the 30th Annual Symposium on Computational Geometry, 2014. http://www.computationalgeometry.org/SoCG-videos/socg14video/ksp/index.html.
21. J. Hershberger and S. Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of
Algorithms, 18(3):403–431, 1995.
22. J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on
Computing, 28(6):2215–2256, 1999.
23. S. Kapoor, S.N. Maheshwari, and J.S.B. Mitchell. An efficient algorithm for Euclidean shortest paths among
polygonal obstacles in the plane. Discrete and Computational Geometry, 18(4):377–383, 1997.
24. R. Khosravi and M. Ghodsi. The fastest way to view a query point in simple polygons. In Proc. of the 24th
European Workshop on Computational Geometry, pages 187–190, 2005.
25. D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28–35, 1983.
26. E. Melissaratos and D. Souvaine. Shortest paths help solve geometric optimization problems in planar regions.
SIAM Journal on Computing, 21(4):601–638, 1992.
27. J.S.B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and
Artificial Intelligence, 3(1):83–105, 1991.
28. J.S.B. Mitchell. Shortest paths among obstacles in the plane. International Journal of Computational Geometry
and Applications, 6(3):309–332, 1996.
29. M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudotriangulations. Discrete and
Computational Geometry, 16(4):419–453, 1996.
30. M. Pocchiola and G. Vegter. The visibility complex. International Journal of Computational Geometry and
Applications, 6(3):279–308, 1996.

50

