On the Geodesic Centers of Polygonal Domains⋆
Haitao Wang

arXiv:1607.05824v1 [cs.CG] 20 Jul 2016

Department of Computer Science
Utah State University, Logan, UT 84322, USA
haitao.wang@usu.edu
Abstract. In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal
domain P with a total of n vertices. We discover many interesting observations. We give a necessary
condition for a point being a geodesic center. We show that there is at most one geodesic center among all
points of P that have topologically-equivalent shortest path maps. This implies that the total number of
geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition
of P, which is known to be O(n10 ). One key observation is a π-range property on shortest path lengths
when points are moving. With these observations, we propose an algorithm that computes all geodesic
centers in O(n11 log n) time. Previously, an algorithm of O(n12+ǫ ) time was known for this problem, for
any ǫ > 0.

1

Introduction

Let P be a polygonal domain with a total of h holes and n vertices, i.e., P is a multiply-connected
region whose boundary is a union of n line segments, forming h + 1 closed polygonal cycles. A simple
polygon is a special case of a polygonal domain with h = 0. For any two points s and t, a shortest path
or geodesic path from s to t is a path in P whose Euclidean length is minimum among all paths from
s to t in P; we let d(s, t) denote the Euclidean length of any shortest path from s to t and we also say
that d(s, t) is the shortest path distance or geodesic distance from s to t.
A point s is a geodesic center of P if s minimizes the value maxt∈P d(s, t), i.e., the maximum
geodesic distance from s to all points of P. In this paper, we study the problem of computing the
geodesic centers of P.
The problem in simple polygons has been well studied. It is known that for any point in a simple
polygon, its farthest point must be a vertex of the polygon [20]. It has been shown that the geodesic
center in a simple polygon is unique and has at least two farthest points [18]. Due to these helpful
observations, efficient algorithms for finding geodesic centers in simple polygons have been developed.
Asano and Toussaint [2] first gave an O(n4 log n) time algorithm for the problem, and later Pollack,
Sharir, and Rote [18] solved the problem in O(n log n) time. It had been an open problem whether the
problem is solvable in linear time until recently Ahn et al. [1] presented a linear-time algorithm for it.
Finding a geodesic center in a polygonal domain P is much more difficult. This is partially due to
that a farthest point of a point in P may be in the interior of P [3]. Also, it is easy to construct an
example where the geodesic center of P is not unique (e.g., see Fig. 1). Bae, Korman, and Okamoto
[4] gave the first-known algorithm that can compute a geodesic center in O(n12+ǫ ) time for any ǫ > 0.
They first showed that for any point its farthest points must be vertices of its shortest path map
in P. Then, they considered the shortest path map equivalence decomposition (or SPM-equivalence
decomposition) [7], denoted by Dspm ; for each cell of Dspm , they computed the upper envelope of O(n)
graphs in three-dimensional space, which takes O(n2+ǫ ) time [10], to search a geodesic center in the
cell. Since the size of Dspm is O(n10 ) [7], their algorithm runs in O(n12+ǫ ) time.
A concept closely related to the geodesic center is the geodesic diameter, which is the maximum
geodesic distance over all pairs of points in P, i.e., maxs,t,∈P d(s, t). In simple polygons, due to the
property that there always exists a pair of vertices of P whose geodesic distance is equal to the geodesic
⋆

An extended-abstract of this paper will appear in the Proceedings of the 24th Annual European Symposium on
Algorithms (ESA 2016).

v3
b2
u2
a2
P
Fig. 1. The boundary of P consists of an outer and an inner equilateral triangles with their geometric centers co-located. Each of
the three thick points is a geodesic
center of P.

t

b3
v1
b1

a1
s

v2
u1

a3
u3
Fig. 2. Illustrating the π-range property. Suppose there are three shortest s-t paths
through vertices ui and vi with i = 1, 2, 3, respectively. If s and t move along the
blue arrows simultaneously (possibly with different “speeds”), then all three shortest
paths strictly decreases (it is difficult to tell whether this is true from the figure,
so these two blue directions here are only for illustration purpose). The special case
happens when the six angles ai and bi for i = 1, 2, 3 satisfy ai = bi for i = 1, 2, 3.

diameter, efficient algorithms have been given for computing the geodesic diameters. Chazelle [6] gave
the first algorithm that runs in O(n2 ) time. Later, Suri [20] presented an O(n log n)-time algorithm.
Finally, the problem was solved in O(n) time by Hershberger and Suri [11]. Computing the geodesic
diameter in a polygonal domain P is much more difficult. It was shown in [3] that the geodesic diameter
can be realized by two points in the interior of P, in which case there are at least five distinct shortest
paths between the two points. As for the geodesic center problem, this makes it difficult to discretize
the search space. By an exhaustive-search method, Bae, Korman, and Okamoto [3] gave the first-known
algorithm for computing the diameter of P and the algorithm runs in O(n7.73 ) or O(n7 (log n + h))
time.
Refer to [5,8,13,15,16,17,19] for other variations of geodesic diameter and center problems (e.g.,
the L1 metric and the link distance case).
1.1

Our Contributions

We conduct a “comprehensive” study on geodesic centers of P. We discover many interesting observations, and some of them are even surprising. For example, we show that even if a geodesic center
is in the interior of P, it may have only one farthest point, which is somewhat counter-intuitive. We
give a necessary condition for a point being a geodesic center. We also show that there is at most one
geodesic center among all points of P that have topologically-equivalent shortest path maps in P. This
immediately implies that the interior of each cell or each edge of the SPM-equivalence decomposition
Dspm can contain at most one geodesic center, and thus, the total number of geodesic centers of P
is bounded by the combinatorial size of Dspm , which is known to be O(n10 ) [7]. Previously, the only
known upper bound on the total number of geodesic centers of P is O(n12+ǫ ), which is implied by the
algorithm in [4].
These observations are all more or less due to an interesting observation, which we call the π-range
property and is one key contribution of this paper. Here we demonstrate an application of the π-range
property (see the paper for the details). Let s and t be two points in the interior of P such that t is a
farthest point of s in P. Refer to Fig. 2 for an example. Suppose there are three shortest paths from
s to t as shown in Fig. 2. The π-range property says that unless a special case happens, there exists
an open range of exactly size π (e.g., delimited by the right open half-plane bounded by the vertical
line through s in Fig. 2) such that if s moves along any direction in the range for an infinitesimal
distance, we can always find a direction to move t such that the lengths of all three shortest paths
strictly decrease. Further, if the special case does not happen, we can explicitly determine the above
2

t2

t3
s

t1
Fig. 3. Illustrating a geodesic center s with three farthest points t1 , t2 , t3 such that all these four points are in the interior
of P. There are three shortest paths from s to each of t1 , t2 , t3 .

range of size π. In fact, it is the special case that makes it possible for a geodesic center having only
one farthest point.
With these observations, we propose an exhaustive-search algorithm to compute a set S of candidate
points such that all geodesic centers must be in S. For example, refer to Fig. 3 for a schematic diagram,
where a geodesic center s has three farthest points t1 , t2 , t3 and all these four points are in the interior
of P. The nine shortest paths from s to t1 , t2 , t3 provide a system of eight equations, which give eight
(independent) constraints that can determine the four points s, t1 , t2 , t3 if we consider the coordinates
of these points as eight variables. This suggests our exhaustive-search approach to compute candidate
points for such a geodesic center s (similar exhaustive-search approaches are also used before, e.g.,
[3,7]). However, if a geodesic center s has only one farthest point (e.g., Fig. 2), then we have only
three shortest paths, which give only two constraints. In order to determine s and t, which have four
variables, we need two more constraints. It turns out the π-range property (i.e., the special case)
provides exactly two more constraints (on the angles as shown in Fig. 2). In this way, we can still
compute candidate points for such s. Also, if a geodesic center has two farthest points, we will need
one more constraint, which is also provided by the π-range property (the non-special case). Note that
the previous exhaustive-search approaches [3,7] do not need the π-range property.
The number of candidate points in S is O(n11 ). To find all geodesic centers from S, a straightforward
solution is to compute the shortest path map for every point of S, which takes O(n12 log n) time in
total. Again, with the help of the π-range property, we propose a pruning algorithm to eliminate most
points from S in O(n11 log n) time such that none of the eliminated points is a geodesic center and the
number of the remaining points of S is only O(n10 ). Consequently, we can find all geodesic centers in
additional O(n11 log n) time by computing their shortest path maps.
Although we improve the previous O(n12+ǫ ) time algorithm in [4] by a factor of roughly n1+ǫ ,
the running time is still huge. We feel that our observations (in particular, the π-range property)
may be more interesting than the algorithm itself. We suspect that these observations may also find
applications in other related problems. The paper is lengthy and some discussions are quite tedious,
which is mainly due to a considerable number of cases depending on whether a geodesic center and its
farthest points are in the interior, on an edge, or at vertices of P, although the essential idea is quite
similar for all these cases.
The rest of the paper is organized as follows. In Section 2, we introduce notation and review
some concepts. In Section 3, we give our observations. In particular, we prove the π-range property
in Section 4. Our algorithm for computing the candidate points is presented in Section 5. Finally, we
find all geodesic centers from the candidate points in Section 6.
3

2

Preliminaries

Consider any point s ∈ P. Let dmax (s) denote the maximum geodesic distance from s to all points of
P, i.e., dmax (s) = maxt∈P d(s, t). A point t ∈ P is a farthest point of s if d(s, t) = dmax (s). We use
F (s) to denote the set of all farthest points of s in P. For any two points p and q in P, for convenience
of discussions, we say that p is visible to q if the line segment pq is in P and the interior of pq does
not contain any vertex of P. We use |pq| to denote the (Euclidean) length of any line segment pq.
Note that two points s and t in P may have more than one shortest path between them, and if not
specified, we use π(s, t) to denote any such shortest path.
For simplicity of discussion, we make a general position assumption that any two vertices of P
have only one shortest path and no three vertices of P are on the same line.
Denote by I the set of all interior points of P, V the set of all vertices of P, and E the set of all
relatively interior points on the edges of P (i.e., E is the boundary of P minus V).
Shortest path maps. Given a point s ∈ P, a shortest path map of s [7], denoted by SPM (s), is a
decomposition of P into regions (or cells) such that in each cell σ, the combinatorial structures of
shortest paths from s to all points t in σ are the same, and more specifically, the sequence of obstacle
vertices along π(s, t) is fixed for all t in σ. Further, the root of σ, denoted by r(σ), is the last vertex
of V ∪ {s} in the path π(s, t) for any point t ∈ σ (hence π(s, t) = π(s, r(σ)) ∪ r(σ)t; note that r(σ)
is s if s is visible to t). As in [7], we classify each edge of σ 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 bisector curve/edge that is a hyperbolic arc.
For each point t in a bisector edge of SPM (s), t is on the common boundary of two cells and there
are two shortest paths from s to t through the roots of the two cells, respectively (and neither path
contains both roots). The vertices of SPM (s) include V ∪ {s} and all intersections of edges of SPM (s).
If a vertex t of SPM (s) is an intersection of two or more bisector edges, then there are more than two
shortest paths from s to t. The map SPM (s) has O(n) vertices, edges, and cells, and can be computed
in O(n log n) time [12]. It was shown [4] that any farthest point of s in P must be a vertex of SPM (s).
For differentiation, we will refer to the vertices of V as polygon vertices and refer to the edges of E
as polygon edges.
The SPM-equivalence decomposition Dspm of P [7] is a subdivision of P into regions such that for
all points s in the interior of the same region or edge of Dspm , the shortest path maps SPM (s) are
topologically equivalent. Chiang and Mitchell [7] showed that the combinatorial complexity of Dspm
is bounded by O(n10 ) and Dspm can be computed in O(n11 ) time.
Directions and ranges. In this paper, we will have intensive discussions on moving points along certain
directions. For any direction r, we represent r by the angle α(r) ∈ [0, 2π) counterclockwise from the
positive direction of the x-axis. For convenience, whenever we are talking about an angle α, unless
otherwise specified, depending on the context we may refer to any angle α + 2π · k for k ∈ Z. For any
two angles α1 and α2 with α1 ≤ α2 < α1 + 2π, the interval [α1 , α2 ] represents a direction range that
includes all directions whose angles are in [α1 , α2 ], and α2 − α1 is called the size of the range. Note
that the range can be open (e.g., (α1 , α2 )) and the size of any direction range is no more than 2π.
Consider a half-plane h whose bounding line is through a point s in the plane. We say h delimits a
range of size π of directions for s that consists of all directions along which s will move towards inside
h. If h is an open half-plane, then the range is open as well.
A direction r for s ∈ P is called a free direction of s if we move s along r for an infinitesimal
distance then s is still in P. We use Rf (s) to denote the range of all free directions of s. Clearly, if
s ∈ I, Rf (s) contains all directions; if s ∈ E, Rf (s) is a (closed) range of size π; if s ∈ V , Rf (s) is
delimited by the two incident polygon edges of s.
4

3

Observations

Consider any point s ∈ P and let t be any farthest point of s. Recall that t is a vertex of SPM (s) [4].
Suppose we move s infinitesimally along a free direction r to a new point s′ . Since |ss′ | is infinitesimal,
we can assume that s and s′ are in the same cell σ of Dspm . Further, if s is in the interior of σ, then
s′ is also in the interior of σ.
Regardless of whether s is in the interior of σ or not, there is a vertex t′ ∈ SPM (s′ ) corresponding
to the vertex t of SPM (s) in the following sense [7]: If the line segment s′ t′ is a shortest path from
s′ to t′ , then st is a shortest path from s to t; otherwise, if s′ , u1 , u2 , . . . , uk , t′ is the sequence of the
vertices of V ∪ {s′ , t′ } in a shortest path from s′ to t′ , then s, u1 , u2 , . . . , uk , t is also the sequence of
the vertices of V ∪ {s, t} in a shortest path from s to t.
In the case that s is on the boundary of σ while s′ is in the interior of σ, there might be more than
one such vertex t′ ∈ Dspm corresponding to t (refer to [7] for the details) and we use Mt (s′ ) to denote
the set of all such vertices t′ . We should point out that although a vertex in SPM (s) may correspond
to more than one vertex in SPM (s′ ), any vertex in SPM (s′ ) can correspond to one and only one vertex
in SPM (s) (because s′ is always in the interior of σ).
We introduce the following definition which is crucial to the paper.
Definition 1. A free direction r is called an admissible direction of s with respect to t if as we move
s infinitesimally along r to a new point s′ , d(s′ , t′ ) < d(s, t) holds for each t′ ∈ Mt (s′ ).
For T
any t ∈ F (s), let R(s, t) denote the set of all admissible directions of s with respect to t; let
R(s) = t∈F (s) R(s, t). The following Lemma 1, which gives a necessary condition for a point being a
geodesic center of P, explains why we consider admissible directions.
Before proving Lemma 1, we introduce some notation and Observation 1.
Consider any two points s and t in P. Suppose the vertices of V ∪ {s, t} along a shortest s-t path
π(s, t) are s = u0 , u1 , . . . , uk = t. According to our definition on the “visibility”, s is visible to t if and
only if k = 1. If s is not visible to t, then k 6= 1 and we call u1 an s-pivot and uk−1 a t-pivot of π(s, t).
It is possible that there are multiple shortest paths between s and t, and thus there might be multiple
s-pivots and t-pivots for (s, t). We use Us (t) and Ut (s) to denote the sets of all s-pivots and t-pivots
for (s, t), respectively. Note that according to our above definition, for any u ∈ Us (t), the line segment
su does not contain any polygon vertex in its interior.
We have the following observation. Similar results have been given in [3].
Observation 1 Suppose t is a farthest point of a point s.
1. If t is in I, then |Ut (s)| ≥ 3 and t must be in the interior of the convex hull of the vertices of Ut (s).
2. If t is in E, say, t ∈ e for a polygon edge e of E, then |Ut (s)| ≥ 2 and Ut (s) has at least one vertex
in the open half-plane bounded by the supporting line of e and containing the interior of P in the
small neighborhood of e. Further, Ut (s) has at least one vertex in each of the two open half-planes
bounded by the line through t and perpendicular to e.
Proof: The proof is similar to those in [3]. The main idea is that if the conditions are not satisfied,
then we can always find a point t′ further to s than t, incurring contradiction.

Lemma 1. If s is a geodesic center of P, then R(s) = ∅.
Proof: Assume to the contrary that R(s) 6= ∅. Let r be any direction in R(s). Then, r is in R(s, t) for
each t ∈ F (s). In other words, r is an admissible direction of s with respect to each t ∈ F (s). Suppose
we move s infinitesimally along r to a new point s′ . In the following, we show that dmax (s′ ) < dmax (s),
which contradicts with that s is a geodesic center.
5

t∗

t′

e

s

γs

γt
rs

rt

t

u
u

l t′

v

Fig. 4. Illustrating the proof of Lemma 1 for the case t′ ∈ E: Fig. 5. Illustrating the definitions of the angles γs and γt .
|ut′ | < |ut∗ |.

Consider any t′ ∈ F (s′ ), i.e., t′ is a farthest point of s′ . To prove dmax (s′ ) < dmax (s), it is sufficient
to show that d(s′ , t′ ) < dmax (s).
If t′ is in Mt (s′ ) for any t ∈ F (s), then since r is an admissible direction of s with respect to t, it
holds that d(s′ , t′ ) < d(s, t) = dmax (s). In the following, we assume t′ is not in Mt (s′ ) for any t ∈ F (s).
Let V (s) be the set of all vertices of SPM (s) that are not in F (s). Let δ = dmax (s)−maxt∈V (s) d(s, t).
Note that since |V (s)| is finite, the value δ is well-defined. Also note that the value δ is fixed and does
not depend on s′ . Since s moves infinitesimally to s′ , we can assume |ss′ | < δ.
Since t′ is a farthest point of s′ , t′ must be a vertex of SPM (s′ ). Let t∗ be the vertex of SPM (s)
corresponding to t′ . Note that although a vertex of SPM (s) may correspond to multiple vertices of
SPM (s′ ), a vertex of SPM (s′ ) corresponds to one and only one vertex of SPM (s). Hence, the vertex
t∗ is unique, and further, Ut′ (s′ ) ⊆ Ut∗ (s). Since t′ is not in Mt (s′ ) for any t ∈ F (s), we know that t∗
is not in F (s) but in V (s). Therefore, d(s, t∗ ) ≤ maxt∈V (s) d(s, t) = dmax (s) − δ.
Since ss′ ∈ P, it holds that d(s′ , t′ ) ≤ |s′ s| + d(s, t′ ). Therefore, if we can prove d(s, t′ ) ≤ d(s, t∗ ),
since |ss′ | < δ and d(s, t∗ ) ≤ dmax (s) − δ, we can obtain d(s′ , t′ ) ≤ |s′ s| + d(s, t′ ) < δ + dmax (s) − δ =
dmax (s). In the sequel, we prove d(s, t′ ) ≤ d(s, t∗ ).
If t′ ∈ V, then t∗ must be t′ [7]. Hence, d(s, t′ ) = d(s, t∗ ) and thus d(s, t′ ) ≤ d(s, t∗ ) trivially follows.
In the following, we assume t′ 6∈ V. Thus, t′ is either in E or I.
Recall that Ut′ (s′ ) ⊆ Ut∗ (s). To prove d(s, t′ ) ≤ d(s, t∗ ), it is sufficient to find a vertex u ∈ Ut′ (s′ )
such that |ut′ | ≤ |ut∗ | because d(s, t′ ) = d(s, u) + |ut′ | and d(s, t∗ ) = d(s, u) + |ut∗ |. To this end, we
will make use of Observation 1.
1. If t′ ∈ E, let e be the polygon edge of E that contains t′ . Since t′ is a farthest point of s′ , by
Observation 1, there must be a vertex of Ut′ (s′ ) on either open half-plane bounded by lt′ , where
lt′ is the line through t′ and perpendicular to e. Since t′ ∈ E, t∗ is either on e or an endpoint of e
[7]. In either case, one open half-plane bounded by lt′ contains t∗ and the other does not (e.g., see
Fig. 4). Let u be the vertex of Ut′ (s′ ) in the open half-plane bounded by lt′ that does not contain
t∗ . Clearly, |ut′ | ≤ |ut∗ | holds.
2. If t′ ∈ I, then since t′ is a farthest point of s′ , by Observation 1, t′ must be in the interior of the
convex hull of all vertices of Ut′ (s′ ). Then, regardless of whatever position of t∗ is, there must be
a vertex u ∈ Ut′ (s′ ) on the convex hull such that |ut′ | ≤ |ut∗ | holds.
The lemma is thus proved.

As explained in Section 1, we will compute candidate points for geodesic centers. As a necessary
condition, Lemma 1 will be helpful for computing those candidate points.
Consider any point s ∈ P. Let t be a farthest point of s. We need to find a way to determine the
admissible range R(s, t). To this end, we will give a sufficient condition for a direction being in R(s, t).
We first assume that s is not visible to t, and as will be seen later, the other case is trivial.
Let u and v respectively be the s-pivot and the t-pivot of (s, t) in a shortest s-t path π(s, t).
Clearly, d(s, t) = |su| + d(u, v) + |vt|. We define du,v (s, t) = |su| + d(u, v) + |vt| as a function of s ∈ R2
and t ∈ R2 . Suppose we move s along a free direction rs with the unit speed and move t along a
free direction rt with a speed τ ≥ 0. Let γs denote the smaller angle between the following two rays
originated from s (e.g., see Fig. 5): one with direction rs and one with direction from u to s. Similarly,
6

let γt denote the smaller angle between the following two rays originated from t: one with direction rt
and one with direction from v to t. In fact, as discussed in [3], if we consider d(s, t) as a four-variate
function, the triple (rs , rt , τ ) corresponds to a vector ρ in R4 , and the directional derivative of du,v (s, t)
at (s, t) ∈ R4 along ρ, denoted by d′u,v (s, t), and the second directional derivative of du,v (s, t) at (s, t)
along ρ, denoted by d′′u,v (s, t), are
d′u,v (s, t) = cos γs + τ cos γt ,

d′′u,v (s, t) =

sin2 γt
sin2 γs
+τ ·
.
|su|
|tv|

(1)

Since τ ≥ 0, d′′u,v (s, t) ≥ 0 always holds. Further, if τ 6= 0, then d′′u,v (s, t) = 0 if and only if sin2 γs =
sin2 γt = 0, i.e., each of γs and γt is either 0 or π. In the following, in order to make the discussions
more intuitive, we choose to use the parameters rs , rt , and τ instead of the vectors of R4 .
For each vertex u ∈ Us (t), there must be a vertex v ∈ Ut (s) such that the concatenation of su,
π(u, v), and vt is a shortest path from s to t, and we call such a vertex v a coupled t-pivot of u (if u
has more than one such vertex, then all of them are coupled t-pivots of u). Similarly, for each vertex
v ∈ Ut (s), we also define its coupled s-pivots in Us (t).
The following lemma provides a sufficient condition for a direction being an admissible direction
for s with respect to t.
Lemma 2. Suppose t is a farthest point of s and s is not visible to t.
1. For t ∈ I, a free direction rs is in R(s, t) if there is a free direction rt for t with a speed τ ≥ 0 such
that when we move s along rs with the unit speed and move t along rt with speed τ , each vertex
v ∈ Ut (s) has a coupled s-pivot u with either d′u,v (s, t) < 0, or d′u,v (s, t) = 0 and d′′u,v (s, t) = 0.
2. For t ∈ E, a free direction rs is in R(s, t) if there is a free direction rt for t that is parallel to the
polygon edge of E containing t with a speed τ ≥ 0 such that when we move s along rs with the unit
speed and move t along rt with speed τ , each vertex v ∈ Ut (s) has a coupled s-pivot u with either
d′u,v (s, t) < 0, or d′u,v (s, t) = 0 and d′′u,v (s, t) = 0.
3. For t ∈ V, a free direction rs is in R(s, t) if we move s along rs with the unit speed, each vertex
v ∈ Ut (s) has a coupled s-pivot u with either d′u,v (s, t) < 0, or d′u,v (s, t) = 0 and d′′u,v (s, t) = 0.
Proof: Suppose we move s infinitesimally along rs to s′ . The point t, as a vertex of SPM (s), corresponds
to a set Mt (s′ ) of vertices in SPM (s′ ). To prove that rs is an admissible direction for s with respect
to t, we need to show that d(s′ , t′ ) < d(s, t) for any t′ ∈ Mt (s′ ). In the following, we discuss the three
cases depending on whether s is in I, E, or V.
We remark that the proof would be much simpler if we only considered the “non-degenerate” case
whether s is in the interior of a cell of the SPM-equivalence decomposition Dspm (because in that case
Mt (s′ ) has only one vertex).
The case t ∈ I. We first prove the case t ∈ I. We begin with proving the following claim.
Claim: Suppose we move s to s′ infinitesimally along a free direction r; if there is a point t∗ in the
interior of the convex hull of the vertices of Ut (s) such that d(s′ , v) + |vt∗ | ≤ d(s, t) holds for each
v ∈ Ut (s) and d(s′ , v) + |vt∗ | < d(s, t) holds for at least one vertex v ∈ Ut (s), then r is in R(s, t).
We prove the claim as follows. Consider any t′ ∈ Mt (s′ ). To prove r ∈ R(s, t), it is sufficient is to
show that d(s′ , t′ ) < d(s, t).
Since s moves to s′ infinitesimally, the distance between t and t′ is also infinitesimal. Let H be
the convex hull of the vertices of Ut (s). By Observation 1, t is in the interior of H. Hence, t′ is
also in the interior of H. Further, since t′ ∈ Mt (s′ ) and Ut′ (s′ ) ⊆ Ut (s), it holds that d(s′ , t′ ) =
minv∈Ut (s) (d(s′ , v) + |vt′ |).
If t′ = t∗ , because there exists a vertex v ∈ Ut (s) with d(s′ , v) + |vt∗ | < d(s, t), we can obtain
′
d(s , t′ ) = minv∈Ut (s) (d(s′ , v) + |vt′ |) < d(s, t), which proves the claim. Below we assume t′ 6= t∗ .
7

v1
u1

s

t

v2

u2

Fig. 6. Suppose s and t have two shortest paths: πu1 ,v1 (s, t) and πu2 ,v2 (s, t), with s ∈ u1 u2 and t ∈ v1 v2 . If s moves
towards u1 and t moves towards v2 (or s moves towards u2 and t moves towards v1 ) for the same speed, then d′ui ,vi (s, t) = 0
and d′′ui ,vi (s, t) = 0 hold for both i = 1, 2.

We triangulate H by adding a line segment from t∗ to each vertex of H. Let △vi vj t∗ be a triangle
that contains t′ , where vi and vj are two adjacent vertices of H. Since t′ 6= t∗ , it is easy to see that at
least one of |t′ vi | < |t∗ vi | and |t′ vj | < |t∗ vj | must hold. Consequently, we can derive the following
d(s′ , t′ ) = min (d(s′ , v) + |vt′ |) ≤ min{d(s′ , vi ) + |vi t′ |, d(s′ , vj ) + |vj t′ |}
v∈Ut (s)

< max{d(s′ , vi ) + |vi t∗ |, d(s′ , vj ) + |vj t∗ |} ≤ d(s, t).
The last inequality is due to the condition in the claim that d(s′ , v) + |vt∗ | ≤ d(s, t) holds for each
v ∈ Ut (s). The claim is thus proved.
Now we are back to prove the lemma for the case t ∈ I. Suppose we move s infinitesimally along rs
with the unit speed to s′ , and move t simultaneously along rt with speed τ ; let t∗ be the point where
t is located when s arrives at s′ . Since |ss′ | is infinitesimal, |tt∗ | is also infinitesimal. In the following,
we will show that t∗ satisfies the condition in the above claim, which will lead to the lemma.
For each vi ∈ Ut (s), let ui be the coupled s-pivot of vi such that either d′ui ,vi (s, t) < 0, or d′ui ,vi (s, t) =
0 and d′′ui ,vi (s, t) = 0. Note that dui ,vi (s′ , t∗ ) is the length of a path from s′ to t∗ that is the concatenation
of s′ ui , π(ui , vi ), and vi t∗ . Similarly, d(s′ , vi ) + |vi t∗ | is also the length of a path from s′ to t∗ that is
the concatenation of π(s′ , vi ), and vi t∗ . Hence, the following holds
d(s′ , vi ) + |vi t∗ | ≤ dui ,vi (s′ , t∗ ).

(2)

On the one hand, for any vi ∈ Ut (s), since either d′ui ,vi (s, t) < 0 or d′ui ,vi (s, t) = 0, we obtain
dui ,vi (s, t) ≥ dui ,vi (s′ , t∗ ). Hence, with Inequality (2), we obtain d(s′ , vi ) + |vi t∗ | ≤ dui ,vi (s, t) for any
vi ∈ Ut (s).
On the other hand, since t ∈ I and t is a vertex of SPM (s), by Observation 1, Ut (s) has at least
three vertices. A vertex v of Ut (s) is called a special t-pivot if it has a coupled s-pivot u such that
d′u,v (s, t) = 0 and d′′u,v (s, t) = 0 (as shown in [3] this case happens only if rs is towards u and rt is leaving
v, or rs is leaving u and rt is towards v; e.g., see Fig 6). It was shown in [3] that Ut (s) has at most two
special t-pivots (e.g., see Fig 6). Hence, there is at least one vertex vi ∈ Ut (s) such that d′ui ,vi (s, t) < 0.
This implies that d(s, t) > dui ,vi (s′ , t∗ ). With Inequality (2), we have d(s′ , vi ) + |vi t∗ | < d(s, t).
The above proves that t∗ satisfies the condition in the claim. Hence, the lemma follows for the case
t ∈ I.
The case t ∈ V. We proceed on the third case t ∈ V. Recall the definitions of s′ , t′ , and Mt (s′ ) in
the beginning of the proof of the lemma. Our goal is to prove d(s, t) > d(s′ , t′ ). Note that since t is a
polygon vertex, t′ is either t or on one of the two polygon edges of E incident to t [7].
Consider any vertex v ∈ Ut (s). It has a coupled s-pivot u such that d′u,v (s, t) < 0, or d′u,v (s, t) = 0
and d′′u,v (s, t) = 0. In fact, since t does not move (i.e., τ = 0), it is not possible that both d′u,v (s, t) =
0 and d′′u,v (s, t) = 0 hold. Indeed, since τ = 0, according to Equation (1), d′u,v (s, t) = cos γs and
2

d′′u,v (s, t) = sin|su|γs . Both d′u,v (s, t) = 0 and d′′u,v (s, t) = 0 hold if and only if cos γs = sin γs = 0, which
is not possible for any angle γs . Hence, we obtain d′u,v (s, t) < 0. This implies that d(s, t) = du,v (s, t) >
|s′ u| + d(u, v) + |vt|. Further, since d(s, t) = |su| + d(u, v) + |vt|, it holds that |su| > |s′ u|.
8

Let v be any vertex of Ut′ (s′ ). By the definitions of s′ and t′ , Ut′ (s′ ) ⊆ Ut (s). Hence, v is in Ut (s).
The above shows that v has a coupled s-pivot u with d′u,v (s, t) < 0, and |su| > |s′ u|. Since v ∈ Ut′ (s′ ),
s′ u ∪ π(u, v) ∪ vt′ is a shortest path from s′ to t′ . Hence, d(s′ , t′ ) = |s′ u| + d(u, v) + |vt′ |.
If t′ = t, then since |su| > |s′ u|, it follows that d(s′ , t′ ) = |s′ u|+d(u, v)+|vt′ | < |su|+d(u, v)+|vt| =
d(s, t), which proves the lemma.
If t′ 6= t, as discussed above, t′ is on one of the two polygon edges incident to t, which implies that
Ut (s) has more than one vertex [7].
We claim that there must exist a vertex v ∈ Ut (s) such that |t′ v| ≤ |tv|. Indeed, suppose to
the contrary that |t′ v| > |tv| for every v ∈ Ut (s). Then, since t′ is in Mt (s′ ) and |ss′ | is infinitesimal, |tt′ | is also infinitesimal. Note that π(s, t) cannot be a line segment since otherwise Ut (s) would
have only one vertex, incurring contradiction. Also, due to our general position assumption that
no three polygon vertices are on the same line, since t is polygon vertex, the last three vertices
of any shortest path from s to t are not in the same line. Since |tt′ | is infinitesimal, it holds that
d(s, t′ ) = minv∈Ut (s) (d(s, v) + |vt′ |) (similar results were also proved in [3]). Since |t′ v| > |tv| for every
v ∈ Ut (s), d(s, t′ ) > minv∈Ut (s) (d(s, v) + |vt|) = d(s, t), which contradicts with that t is a farthest point
of s.
In light of the above claim, we assume |t′ vi | ≤ |tvi | for a vertex vi ∈ Ut (s). Let ui be the coupled
s-pivot of vi such that either d′ui ,vi (s, t) < 0 or d′ui ,vi (s, t) = 0. We have shown above that |sui | > |s′ ui |
Note that since t′ ∈ Mt (s′ ), it also holds that d(s′ , t′ ) = minv∈Ut (s) (d(s′ , v) + |vt′ |). Based on the above
discussion, we can derive the following,
d(s′ , t′ ) = min (d(s′ , v) + |vt′ |) ≤ d(s′ , vi ) + |vi t′ |
v∈Ut (s)

≤ |s′ ui | + d(ui , vi ) + |vi t′ | < |sui | + d(ui , vi ) + |vi t| = d(s, t).
This proves the lemma for the case t ∈ V.
The case t ∈ E. Let e be the polygon edge that contains t. Suppose we move s infinitesimally along
rs with the unit speed to s′ and move t simultaneously along rt with speed τ for the same time to
a point t∗ (i.e., t∗ is the location of t when s arrives at s′ ). Since |ss′ | is infinitesimal, |tt∗ | is also
infinitesimal. Since rt is parallel to e and t is in the interior of e, t∗ is also in the interior of e. Recall
that t corresponds to a set Mt (s′ ) of vertices in SPM (s′ ). Our goal is to prove d(s′ , t′ ) < d(s, t) for any
t′ ∈ Mt (s′ ). Consider any t′ ∈ Mt (s′ ). Below, we prove that d(s′ , t′ ) < d(s, t).
As shown in [7], t′ may be on e or not. In either case, t′ is infinitesimally close to t as |ss′ | is
infinitesimal.
Consider any vi ∈ Ut (s). Let ui be the coupled s-pivot of v such that either d′ui ,vi (s, t) < 0, or
′
dui ,vi (s, t) = 0 and d′′ui ,vi (s, t) = 0. Hence, dui ,vi (s, t) ≥ dui ,vi (s′ , t∗ ). By Observation 1, at least one
vertex of Ut (s) must be in the open half-plane bounded by the supporting line of e and containing the
interior of P in the small neighborhood of e; let vj be such a vertex. Since t moves along the direction
rt , which is parallel to e, according to Equation (1), it is not possible that d′′uj ,vj (s, t) = 0. This implies
that d′uj ,vj (s, t) < 0. Consequently, we obtain duj ,vj (s, t) > duj ,vj (s′ , t∗ ).
Next we prove the following claim: For any point q on e that is infinitesimally close to t, it holds
that minvi ∈Ut (s) (|s′ ui | + d(ui , vi ) + |vi q|) < d(s, t).
Indeed, if q = t∗ , then we have minvi ∈Ut (s) (|s′ ui | + d(ui , vi ) + |vi q|) ≤ |s′ uj | + d(uj , vj ) + |vj q| =
duj ,vj (s′ , t∗ ) < duj ,vj (s, t) = d(s, t).
Next we assume q 6= t∗ . By Observation 1, Ut (s) has at least one vertex in each of the two open
half-planes bounded by lt , where lt is the line through s and perpendicular to e. Without loss of
generality, we assume e is horizontal (e.g., see Fig. 7). Hence, there is a vertex v ′ ∈ Ut (s) strictly to the
left of lt and a vertex v ′′ ∈ Ut (s) strictly to the right of lt . Since both q and t∗ are infinitesimally close
to t, v ′ (resp., v ′′ ) is strictly to the left (resp., right) of both q and t∗ . Without loss of generality, we
9

t q t∗
v

t t∗ t′′
e
t′

e
v ′′

′

v0

v1

lt

Fig. 7. Since v ′ is to the left of both q and t∗ and q is to
the left t∗ , it holds that |v ′ q| < |v ′ t∗ |.

Fig. 8. Illustrating the proof: |v1 t∗ | > |v1 t′′ | > |v1 t′ |.

assume q is to the left of t∗ . Then, we have |qv ′ | < |t∗ v ′ |. Let v ′ be vk for some index k. Consequently,
minvi ∈Ut (s) (|s′ ui |+d(ui , vi )+|vi q|) ≤ |s′ uk |+d(uk , vk )+|vk q| < |s′ uk |+d(uk , vk )+|vk t∗ | = duk ,vk (s′ , t∗ ) ≤
duk ,vk (s, t) = d(s, t).
Therefore, the above claim is proved.
Now we are back to our original problem for proving d(s′ , t′ ) < d(s, t). Depending on whether t′ is
on e or not, there are two cases.
If t′ is on e, then since t′ is infinitesimally close to t, then by the above claim, it holds that
minvi ∈Ut (s) (|s′ ui |+d(ui , vi )+|vi t′ |) < d(s, t). Note that since t′ is in Mt (s′ ), d(s′ , t′ ) = minvi ∈Ut (s) (|s′ ui |+
d(ui , vi ) + |vi t′ |). Hence, we obtain d(s′ , t′ ) < d(s, t).
If t′ is not on e, the proof is somewhat similar in spirit to the case t ∈ I.
We begin with proving an observation that there must be a vertex v ∈ Ut (s) such that |vt′ | < |vt∗ |.
Without loss of generality, we assume e is horizontal. All vertices of Ut (s) are in one of the closed
half-planes bounded by le , where le is the horizontal line containing e. Without loss of generality, we
assume all vertices of Ut (s) are below or on the line le , i.e., they are in the closed half-plane bounded
by le from above (let h denote the half-plane). Since t′ is not on e and t′ is infinitesimally close to
t, t′ is strictly below le . Next, we do a “triangulation” around the point t∗ . Imagine that we rotate
a rightwards ray originated from t∗ clockwise to sweep the half-plane h, and let v1 , v2 , . . . vm be the
vertices of Ut (s) hit by our sweeping ray in order. Note that v1 and vm may be on e. If v1 is not on
e, let v0 be the right endpoint of e. If vm is not on e, let vm+1 be the left endpoint of e. Since t′ is
infinitesimally close to t and t′ is in h, t′ must be in one of the triangles △t∗ vi vi+1 for 0 ≤ i ≤ m.
Suppose t′ is in △t∗ vi vi+1 for some 1 ≤ i ≤ m − 1. Then, vi and vi+1 are both from Ut (s). Since t′ is
in △t∗ vi vi+1 , one of |t′ vi | < |t∗ vi | and |t′ vj | < |t∗ vj | must hold, and this proves the above observation.
If t′ is in △t∗ vi vi+1 for i = 0 or m, then one of vi and vi+1 is not in Ut (s). So we cannot use the
same argument as above. In the following, we only prove the case for i = 0, and the other case is
similar. When t′ is in △t∗ v0 v1 , v0 is the right endpoint of e and v1 is not on e (e.g., see Fig. 8). In the
following, we show that |v1 t′ | < |v1 t∗ |, which will prove the observation.
By Observation 1, Ut (s) has at least one vertex strictly to right of the vertical line through t. Since
is infinitesimal, Ut (s) has at least one vertex strictly to the right of the vertical line lt∗ through
t∗ as well. By the definition of v1 , v1 must be strictly to the right of lt∗ . Hence, the slope of the line
through v1 and t∗ is strictly negative. Recall that t′ is in △t∗ v0 v1 . If t′ is on v1 t∗ , then since t′ 6= t∗
(due to t′ 6∈ e), we have |v1 t∗ | > |v1 t′ |. Otherwise, we extend v1 t′ until it hits v0 t∗ at a point t′′ , which
is strictly to the right of t∗ . Since both t∗ and t′ are infinitesimally close to t, |t∗ t′ | is also infinitesimal
and thus |t∗ t′′ | is infinitesimal as well. Since the slope of v1 t∗ is strictly negative and t′′ is strictly to
the right of t∗ , we obtain |v1 t∗ | > |v1 t′′ | > |v1 t′ |.
|tt∗ |

The above proves the observation.
In light of the above observation, we assume |t′ vi | < |t∗ vi | for a vertex vi ∈ Ut (s). Let ui be
the coupled s-pivot of vi such that either d′ui ,vi (s, t) < 0, or d′ui ,vi (s, t) = 0. Note that dui ,vi (s, t) ≥
dui ,vi (s′ , t∗ ). Since t′ is in Mt (s′ ), d(s′ , t′ ) = minv∈Ut (s) (d(s′ , v) + |vt′ |). Based on the above discussion,
10

t
hs (t)
s
Fig. 9. Illustrating Observation 2: The blue direction is towards the interior of hs (t) and thus is in R(s, t).

we derive the following
d(s′ , t′ ) = min (d(s′ , v) + |vt′ |) ≤ d(s′ , vi ) + |vi t′ | < d(s′ , vi ) + |vi t∗ |
v∈Ut (s)

≤ |s′ ui | + d(ui , vi ) + |vi t∗ | = dui ,vi (s′ , t∗ ) ≤ dui ,vi (s, t) = d(s, t).
This proves that d(s′ , t′ ) < d(s, t). This finishes the proof for the case t ∈ E.
The lemma is thus proved for all three cases.

Lemma 2 is on the case where s is not visible to t. If s is visible to t, the result is trivial, as shown
in Observation 2.
Observation 2 Suppose t is a farthest point of s and s is visible to t. Then t must be a polygon vertex
of V. Further, a free direction rs of s is in R(s, t) if and only if rs is towards the interior of hs (t),
where hs (t) is the open half-plane containing t and bounded by the line through s and perpendicular to
st (e.g., see Fig. 9).
Proof: Since s is visible to t, st is the only shortest path from s to t. As t is a vertex of SPM (s), t
cannot be in I or E, since otherwise there would be more than one shortest s-t path. Thus, t ∈ V.
Consider any free direction rs of s. Suppose we move s infinitesimally along rs to s′ . According
to our definition of “visibility”, st does not contain any polygon vertex in its interior. Since |ss′ | is
infinitesimal, s′ is also visible to t. Therefore, the point t, as a vertex of SPM (s), corresponds to a
vertex of SPM (s′ ) that is t itself. Hence, rs is in R(s, t) if and only |s′ t| < |st|. Clearly, |s′ t| < |st| if
and only if rs is towards the interior of the open half-plane hs (t).

By Observation 2, if s is visible to t, then the range R(s, t) is the intersection of the free direction
range Rf (s) and an open range of size π delimited by the open half-plane hs (t).
The next lemma is proved by using Lemmas 1 and 2 as well as Observation 2.
Lemma 3. Among all points of P that have topologically equivalent shortest path maps in P, there is
at most one geodesic center. This implies that each cell or edge of Dspm contains at most one geodesic
center in its interior, which further implies that the number of geodesic centers of P is O(|Dspm |),
where |Dspm | is the combinatorial complexity of Dspm .
Proof: Let Q be any set of points of P that have topologically equivalent shortest path maps in P.
We show that there is at most one geodesic center in Q, which will prove the lemma. Note that any
two points of Q must be visible to each other since otherwise their shortest path maps would not
be topologically equivalent. Let s be a geodesic center in Q. Let s′ be any other point in Q. In the
following, we prove that dmax (s′ ) > dmax (s), which implies that s′ cannot be a geodesic center, and
thus the lemma will be proved.
Consider the direction rs of moving s towards s′ . Since s is visible to s′ , rs is a free direction. Since
s is a geodesic center, by Lemma 1, R(s) is empty. Thus, s has a farthest point t such that rs 6∈ R(s, t).
Because t is a farthest point of s, d(s, t) = dmax (s).
If s is visible to t, by Observation 2, rs is not towards the interior of the open half-plane hs (t).
Hence, |s′ t| > |st|, and thus dmax (s′ ) ≥ d(s′ , t) ≥ |s′ t| > |st| = d(s, t) = dmax (s).
In the following, we assume that s is not visible to t. Depending on whether t is in V, E, or I,
there are three cases.
11

The case t ∈ V. Suppose t ∈ V. Due to rs 6∈ R(s, t), by Lemma 2(3), if we move s along rs with unit
speed, there exists a vertex v ∈ Ut (s) such that either d′u,v (s, t) > 0, or d′u,v (s, t) = 0 and d′′u,v (s, v) 6= 0,
for any coupled s-pivot u of v. Let u be any coupled s-pivot of v.
Note that su ∪ π(u, v) ∪ vt is a shortest path from s to t, whose length is du,v (s, t). Since SPM (s)
and SPM (s′ ) are topologically equivalent and t is a polygon vertex, s′ u ∪ π(u, v) ∪ vt is a shortest path
from s′ to t, whose length is du,v (s′ , t). In the following, we show that du,v (s′ , t) > du,v (s, t).
Indeed, as s moves towards s′ along rs with unit speed, recall that the second derivative d′′u,v (s, t) ≥
0 always holds. Hence, if d′u,v (s, t) > 0, then during the movement of s, it always holds that d′u,v (s, t) >
0. This implies that du,v (s′ , t) > du,v (s, t). Similarly, if d′u,v (s, t) = 0 and d′′u,v (s, t) 6= 0, then since
d′′u,v (s, t) ≥ 0, we obtain d′′u,v (s, t) > 0. Consequently, as s moves towards s′ along rs with unit speed,
except for the starting moment, it holds that d′u,v (s, t) > 0 and d′′u,v (s, t) ≥ 0. Thus, du,v (s′ , t) >
du,v (s, t).
The above proves that d(s′ , t) = du,v (s′ , t) > du,v (s, t) = d(s, t). Therefore, we obtain dmax (s′ ) >
dmax (s) since dmax (s′ ) ≥ d(s′ , t) > d(s, t) = dmax (s).
The case t ∈ E. If t ∈ E, let e denote the polygon edge of E that contains t. Due to rs 6∈ R(s, t), by
Lemma 2(2), if we move s along rs with unit speed and move t along e with any speed τ ≥ 0, there
exists a vertex v ∈ Ut (s) such that either d′u,v (s, t) > 0, or d′u,v (s, t) = 0 and d′′u,v (s, v) 6= 0, for any
coupled s-pivot u of v. Let u be any coupled s-pivot of v.
Note that su ∪ π(u, v) ∪ vt is a shortest path from s to t, whose length is du,v (s, t). Since SPM (s)
and SPM (s′ ) are topologically equivalent and t ∈ e, the point t, as a vertex of SPM (s), corresponds
to one and only one vertex t′ in SPM (s′ ) that is also on e. Then, s′ u ∪ d(u, v) ∪ vt′ is a shortest path
from s′ to t′ , whose length is du,v (s′ , t′ ). In the following, we show that du,v (s′ , t′ ) > du,v (s, t), which
will lead to dmax (s′ ) > dmax (s) as dmax (s′ ) ≥ d(s′ , t′ ) = du,v (s′ , t′ ) and dmax (s) = d(s, t) = du,v (s, t).
Suppose we move s along rs towards s′ with unit speed and move t along e towards t′ with speed
τ = |tt′ |/|ss′ |. Hence, when s arrives at s′ , t arrives at t′ simultaneously. By Lemma 2(2), either
d′u,v (s, t) > 0, or d′u,v (s, t) = 0 and d′′u,v (s, v) 6= 0. In either case, by the same analysis as in the above
case t ∈ V, we can show that du,v (s′ , t′ ) > du,v (s, t) and we omit the details.
The case t ∈ I. The proof for this case is very similar. Due to rs 6∈ R(s, t), by Lemma 2(1), if we move
s along rs with unit speed and move t along any free direction with any speed τ ≥ 0, there exists a
vertex v ∈ Ut (s) such that either d′u,v (s, t) > 0, or d′u,v (s, t) = 0 and d′′u,v (s, v) 6= 0, for any coupled
s-pivot u of v.
Since SPM (s) and SPM (s′ ) are topologically equivalent, t corresponds to one and only one vertex
t′ in SPM (s′ ) that is also in I. The rest of the argument is exactly the same as that for the case t ∈ E.
We can prove that dmax (s′ ) > dmax (s) and we omit the details.
This completes the proof for the lemma.

Remark: By extending the proof of Lemma 3, it is possible to obtain a slightly stronger result:
Every cell (including its boundary) of Dspm contains at most one geodesic center.
The following corollary can be proved by the same techniques as Lemma 3, and it implies that if
t is a farthest point of s, then slightly moving s along a free direction that is not in R(s, t) can never
obtain a geodesic center.
Corollary 1. Suppose t is a farthest point of s. If we move s infinitesimally along a free direction
that is not in R(s, t), then dmax (s) will become strictly larger.
Proof: Let rs be any free direction that is not in R(s, t). Suppose we move s infinitesimally along rs
to s′ . By using exactly the same argument as in the proof of Lemma 3, we can show that SPM (t) has
a vertex t′ corresponding to t in SPM (s) such that d(s, t) < d(s′ , t′ ). Therefore, we obtain dmax (s) =
d(s, t) < d(s′ , t′ ) ≤ dmax (s′ ), which proves the corollary.

12

So far we have shown that the total number of geodesic centers is bounded by the combinatorial
size of Dspm. This result, although it is interesting in its own right, is not quite helpful for computing
the geodesic centers. In order to compute candidate points for geodesic centers, we need to find a way
to determine the range R(s, t). It turns out that it is sufficient to determine R(s, t) when t is in a
non-degenerate position with respect to s in the following sense: Suppose t is a farthest point of s;
we say that t is non-degenerate with respect to s if there are exactly three, two, and one shortest s-t
paths for t in I, E, and V, respectively (by Observation 1, this implies that |Ut (s)| is 3, 2, and 1,
respectively for the three cases).
Lemma 2 gives a sufficient condition for a direction in R(s, t). The following lemma gives both a
sufficient and a necessary condition for a direction in R(s, t) when t is non-degenerate, and the lemma
will be used to explicitly compute the range R(s, t) in Section 4. Note that Observation 2 already gives
a way to determine R(s, t) when s is visible to t.
Lemma 4. Suppose t is a non-degenerate farthest point of s and s is not visible to t. Then, a free
direction rs is in R(s, t) if and only if
1. for t ∈ I, there is a free direction rt for t with a speed τ ≥ 0 such that when we move s along rs
with unit speed and move t along rt with speed τ , each vertex v ∈ Ut (s) has a coupled s-pivot u
with d′u,v (s, t) < 0.
2. for t ∈ E, there is a free direction rt for t that is parallel to the polygon edge containing t with a
speed τ ≥ 0 such that when we move s along rs with unit speed and move t along rt with speed τ ,
each vertex v ∈ Ut (s) has a coupled s-pivot u with d′u,v (s, t) < 0.
3. for t ∈ V, when we move s along rs with unit speed, each vertex v ∈ Ut (s) has a coupled s-pivot u
with d′u,v (s, t) < 0.
Proof: First of all, in any of these three cases, if the condition in the lemma statement holds, by
Lemma 2, rs is in R(s, t). In the following, we prove the other direction of the lemma.
Let rs be in R(s, t). Suppose we move s along rs infinitesimally to s′ . Since t is non-degenerate
with respect to s, the point t, as a vertex of SPM (s), corresponds to one and only one vertex t′ in
SPM (s′ ) (i.e., Mt (s′ ) = {t′ }) [7]. Due to rs ∈ R(s, t), d(s, t) > d(s′ , t′ ). In the following, we prove the
three cases: t ∈ I, t ∈ E, and t ∈ V.
The case t ∈ I. Suppose we move s towards s′ with unit speed and move t towards t′ with speed
|tt′ |/|ss′ |. Then, when s arrives at s′ , t arrives at t′ simultaneously.
Consider any vertex v ∈ Ut (s). To prove the lemma for this case, our goal is to show that there
exists a coupled s-pivot u of v with d′u,v (s, t) < 0.
Let u be any coupled s-pivot of v. Hence, d(s, t) = du,v (s, t). Since Mt (s′ ) = {t′ }, s′ u ∪ π(u, v) ∪ vt′
is a shortest path from s′ to t′ , and thus d(s′ , t′ ) = du,v (s′ , t′ ). We claim that d′u,v (s, t) < 0. Suppose
to the contrary that d′u,v (s, t) ≥ 0. If d′u,v (s, t) > 0, then we would obtain du,v (s, t) < du,v (s′ , t′ ), which
contradicts with d(s, t) > d(s′ , t′ ). Similarly, if d′u,v (s, t) = 0, since d′′u,v (s, t) ≥ 0, we would obtain
du,v (s, t) ≤ du,v (s′ , t′ ), which contradicts with d(s, t) > d(s′ , t′ ). Hence, d′u,v (s, t) < 0 is proved.
This proves the lemma for the case t ∈ I.
The case t ∈ E. Let e be the polygon edge containing t. Then, t′ is also on e. Suppose we move s
towards s′ with unit speed and move t on e towards t′ with speed |tt′ |/|ss′ |. Hence, when s arrives at
s′ , t arrives at t′ simultaneously.
Consider any vertex v ∈ Ut (s). Let u be any coupled s-pivot of v. As in the above case, du,v (s, t) =
d(s, t) and du,v (s′ , t′ ) = d(s′ , t′ ). Using the same analysis as in the above case we can also prove that
d′u,v (s, t) < 0, which leads to the lemma.
13

The case t ∈ V. In this case, since t is a polygon vertex, t′ = t. Suppose we move s towards s′ with unit
speed. Consider any vertex v ∈ Ut (s). Let u be any coupled s-pivot of v. Again, du,v (s, t) = d(s, t) and
du,v (s′ , t′ ) = d(s′ , t′ ). Using the same analysis as in the first case we can also prove that d′u,v (s, t) < 0,
which leads to the lemma.

Lemma 4 will be used to determine the range R(s, t) for a non-degenerate farthest point of s. The
details are deferred in Section 4, where we will show that R(s, t) is the intersection of the free direction
range Rf (s) and an open range of size π (i.e., the previously mentioned π-range property).
In addition, we present Lemma 5, which will be useful for computing the candidate points in
Section 5. If a farthest point t of s is not non-degenerate, then we say that t is degenerate (note that s
cannot be visible to t in the degenerate case). Lemma 5 provides a sufficient condition for a direction
in R(s, t) particularly for a degenerate farthest point t of s.
Lemma 5. Suppose t is a degenerate farthest point of s.
1. For t ∈ I, a free direction rs is in R(s, t) if the following conditions are satisfied: (1) there exist
three vertices v1 , v2 , v3 ∈ Ut (s) such that t is in the interior of the triangle △v1 v2 v3 (i.e., {v1 , v2 , v3 }
satisfies the same condition as Ut (s) in Observation 1(1)); (2) there exists a free direction rt for
t with a speed τ ≥ 0 such that when we move s along rs with unit speed and move t along rt with
speed τ , each vertex v ∈ {v1 , v2 , v3 } has a coupled s-pivot u with d′u,v (s, t) < 0.
2. For t ∈ E, suppose e is the polygon edge containing t. A free direction rs is in R(s, t) if the
following conditions are satisfied: (1) there exist two vertices v1 , v2 ∈ Ut (s) such that {v1 , v2 } has
one vertex in each of the two open half-planes bounded by the line through t and perpendicular to
e, and {v1 , v2 } has at least one vertex in the open half-plane bounded by the supporting line of e
and containing the interior of P in the small neighborhood of e (i.e., {v1 , v2 } satisfies the same
condition as Ut (s) in Observation 1(2)); (2) there is a free direction rt for t parallel to e with a
speed τ ≥ 0 such that when we move s along rs with unit speed and move t along rt with speed τ ,
each vertex v ∈ {v1 , v2 } has a coupled s-pivot u with d′u,v (s, t) < 0.
Proof: The proof uses similar techniques as in the proof of Lemma 2. Indeed, the proof of Lemma 2
mainly relies on Observation 1. Here, for the case t ∈ I, {v1 , v2 , v3 } satisfies Observation 1(1); for the
case t ∈ E, {v1 , v2 } satisfies Observation 1(2). Therefore, similar techniques as in the proof of Lemma
2 can be used here. We briefly discuss it below.
The case t ∈ I. We first consider the case t ∈ I. Let v1 , v2 , and v3 be the polygon vertices specified in
the lemma statement. For each i with 1 ≤ i ≤ 3, let ui be the coupled s-pivot of vi with d′ui ,vi (s, t) < 0.
Suppose we move s along rs infinitesimally with unit speed to s′ and simultaneously move t along rt
with speed τ to a point t∗ (i.e., t∗ is the location of t when s arrives at s′ ). Since |ss′ | is infinitesimal,
|tt∗ | is also infinitesimal. Since t is in the interior of △v1 v2 v3 , t∗ is also in the interior of the triangle.
Consider any t′ in Mt (s′ ). To prove that rs is in R(s, t), our goal is to show that d(s′ , t′ ) < d(s, t).
Since |ss′ | is infinitesimal, |tt′ | is also infinitesimal and t′ is also in the interior of △v1 v2 v3 . For
each 1 ≤ i ≤ 3, since d′ui ,vi (s, t) < 0, it holds that dui ,vi (s, t) > dui ,vi (s′ , t∗ ). The three segments t∗ vi
for i = 1, 2, 3 partition △v1 v2 v3 into three smaller triangles and t′ must be one of them. Without
loss of generality, assume t′ is in △v1 v2 t∗ . Hence, at least one of |t′ v1 | < |t∗ v1 | and |t′ v2 | < |t∗ v2 |
holds. Without loss of generality, we assume the former one holds. Therefore, we can derive d(s′ , t′ ) ≤
|s′ u1 | + d(u1 , v1 ) + |v1 t′ | < |s′ u1 | + d(u1 , v1 ) + |v1 t∗ | = du1 ,v1 (s′ , t∗ ) < du1 ,v1 (s, t) = d(s, t).
The case t ∈ E. Let v1 and v2 be the two polygon vertices specified in the lemma statement. For each
i with 1 ≤ i ≤ 2, let ui be the coupled s-pivot of vi with d′ui ,vi (s, t) < 0. Suppose we move s along
rs infinitesimally with unit speed to s′ and simultaneously move t along e with speed τ to a point t∗ .
Since |ss′ | is infinitesimal, |tt∗ | is also infinitesimal. Consider any t′ in Mt (s′ ). To prove that rs is in
R(s, t), our goal is to show that d(s′ , t′ ) < d(s, t).
14

For each 1 ≤ i ≤ 2, since d′ui ,vi (s, t) < 0, it holds that dui ,vi (s, t) > dui ,vi (s′ , t∗ ). Since |tt∗ | is
infinitesimal, {v1 , v2 } has one vertex in each of the open half-planes bounded by the line through t∗
and perpendicular to e. Also, because at least one vertex of v1 and v2 is in the open half-plane bounded
by the supporting line of e and containing the interior of P in the small neighborhood of e, regardless
of whether t′ is on e or not, we can use the similar approach as in the proof of Lemma 2 (for the case
t ∈ E) to show that either |t′ v1 | < |t∗ v1 | or |t′ v2 | < |t∗ v2 | holds. Consequently, by the similar argument
as the above case for t ∈ I, we can obtain d(s′ , t′ ) < d(s, t).


4

Determining the Admissible Direction Range R(s, t) and the π-Range
Property

In this section, we determine the admissible direction range R(s, t) for any point s and any of its nondegenerate farthest point t. In particular, we will prove the π-range property mentioned in Section
1.
Depending on whether t is in V, E, and I, there are three cases. Recall that Rf (s) is the range of
all free directions of s. In each case, we will show that R(s, t) is the intersection of Rf (s) and an open
range Rπ (s, t) of size π. We call Rπ (s, t) the π-range. As will be seen later, the π-range Rπ (s, t) can
be explicitly determined based on the positions of s, t, and the vertices of Us (t) and Ut (s).
In fact, for each case, we will give more general results that are on shortest path distance functions.
These more general results will also be useful for computing the candidate points later in Section 5.
4.1

The Case t ∈ V

We first discuss the case t ∈ V. The result is relatively straightforward in this case. If s is visible to
t, the π-range Rπ (s, t) is defined to be the open range of directions delimited by the open half-plane
hs (t) as defined in Observation 2; by Observation 2, R(s, t) = Rf (s) ∩ Rπ (s, t).
In the following, we assume s is not visible to t. We first present a more general result on a shortest
path function. Let s and t be any two points in P such that t is in V and s is not visible to t. Let
π(s, t) be any shortest s-t path in P. Let u and v be the s-pivot and t-pivot in π(s, t), respectively.
Thus, du,v (s, t) = |su| + d(u, v) + |vt|. Now we consider du,v (s, t) as a function of s and t in the entire
plane R2 (not only in P; namely, when we move s and t, they are allowed to move outside P, but the
function du,v (s, t) is always defined as |su| + d(u, v) + |vt|, where d(u, v) is a fixed value).
The π-range Rπ (s, t) is defined with respect to t and the path π(s, t) as follows: a direction rs for
s is in Rπ (s, t) if d′u,v (s, t) < 0 when we move s along rs with unit speed. The following lemma is quite
straightforward.
Lemma 6. The π-range Rπ (s, t) is exactly the open range of size π delimited by hs (u), where hs (u)
is the open half-plane containing u and bounded by the line through s and perpendicular to su.
Proof: The analysis is similar to Observation 2. Suppose we move s along a direction rs with unit
speed. Then, d′u,v (s, t) < 0 if and only if rs is towards the interior of hs (u).

Now we are back to our original problem to determine R(s, t) for a non-degenerate farthest point
t of s with t ∈ V. Since t is non-degenerate and t is in V, there is only one shortest path π(s, t) from s
to t. We define Rπ (s, t) as above. Based on Observation 2 and Lemmas 4(3), we have Lemma 7, and
thus R(s, t) can be determined by Observation 2 and Lemma 6.
Lemma 7. R(s, t) = Rf (s) ∩ Rπ (s, t).
Proof: If s is visible to t, we have already shown that the lemma is true. Below we assume s is not
visible to t.
Let u and v be the s-pivot and t-pivot in π(s, t), respectively. Note that v is the only vertex in
Ut (s) and u is the only vertex in Us (t).
15

1. Consider any direction rs ∈ R(s, t), i.e., rs is an admissible direction for s with respect to t.
According to Lemma 4(3), when we move s along rs with unit speed, it holds that d′u,v (s, t) < 0. This
implies that rs is in Rπ (s, t). Since rs is in R(s, t), rs is in Rf (s). Therefore, rs is in Rf (s)∩ Rπ (s, t).
2. Consider any direction rs in Rf (s) ∩ Rπ (s, t). First of all, rs is a free direction. Since rs is in
Rπ (s, t), when s moves along rs with unit speed, d′u,v (s, t) < 0. Since v is the only vertex in Ut (s),
by Lemma 4(3), rs is in R(s, t).
The lemma is thus proved.
4.2



The Case t ∈ E

The analysis for this case is substantially more complicated than the previous case, although the next
case for t ∈ I is even more challenging. One may consider the analysis for this case as a “warm-up”
for the most general case t ∈ I.
As in the previous case, we first present a more general result that is on two shortest path distance
functions. Let s and t be any two points in P such that t is in E and there are two shortest s-t paths
π1 (s, t) and π2 (s, t) (this implies that s is not visible to t). Let e be the polygon edge containing t
and let l(e) denote the line containing e. For each i = 1, 2, let πi (s, t) = πui ,vi (s, t), i.e., ui and vi are
the s-pivot and t-pivot of πi (s, t), respectively. We further require the set {v1 , v2 } satisfy the same
condition as Ut (s) in Observation 1(2), i.e., {v1 , v2 } has at least one vertex in the open half-plane
bounded by l(e) and containing the interior of P in the small neighborhood of e, and it has at least
one vertex in each of the two open half-planes bounded by the line through t and perpendicular to e.
We say that the two shortest paths π1 (s, t) and π2 (s, t) are canonical with respect to s and t if {v1 , v2 }
satisfies the above condition. In the following, we assume π1 (s, t) and π2 (s, t) are canonical. Note that
the condition implies that v1 6= v2 . However, u1 = u2 is possible.
For each i = 1, 2, we consider dui ,vi (s, t) = |sui | + d(ui , vi ) + |vi t| as a function of s ∈ R2 (instead
of s ∈ P only) and t ∈ e.
In this case, the π-range Rπ (s, t) of s is defined with respect to t and the two paths π1 (s, t) and
π2 (s, t) as follows: a direction rs for s is in Rπ (s, t) if there exists a direction rt parallel to e for t with
a speed τ ≥ 0 such that when we move s along rs with unit speed and move t along rt with speed
τ ≥ 0, d′ui ,vi (s, t) < 0 holds for i = 1, 2.
In Section 4.1, we showed that the π-range for the case s ∈ V is an open range of size π. Here we
will show a similar result in Lemma 8 unless a special case happens. Although the analysis in Section
4.1 is quite straightforward, the result here for two functions dui ,vi (s, t) with i = 1, 2 is somewhat
surprising and the proof is substantially more difficult (one could imagine that a similar result for
three functions, as shown in Section 4.4, is even more surprising). Before presenting Lemma 8, we
introduce some notation.
→
For any two points p and q in the plane, define −
pq as the direction from p to q.
Recall that the angle of any direction r is defined to be the angle in [0, 2π) counterclockwise from
→, and let α denote the
the positive direction of the x-axis. Let α1 denote the angle of the direction −
su
1
2
→ (e.g., see Fig. 10). Note that by our way of defining pivot vertices, α = α
angle of the direction −
su
2
1
2
if and only if u1 = u2 .
Note that v1 and v2 are in a closed half-plane bounded by the line l(e). We assign a direction to
l(e) such that each of v1 and v2 are to the left or on l(e). Define βi as the smallest angle to rotate
−
→
l(e) counterclockwise such that the direction of l(e) becomes the same as the direction tvi , for each
i = 1, 2 (e.g., see Fig. 10). Hence, both β1 and β2 are in [0, π]. Without of loss of generality, we assume
β1 ≤ β2 (otherwise the analysis is symmetric). Since {v1 , v2 } contains at least one vertex in each of
the open half-planes bounded by the line through t and perpendicular to e, we have β1 ∈ [0, π/2) and
β2 ∈ (π/2, π]. Further, since at least one of v1 and v2 is not on l(e), it is not possible that both β = 0
and β = π hold.
16

v2

u2

v1
β2

β1

u1

α2
α1

l(e)

s

t

Fig. 10. Illustrating the definitions of the angles.

u2

u1

u2

u1 = u2

s

α2

α1

v2

v1
t

v1

v2

α1

s

26.66◦

β2

v1

s
v2

u1

β1

t

t

Fig. 11. Illustrating several concrete examples for Lemma 8. Left: the special case (the vertical line through t bisects
∠v1 tv2 ); in this case, Rπ (s, t) = ∅. Middle: the case where α1 = α2 , and thus α = 0, sin(α) = 0, and u1 = u2 ; in this case,
Rπ (s, t) = (α1 −π/2, α1 +π/2), which is delimited by the open half-plane (marked with red color in the figure) bounded by
the line through s and perpendicular to su1 . Right: the most general case where α1 = 30◦ , α2 = 90◦ , β1 = 30◦ , β2 = 135◦ ;
γ
by calculation, λ ≈ 1.3165, arctan( sin(α)
) ≈ 56.66◦ , and thus, Rπ (s, t) ≈ (α1 − 56.66◦ , α1 + 56.66◦ ) = (−26.66◦ , 153.34◦ );
the open half-plane that delimits Rπ (s, t) is marked with red color in the figure.

Let α = α2 − α1 . We refer to the case where β1 + β2 = π and α = ±π (i.e., α is π or −π) as the
special case. In the special case, s is on u1 u2 and the vertical line through t and perpendicular to l(e)
bisects the angle ∠v1 tv2 .
Lemma 8. The π-range Rπ (s, t) is determined as follows (e.g., see Fig. 11).

Rπ (s, t) =


λ
λ
), α1 − arctan( sin(α)
) + π)
(α1 − arctan( sin(α)




λ
λ


(α1 − arctan( sin(α) ) − π, α1 − arctan( sin(α) ))
(α1 − π/2, α1 + π/2)




(α1 − 3π/2, α1 − π/2)



∅

if sin(α) > 0,
if sin(α) < 0,
if sin(α) = 0 and λ > 0,
if sin(α) = 0 and λ < 0,
if sin(α) = 0 and λ = 0,

β2
where λ = cos α − cos
cos β1 . Further, α = ±π and β1 + β2 = π (i.e., the special case) if and only if
sin(α) = 0 and λ = 0.

Remark: Unlike Lemma 6 whose geometric intuition is very straightforward, it is not clear to us how
to interpret Lemma 8 intuitively.
We defer the proof of Lemma 8 to Section 4.3. According to Lemma 8, if the special case happens,
Rπ (s, t) is empty; otherwise, it is an open range of size exactly π. Since α = 0 if and only if u1 = u2 ,
the case u1 = u2 is also covered by the lemma.
Now we are back to our original problem to determine the range R(s, t) for a non-degenerate
farthest point t ∈ E of s. By Observation 2, s is not visible to t. Further, s and t have exactly
two shortest paths π1 (s, t) and π2 (s, t). Clearly, by Observation 1(2), the two paths are canonical.
Therefore, the π-range Rπ (s, t) of s with respect to t and the two shortest paths π1 (s, t) and π2 (s, t)
can be determined by Lemma 8.
By using Lemma 4(2), we have the following lemma.
17

s
P

t
Fig. 12. Illustrating an example in which a geodesic center s is in I and has only one farthest point t. The polygonal
domain P is between two (very close) concentric squares plus an additional (very small) triangle so that s is in I. The
point s is at the middle of the top edge of the inner square, and t is at the middle of the bottom edge of the outer square.
One can verify that s is a geodesic center and t is the only farthest point of s. The two shortest paths from s to t are
shown with red dashed segments. Note that the middle point of every edge of the inner square is a geodesic center.

Lemma 9. R(s, t) = Rπ (s, t) ∩ Rf (s).
Proof: For each i = 1, 2, let ui and vi be the s-pivot and t-pivot of the shortest path πi (s, t), respectively. Since s and t have only two shortest paths π1 (s, t) and π2 (s, t), Ut (s) = {v1 , v2 } and
Us (t) = {u1 , u2 }. Further, for each i = 1, 2, vi has only one s-pivot, which is ui .
1. Consider any direction rs ∈ R(s, t). Clearly, rs ∈ Rf (s). By Lemma 4(2), there exists a direction
rt parallel to e for t with a speed τ ≥ 0 such that if we move s along rs for unit speed and move
t along lt with speed τ , each vertex v ∈ Ut (s) has a coupled s-pivot u with d′u,v (s, t) < 0. Since
Ut (s) = {v1 , v2 } and for each i = 1, 2, vi has only one s-pivot ui , it holds that d′ui ,vi (s, t) < 0.
Hence, rs is in Rπ (s, t).
2. Consider any rs in Rf (s, t) ∩ Rπ (s, t). First of all, rs is a free direction. Since rs is in Rπ (s, t), there
exists a direction rt parallel to e for t with a speed τ ≥ 0 such that if we move s along rs for unit
speed and move t along rt with speed τ , d′ui ,vi (s, t) < 0 for each i = 1, 2. Since Ut (s) = {v1 , v2 },
according to Lemma 4(2), rs is in R(s, t).
The lemma thus follows.

Suppose t is the only farthest point of s and t is non-degenerate. According to Lemma 8, if the
special case happens, Rπ (s, t) = ∅, and thus R(s, t) = ∅ by Lemma 9. By Corollary 1, whenever we
move s along any free direction infinitesimally, the value dmax (s) will be strictly increasing. Therefore,
it is possible that the point s, which is in I and has only one farthest point, is a geodesic center. It
is not difficult to construct such an example by following the left figure of Fig. 11; e.g., see Fig. 12.
Hence, we have the following corollary.
Corollary 2. It is possible that a geodesic center is in I and has only one farthest point.

4.3

Proof of Lemma 8

Consider any direction rs for moving s. Let θs denote the angle of rs . Recall that the moving direction
rt for t is parallel to e and we have assigned a direction to the line l(e). Let θt denote the smallest angle
to rotate l(e) such that l(e) becomes the same direction as rt (thus the definition of θt is “consistent”
with the definitions of β1 and β2 ). Since rt is parallel to e, θt is either 0 or π.
According to Equation (1), we can obtain the derivatives of the two functions du1 ,v1 (s, t) and
du2 ,v2 (s, t) as follows
(
d′u1 ,v1 (s, t) = − cos(α1 − θs ) − τ · cos(β1 − θt ),
(3)
d′u2 ,v2 (s, t) = − cos(α2 − θs ) − τ · cos(β2 − θt ).
18

Therefore, for each i = 1, 2, d′ui ,vi (s, t) is a function of θs , θt , and τ . In order to simplify our proof
for Lemma 8, we first give the following lemma.
Lemma 10. A direction rs is in Rπ (s, t) if and only if there exist θt ∈ {0, π} and τ ≥ 0 such that
d′u1 ,v1 (s, t) = 0 and d′u2 ,v2 (s, t) < 0 (the same also holds if we exchange the indices 1 and 2).
Proof: Given any direction rs for s, the angle θs is fixed, and thus for each i = 1, 2, d′ui ,vi (s, t) is a
function of θt and τ . In the following, we will use d′i (θt , τ ) to represent d′ui ,vi (s, t) for each i = 1, 2.
We first prove one direction of the lemma. Assume d′1 (θt , τ ) = 0 and d′2 (θt , τ ) < 0 for some
θt ∈ {0, π} and τ ≥ 0. Our goal is to show that rs is in Rπ (s, t). To this end, it is sufficient to find
another pair (θt′ , τ ′ ) with θt′ ∈ {0, π} and τ ′ ≥ 0 such that d′1 (θt′ , τ ′ ) < 0 and d′2 (θt′ , τ ′ ) < 0.
Recall that neither β1 nor β2 can be π/2. Since θt is either 0 or π, β1 − θt 6= ±π/2, and thus
cos(β1 − θt ) 6= 0. Since d′1 (θt , τ ) = 0 and d′2 (θt , τ ) < 0, if τ > 0, regardless of whether cos(β1 − θt )
is positive or negative, we can always change τ infinitesimally to a new value τ ′ > 0 such that
d′1 (θt , τ ′ ) < 0 and d′2 (θt , τ ′ ) < 0.
If τ = 0, then by Equation (3), − cos(α1 − θs ) = 0 and − cos(α2 − θs ) < 0. We let τ ′ be an
infinitesimally small positive value and let θt′ be 0. Since β1 ∈ [0, π/2), we have cos(β1 − θt′ ) > 0, and
thus d′1 (θt′ , τ ′ ) < 0 due to − cos(α1 − θs ) = 0. Further, since τ ′ is an infinitesimal small positive value
and − cos(α2 − θs ) < 0, we have d′2 (θt′ , τ ′ ) < 0.
This proves that rs must be in Rπ (s, t).
We proceed to prove the other direction of the lemma. Assume rs is in Rπ (s, t). By the definition
of Rπ (s, t), there exist θt ∈ {0, π} and τ ≥ 0 such that d′1 (θt , τ ) < 0 and d′2 (θt , τ ) < 0. Our goal is to
find another pair (θt′ , τ ′ ) with θt′ ∈ {0, π} and τ ′ ≥ 0 such that d′1 (θt′ , τ ′ ) = 0 and d′2 (θt′ , τ ′ ) < 0.
Recall that cos(β1 − θt ) 6= 0. Depending on whether cos(β1 − θt ) is positive or negative, there are
two cases.
If cos(β1 − θt ) < 0, then cos(β2 − θt ) > 0 because β1 ∈ [0, π/2), β2 ∈ (π/2, π], and θt ∈ {0, π}. Since
τ ≥ 0, if we increase the value τ , d′1 (θt , τ ) will strictly increase and d′1 (θt , τ ) will strictly decrease.
Hence, if we keep increasing τ , there must be a moment when d′1 (θt , τ ) = 0 and d′1 (θt , τ ) < 0. We are
done with the proof.
If cos(β1 − θt ) > 0, then cos(β2 − θt ) < 0. Depending on whether τ = 0, there are two subcases.
– If τ = 0, let θt′ = (θt + π mod 2π) (i.e., we reverse the moving direction of t). Consequently, we
obtain cos(β1 − θt′ ) < 0 and cos(β2 − θt′ ) > 0. Then, we can use the same approach as above, i.e.,
keep increasing τ until d′1 (θt′ , τ ) = 0 and d′1 (θt′ , τ ) < 0.
– If τ > 0, then if we decrease τ , d′1 (θt , τ ) increases and d′2 (θt , τ ) decreases. We keep decreasing the
value τ until one of the two events happens: τ = 0 and d′1 (θt , τ ) = 0.
Whichever event happens first, it always holds that d′2 (θt , τ ) < 0. If d′1 (θt , τ ) = 0 happens first (or
both events happen simultaneously), we are done with the proof. Otherwise, we obtain τ = 0 and
both d′1 (θt , τ ) and d′2 (θt , τ ) are negative. Then, we can use the same approach as the above case
for τ = 0 to prove.
This completes the proof for the lemma.

To simplify the notation, let w1 = −d′u1 ,v1 (s, t) and w2 = −d′u2 ,v2 (s, t). Once rs is fixed (and thus
θs is fixed), both w1 and w2 are implicitly considered as functions of θt ∈ {0, π} and τ ≥ 0. By Lemma
10, Rπ (s, t) consists of all directions rs for s such that there exist θt ∈ {0, π} and τ ≥ 0 with w1 = 0
and w2 > 0.
Let x = α1 − θs . Recall that α = α2 − α1 . Then, α2 − θs = x + α. Thus, we have
(
w1 = cos(x) + τ · cos(β1 − θt ),
w2 = cos(x + α) + τ · cos(β2 − θt ).
19

First of all, let w1 = 0. As shown in the proof of Lemma 10, since β1 ∈ [0, π/2) and θt ∈ {0, π}, it
holds that cos(β1 − θt ) 6= 0. Consequently, we have
τ =−

cos(x)
.
cos(β1 − θt )

Since τ ≥ 0 and β1 ∈ [0, π/2), we obtain the following: if cos(x) > 0, then θt = π; if cos(x) < 0, then
θt = 0; if cos(x) = 0, then θt can be either 0 or π.
cos(x)
By substituting τ with − cos(β
in w2 and using the angle sum identities of trigonometric
1 −θt )
functions, we have
w2 = cos(x + α) + τ · cos(β2 − θt )
cos(x)
· cos(β2 − θt )
cos(β1 − θt )
cos(β2 )
= cos(x) · cos(α) − sin(x) · sin(α) − cos(x) ·
.
cos(β1 )

= cos(x) · cos(α) − sin(x) · sin(α) −

The last equality in the above equation is because regardless of whether θt is 0 or π, it always holds
cos(β2 )
cos(β2 )
2 −θt )
that cos(β
cos(β1 −θt ) = cos(β1 ) . Recall that λ = cos(α) − cos(β1 ) in the statement of Lemma 8. Hence,
w2 = cos(x) · λ − sin(x) · sin(α). Therefore, w2 > 0 is equivalent to cos(x) · λ > sin(x) · sin(α).
The above discussion shows the following observation.
Observation 3 w1 = 0 and w2 > 0 if and only if the following holds:
cos(x) · λ > sin(x) · sin(α).

(4)

Depending on whether sin(α) is positive, negative, or zero, there are three cases.
1. If sin(α) > 0, depending on whether cos(x) is positive, negative, or zero, there are further three
subcases.
(a) If cos(x) > 0, then x ∈ (−π/2, π/2) and Inequality (4) is equivalent to tan(x) <
w1 = 0 and w2 > 0 if and only if x ∈

λ
sin(α) .

Thus,

λ
sin(x) .

Thus,

λ
)).
(−π/2, arctan( sin(α)

(b) If cos(x) < 0, then x ∈ (−3π/2, −π/2) and Inequality (4) is equivalent to tan(x) >
λ
)
(arctan( sin(α)

− π, −π/2).
w1 = 0 and w2 > 0 if and only if x ∈
π
(c) If cos(x) = 0, then x = ± 2 and Inequality (4) is equivalent to sin(x) < 0, which further implies
that x must be −π/2. Thus, w1 = 0 and w2 > 0 if and only if x = −π/2.
Combining the above discussions for the case sin(α) > 0, w1 = 0 and w2 > 0 if and only if
λ
λ
) − π, arctan( sin(α)
)).
x ∈ (arctan( sin(α)
2. If sin(α) < 0, the analysis is symmetric. Depending on whether cos(x) is positive, negative, or zero,
there are further three subcases.
(a) If cos(x) > 0, then x ∈ (−π/2, π/2) and Inequality (4) is equivalent to tan(x) >
w1 = 0 and w2 > 0 if and only if x ∈

λ
sin(α) .

Thus,

λ
sin(x) .

Thus,

λ
), π/2).
(arctan( sin(α)

(b) If cos(x) < 0, then x ∈ (π/2, 3π/2) and Inequality (4) is equivalent to tan(x) <
λ
(π/2, arctan( sin(α)
)+

w1 = 0 and w2 > 0 if and only if x ∈
π).
π
(c) If cos(x) = 0, then x = ± 2 and Inequality (4) is equivalent to sin(x) > 0, which further implies
that x must be π/2. Thus, w1 = 0 and w2 > 0 if and only if x = π/2.
Combining the above discussions for the case sin(α) > 0, w1 = 0 and w2 > 0 if and only if
λ
λ
), arctan( sin(α)
) + π).
x ∈ (arctan( sin(α)
20

3. If sin(α) = 0, then Inequality (4) is equivalent to cos(x)·λ > 0. Depending on whether λ is positive,
negative, or zero, there are further three subcases.
(a) If λ > 0, then Inequality (4) is equivalent to cos(x) > 0, implying that x ∈ (−π/2, π/2).
(b) If λ < 0, then Inequality (4) is equivalent to cos(x) < 0, implying that x ∈ (π/2, 3π/2).
(c) If λ = 0, then Inequality (4) is equivalent to 0 < 0, which is not possible for any x.
λ
)−
As a summary, w1 = 0 and w2 > 0 if and only if: for sin(α) > 0, x ∈ (arctan( sin(α)
λ
λ
λ
)); for sin(α) > 0, x ∈ (arctan( sin(α)
), arctan( sin(α)
) + π); for sin(α) = 0 and λ > 0,
π, arctan( sin(α)
x ∈ (−π/2, π/2); for sin(α) = 0 and λ < 0, x ∈ (π/2, 3π/2); for sin(α) = 0 and λ = 0, x ∈ ∅.
Recall that x = α1 − θs . By Lemma 10, we obtain the π-range Rπ (s, t) as follows.

λ
λ

(α1 − arctan( sin(α) ), α1 − arctan( sin(α) ) + π) if sin(α) > 0,


λ
λ


(α1 − arctan( sin(α) ) − π, α1 − arctan( sin(α) )) if sin(α) < 0,
Rπ (s, t) = (α1 − π/2, α1 + π/2)
if sin(α) = 0 and λ > 0,




(α1 − 3π/2, α1 − π/2)
if sin(α) = 0 and λ < 0,



∅
if sin(α) = 0 and λ = 0.

We complete the proof of Lemma 8 by showing the following claim: α = ±π and β1 + β2 = π if
and only if sin(α) = 0 and λ = 0. We prove the claim below.
cos(β2 )
2)
= −1 − cos(β
Assume α = ±π and β1 + β2 = π. Then, sin(α) = 0, and λ = cos(α) − cos(β
cos(β1 ) . Since
1)
β1 + β2 = π, cos(β1 ) = − cos(β2 ). Hence, λ = 0.
On the other hand, assume sin(α) = 0 and λ = 0. Then, α is 0 or ±π. We claim that α cannot
be zero. Indeed, suppose to the contrary that α = 0. Since β1 ∈ [0, π/2) and β2 ∈ (π/2, π], it always
cos(β2 )
cos(β2 )
2)
holds that cos(β
cos(β1 ) < 0. Hence, λ = cos(α) − cos(β1 ) = 1 − cos(β1 ) , which is always positive, contradicting
with λ = 0.
cos(β2 )
. Due to λ = 0, it holds that
The above proves that α = ±π. Then, we have λ = −1 − cos(β
1)
cos(β2 ) = − cos(β1 ), which implies that β1 + β2 = π since β1 ∈ [0, π/2) and β2 ∈ (π/2, π].
4.4

The Case t ∈ I

The analysis for this case is substantially more difficult than the case t ∈ E. As before, we first present
a more general result that is on three shortest path distance functions.
Let s and t be any two points in P such that t is in I and there are three shortest s-t paths π1 (s, t),
π2 (s, t), and π3 (s, t) (this implies that s is not visible to t). For each i = 1, 2, 3, let πi (s, t) = πui ,vi (s, t),
i.e., ui and vi are the s-pivot and t-pivot of πi (s, t), respectively. We say that the three paths are
canonical with respect to s and t if they have the following two properties.
1. t is in the interior of the triangle △v1 v2 v3 .
2. Suppose we reorder the indices such that v1 , v2 , and v3 are clockwise around t, then u1 , u2 , and
u3 are counterclockwise around s (e.g., see Fig. 2).
The above first property implies that v1 , v2 , and v3 are distinct, but this may not be true for
u1 , u2 , u3 . In the following, we assume that the three shortest paths πi (s, t) with 1 ≤ i ≤ 3 are
canonical, and we reorder the indices such that v1 , v2 , and v3 are clockwise around t and u1 , u2 , and
u3 are counterclockwise around s. For each i = 1, 2, 3, we consider dui ,vi (s, t) = |sui | + d(ui , vi ) + |vi t|
as a function of s ∈ R2 and t ∈ R2 .
In this case, the π-range Rπ (s, t) of s is defined with respect to t and the three paths πi (s, t) for
i = 1, 2, 3 as follows: a direction rs for s is in Rπ (s, t) if there exists a direction rt for t with a speed
τ ≥ 0 such that when we move s along rs with unit speed and move t along rt with speed τ , d′ui ,vi < 0
holds for i = 1, 2, 3.
21

u2

b2
u3

u2 = u3

b3 = 120◦
t
v1

a1 = 100◦
a2
u1
s
a3 = 140◦

v3

v3

b3 = 120◦
t
v1

a1 = 100◦
u1
s
b2

b1 = 90◦
v2

a3 = 260

◦

b1 = 90◦
v2

Fig. 13. Illustrating two concrete examples for Lemma 11. Left: The sizes of the angles of ai and bi for 1 ≤ i ≤ 3 are
2
already shown in the figure with α1 = 0. By calculation, δ ≈ 0.2426, δ1 ≈ −0.1736, δ2 ≈ 0.3072, arctan( δ1 −δ
) ≈ −63.23◦ ,
δ
◦
◦
◦
◦
◦
and thus Rπ (s, t) ≈ (α1 + 63.23 , α1 + 63.23 + 180 ) = (63.23 , 243.23 ). Right: a case where α2 = α3 with α1 = 0. Thus,
a2 = 0 and u2 = u3 . The sizes of other angles are already shown in the figure. By calculation, δ ≈ 2.1220, δ1 ≈ −0.1736,
2
δ2 ≈ −0.3768, arctan( δ1 −δ
) ≈ 5.47◦ , and thus Rπ (s, t) ≈ (α1 − 5.47◦ , α1 − 5.47◦ + 180◦ ) = (−5.47◦ , 174.53◦ ). The open
δ
half-planes that delimit Rπ (s, t) in both examples are marked with red color.

As Lemma 8 in the previous cases, we will have a similar lemma (Lemma 11), which says that
unless a special case happens the range Rπ (s, t) is an open range of size exactly π. The proof is much
more challenging. Before presenting Lemma 11, we introduce some notation.
Recall the definitions of the angles of directions. For each i = 1, 2, 3, let βi denote the angle of the
−
→
−
→
direction tvi (i.e., the angle of tvi counterclockwise from the positive x-axis). Further, we define three
angles bi for i = 1, 2, 3 as follows (e.g., see Fig. 2). Define b1 as the smallest angle we need to rotate
−
→
−
→
−
→
the direction tv1 clockwise to tv2 ; define b2 as the smallest angle we need to rotate the direction tv2
−
→
−
→
−
→
clockwise to tv3 ; define b3 as the smallest angle we need to rotate the direction tv3 clockwise to tv1 .
For any two angles α′ and α′′ , we use α′ ≡ α′′ to denote α′ = α′′ mod 2π.
It is easy to see that b1 ≡ β1 − β2 , b2 ≡ β2 − β3 , and b3 ≡ β3 − β1 . Note that since t is in the
interior of △v1 v2 v3 , it holds that bi ∈ (0, π) for i = 1, 2, 3. Note that b1 + b2 + b3 = 2π.
→. According to our definition of
For each i = 1, 2, 3, let αi denote the angle of the direction −
su
i
pivot vertices, ui = uj if and only if αi = αj for any two i, j ∈ {1, 2, 3}. We define three angles ai for
→
i = 1, 2, 3 as follows (e.g., see Fig. 2). Define a1 as the smallest angle we need to rotate the direction −
su
1
→; define a as the smallest angle we need to rotate the direction −
→ clockwise
counterclockwise to −
su
su
2
2
2
→; define a as the smallest angle we need to rotate the direction −
→ clockwise to −
→. Hence,
to −
su
su
su
3
3
3
1
a1 ≡ α2 − α1 , a2 ≡ α3 − α2 , and a3 ≡ α1 − α3 .
We refer to the case where ai = bi for each i = 1, 2, 3 as the special case.
Lemma 11. The π-range Rπ (s, t) is determined as follows (e.g., see

δ1 −δ2
2

(α1 − arctan( δ1 −δ

δ ), α1 − arctan( δ ) + π)


δ1 −δ2
δ1 −δ2


(α1 − arctan( δ ) − π, α1 − arctan( δ ))
Rπ (s, t) = (α1 − π/2, α1 + π/2)



(α1 − 3π/2, α1 − π/2)




∅

Fig. 13).
if
if
if
if
if

δ
δ
δ
δ
δ

> 0,
< 0,
= 0 and δ1 > δ2 ,
= 0 and δ1 < δ2 ,
= 0 and δ1 = δ2 ,

sin(α2 −α1 )
cos(β2 −β1 )−cos(α2 −α1 )
1 )−cos(α3 −α1 )
3 −α1 )
, and δ2 = cos(β3 −β
. Further,
where δ = sin(α
sin(β3 −β1 ) − sin(β2 −β1 ) , δ1 =
sin(β2 −β1 )
sin(β3 −β1 )
ai = bi for each i = 1, 2, 3 (i.e., the special case) if and only if δ = 0 and δ1 = δ2 .

We defer the proof of Lemma 11 to Section 4.5. According to Lemma 11, if the special case happens,
then Rπ (s, t) is empty; otherwise, it is an open range of size exactly π.
Now we are back to our original problem to determine the range R(s, t) for a non-degenerate
farthest point t ∈ I of s. Since there are exactly three shortest s-t paths πi (s, t) for i = 1, 2, 3, the
three paths must be canonical. To see this, by Observation 1, t is in the interior of △v1 v2 v3 . Further,
22

it is easy to see that no two of the three paths cross each other since otherwise there would be more
than three shortest s-t paths, this implies that the second property of the canonical paths holds. Let
Rπ (s, t) be the π-range of s with respect to t and the above three shortest paths. We have the following
result.
Lemma 12. R(s, t) = Rπ (s, t) ∩ Rf (s).
Proof: For each i = 1, 2, 3, let ui and vi be the s-pivot and t-pivot of the shortest path πi (s, t),
respectively. Since s and t have only three shortest paths, Ut (s) = {v1 , v2 , v3 } and Us (t) = {u1 , u2 , u3 }.
Further, for each i = 1, 2, 3, vi have only one s-pivot, which is ui .
1. Consider any rs ∈ R(s, t). Clearly, rs ∈ Rf (s). By Lemma 4(1), there is a direction rt for t with
a speed τ ≥ 0 such that when s moves along rs with unit speed and t moves along rt with speed
τ , each v ∈ Ut (s) has a coupled s-pivot u with d′u,v (s, t) < 0. Since Ut (s) = {v1 , v2 , v3 } and each vi
has only one s-pivot ui for each 1 ≤ i ≤ 3, we have d′ui ,vi (s, t) < 0 for i = 1, 2, 3. Hence, rs is in
Rπ (s, t).
2. Consider any rs in Rπ (s, t) ∩ Rf (s). First of all, rs is a free direction. Since rs is in Rπ (s, t), there
exists a direction rr for t with a speed τ ≥ 0 such that if s moves along rs for unit speed and t
moves along rt with speed τ , then d′ui ,vi (s, t) < 0 for i = 1, 2, 3. Since Ut (s) = {v1 , v2 , v3 }, according
to Lemma 4(1), rs is in R(s, t).
The lemma thus follows.
4.5



Proof of Lemma 11

Consider any direction rs for moving s and rt for moving t. Let θs denote the angle of the direction rs .
Let θt denote the angle of rt . According to our analysis for Equation (1), we can obtain the derivatives
of the three functions d′ui ,vi (s, t) for i = 1, 2, 3, as follows.

′

du1 ,v1 (s, t) = − cos(α1 − θs ) − τ · cos(β1 − θt ),
d′u2 ,v2 (s, t) = − cos(α2 − θs ) − τ · cos(β2 − θt ),

 ′
du3 ,v3 (s, t) = − cos(α3 − θs ) − τ · cos(β3 − θt ).

(5)

Therefore, for each i = 1, 2, 3, d′ui ,vi (s, t) is a function of θs , θt , and τ . In order to simplify our
proof for Lemma 11, we first give the following lemma.
Lemma 13. A direction rs is in Rπ (s, t) if and only if there exist θt ∈ [0, 2π) and τ ≥ 0 such that
d′u1 ,v1 (s, t) = 0 and d′ui ,vi (s, t) < 0 for i = 2, 3 (the same result holds if we switch the index 1 with 2 or
3).
Proof: In order to make the notation consistent with the rest of Section 4.5, instead of proving the
statement of the lemma, we prove the following statement (which is essentially the same as the lemma):
rs is in Rπ (s, t) if and only if there exist θt and τ ≥ 0 such that d′u2 ,v2 (s, t) = 0 and d′ui ,vi (s, t) < 0 for
i = 1, 3.
Let x = α1 − θs and y = β1 − θt . Hence, we have the following:

′

du1 ,v1 (s, t) = − cos(x) − τ · cos(y),
d′u2 ,v2 (s, t) = − cos(α2 − α1 + x) − τ · cos(β2 − β1 + y),

 ′
du3 ,v3 (s, t) = − cos(α3 − α1 + x) − τ · cos(β3 − β1 + y).
23

q
y
o
lq
Fig. 14. Illustrating the polar coordinate of q with τ = |oq|.

Consider any fixed direction rs . The angle θs is also fixed, and thus x is fixed. Hence, for each
i = 1, 2, 3, d′ui ,vi (s, t) is a function of θt and τ , and thus also a function of y and τ . In the following
proof, we will use d′i (y, τ ) to represent d′ui ,vi (s, t) for each i = 1, 2, 3.
We first prove one direction of the lemma. Suppose rs is in Rπ (s, t). Then there exist y and τ ≥ 0
such that d′i (y, τ ) < 0 for each i = 1, 2, 3. Our goal is to prove that there exit y ′ and τ ′ ≥ 0 such that
d′2 (y ′ , τ ′ ) = 0 and d′i (y ′ , τ ′ ) < 0 for i = 1, 3.
The idea is to change y and τ simultaneously in such a way that d′2 (y, τ ) is constant, but d′1 (y, τ )
strictly increases while d′3 (y, τ ) strictly decreases, and we keep making the change until d′1 (y, τ ) becomes
zero. To this end, we will find a way that when we change τ and y simultaneously, τ ·cos(y) is constant,
−τ · cos(β2 − β1 + y) increases, and −τ · cos(β3 − β1 + y) decreases, as follows.
Since cos(β2 − β1 + y) = cos(β2 − β1 ) · cos(y) − sin(β2 − β1 ) · sin(y), we have
d′2 (y, τ ) = − cos(α2 − α1 + x) − τ · cos(y) · cos(β2 − β1 ) + τ · sin(y) · sin(β2 − β1 ).
Similarly, we derive
d′3 (y, τ ) = − cos(α3 − α1 + x) − τ · cos(y) · cos(β3 − β1 ) + τ · sin(y) · sin(β3 − β1 ).
Consider a point q in a polar coordinate system with coordinate (τ, y), i.e., τ = |oq| and the polar
angle of q is y, where o is the origin (e.g., see Fig. 14). Let lq be the vertical line through q. Note that
if τ = 0, then q = o and lq is the vertical line through o.
For any point p on lq , let τp = |op| and let yp be the polar angle of p. Suppose we move p on lq
from top to bottom, it is easy to see that τp cos(yp ) is constant and τp sin(yp ) is strictly decreasing.
Based on this observation, we will find y ′ and τ ′ ≥ 0 such that d′2 (y ′ , τ ′ ) = 0 and d′i (y ′ , τ ′ ) < 0 for
i = 1, 3, as follows.
Recall that β1 − β2 ≡ b1 and b1 ∈ (0, π). Thus, sin(β2 − β1 ) < 0. Similarly, since β3 − β1 ≡ b3 and
b3 ∈ (0, π), sin(β3 − β1 ) > 0. Hence, if we change the values of y and τ simultaneously such that q
moves along lq downwards, then d′1 (y, τ ) does not change, but d′2 (y, τ ) strictly increases while d′3 (y, τ )
strictly decreases. We keep making the above change until at some moment d′2 (y, τ ) becomes zero, at
which moment we have d′2 (y, τ ) = 0 and d′2 (y, τ ) < 0 for i = 1, 3.
The above proves one direction of the lemma. Next, we prove the other direction.
Suppose there exist y and τ ≥ 0 such that d′2 (y, τ ) = 0 and d′i (y, τ ) < 0 for i = 1, 3. Our goal is to
show that there exist y ′ and τ ′ ≥ 0 such that d′i (y ′ , τ ′ ) < 0 for i = 1, 2, 3.
1. If τ > 0, depending on whether cos(β2 − β1 + y) = 0, there are two subcases.
(a) If cos(β2 − β1 + y) = 0, then it is always possible to change y infinitesimally such that cos(β2 −
β1 + y) > 0. Due to τ > 0, d′2 (y, τ ) < 0. Also, since the change of y is infinitesimal and both
cos(y) and cos(β3 − β1 + y) are continuous functions, we still have d′i (y, τ ) < 0 for i = 2, 3. We
are done with the proof.
(b) If cos(β2 − β1 + y) 6= 0, depending on whether cos(β2 − β1 + y) is positive or negative, we can
infinitesimally increase or decrease τ , such that τ is still positive and d′i (y, τ ) < 0 holds for each
i = 1, 2, 3. We are done with the proof.
24

2. If τ = 0, then again depending on whether cos(β2 − β1 + y) is positive, negative, or zero, there are
three subcases.
(a) If cos(β2 − β1 + y) > 0, then we can increase τ infinitesimally such that τ > 0 and d′i (y, τ ) < 0
for i = 1, 2, 3.
(b) If cos(β2 −β1 +y) < 0, then we first change y to y +π (i.e., the moving direction of t is reversed).
After this, since τ = 0, we still have d′2 (y, τ ) = 0 and d′i (y, τ ) < 0 for i = 1, 3. However, the
difference is that now cos(β2 − β1 + y) > 0 for the new y. Then, we can use the same analysis
as the first subcase.
(c) If cos(β2 − β1 + y) = 0, then we first slightly change y such that cos(β2 − β1 + y) > 0. Since
τ = 0, we still have d′2 (y, τ ) = 0 and d′i (y, τ ) < 0 for i = 1, 3. However, the difference is that
now cos(β2 − β1 + y) > 0 for the new y. Then, we can use the same analysis as the first subcase.
This completes the proof of the lemma.

′
To simplify the notation, let wi = −dui ,vi (s, t) for each i = 1, 2, 3. Let x = α1 − θs and y = β1 − θt .
Then, by Equation (5), we have the following.


w1 = cos(x) + τ · cos(y),
(6)
w2 = cos(α2 − α1 + x) + τ · cos(β2 − β1 + y),


w3 = cos(α3 − α1 + x) + τ · cos(β3 − β1 + y).

Once rs is fixed, both θs and x are fixed. Also, given any θt , we can determine y, and vice versa.
In the following, for each i = 1, 2, 3, we consider wi implicitly as a function of y ∈ [0, 2π) and τ ≥ 0.
By Lemma 13, Rπ (s, t) consists of all directions rs for s such that there exist y and τ ≥ 0 with w1 = 0
and wi > 0 for i = 2, 3.
Let w1 = 0. Then cos(x) + τ · cos(y) = 0. Depending on whether cos(x) is positive, negative, or
zero, there are three cases.
The case cos(x) > 0. In this case, since τ · cos(y) = − cos(x), we have τ · cos(y) < 0 and τ 6= 0.
Since τ ≥ 0, we obtain τ > 0 and cos(y) < 0, implying that y ∈ (π/2, 3π/2). Further, we have
τ = − cos(x)/ cos(y). By replacing τ with − cos(x)/ cos(y) in Equation (6) for w2 , we obtain
w2 = cos(α2 − α1 ) · cos(x) − sin(α2 − α1 ) · sin(x)

cos(x) 
· cos(β2 − β1 ) · cos(y) − sin(β2 − β1 ) · sin(y)
−
cos(y)
= cos(α2 − α1 ) · cos(x) − sin(α2 − α1 ) · sin(x)
− cos(β2 − β1 ) · cos(x) + sin(β2 − β1 ) · tan(y) · cos(x).

Since cos(x) > 0, if we divide the right side of the above formula by cos(x), we obtain that w2 > 0 if
and only if
cos(α2 − α1 ) − sin(α2 − α1 ) · tan(x) − cos(β2 − β1 ) + sin(β2 − β1 ) · tan(y) > 0.
Recall that β1 − β2 ≡ b1 and b1 ∈ (0, π), and thus sin(β2 − β1 ) < 0. Hence, the above inequality is
equivalent to
cos(β2 − β1 ) − cos(α2 − α1 ) + sin(α2 − α1 ) · tan(x)
.
(7)
tan(y) <
sin(β2 − β1 )
Therefore, we obtained that w2 > 0 if and only if Inequality (7) holds.
Similarly, for w3 , we can obtain that w3 > 0 if and only if the following inequality holds:
tan(y) >

cos(β3 − β1 ) − cos(α3 − α1 ) + sin(α3 − α1 ) · tan(x)
.
sin(β3 − β1 )
25

(8)

Note that to obtain Inequality (8), we need to use the fact that sin(β3 − β1 ) > 0, which is due to
β3 − β1 ≡ b3 and b3 ∈ (0, π).
As a summary, the above shows that w1 = 0 and wi > 0 for i = 2, 3 if and only if both Inequalities
(7) and (8) hold. Recall that since cos(x) > 0, y is in (π/2, 3π/2). Further, note that we can find an
angle y ∈ (π/2, 3π/2) such that both (7) and (8) hold if and only if the right side of Inequality (7) is
strictly larger than the right side of Inequality (8). Hence, we obtain the following observation.
Observation 4 For the case cos(x) > 0, there exist y and τ ≥ 0 such that w1 = 0 and wi > 0 for
i = 2, 3 if and only if the right side of Inequality (7) is strictly larger than the right side of Inequality
(8), which is equivalent to the following inequality:
δ · tan(x) < δ1 − δ2 ,

(9)

where δ, δ1 , and δ2 are defined as in the statement of Lemma 11.
Proof: Recall that
δ=
δ1 =

sin(α3 − α1 ) sin(α2 − α1 )
−
,
sin(β3 − β1 )
sin(β2 − β1 )

cos(β3 − β1 ) − cos(α3 − α1 )
cos(β2 − β1 ) − cos(α2 − α1 )
, and δ2 =
.
sin(β2 − β1 )
sin(β3 − β1 )

That the right side of Inequality (7) is larger than the right side of Inequality (8) is equivalent to
the following
cos(β2 − β1 ) − cos(α2 − α1 ) cos(β3 − β1 ) − cos(α3 − α1 )
sin(α3 − α1 ) · tan(x) sin(α2 − α1 ) · tan(x)
−
<
−
,
sin(β3 − β1 )
sin(β2 − β1 )
sin(β2 − β1 )
sin(β3 − β1 )
which is further equivalent to Inequality (9).

Recall that cos(x) > 0. Thus, x ∈ (−π/2, π/2).
2
If δ > 0, Inequality (9) is equivalent to tan(x) < δ1 −δ
δ . Consequently, since x ∈ (−π/2, π/2), we
δ1 −δ2
obtain that x ∈ (−π/2, arctan( δ )).
δ1 −δ2
2
If δ < 0, Inequality (9) is equivalent to tan(x) > δ1 −δ
δ , implying that x ∈ (arctan( δ ), π/2).
If δ = 0, Inequality (9) is equivalent to 0 < δ1 − δ2 . Hence, if δ1 > δ2 , then any x can make the
inequality hold, implying that x ∈ (−π/2, π/2); otherwise, no x can make it hold.
In summary, for the case cos(x) > 0, there exist y and τ ≥ 0 such that w1 = 0 and wi > 0 for
δ1 −δ2
2
i = 2, 3 if and only if: x ∈ (−π/2, arctan( δ1 −δ
δ )) when δ > 0; x ∈ (arctan( δ ), π/2) when δ < 0;
x ∈ (−π/2, π/2) when δ = 0 and δ1 > δ2 .
The case cos(x) < 0. In this case, x ∈ (π/2, 3π/2). The analysis is similar to the above case. We
omit the details and only give the result below.
2
There exist y and τ ≥ 0 such that w1 = 0 and wi > 0 for i = 2, 3 if and only if: x ∈ (arctan( δ1 −δ
δ )+
2
π, 3π/2) when δ > 0; x ∈ (π/2, arctan( δ1 −δ
δ )+π) when δ < 0; x ∈ (π/2, 3π/2) when δ = 0 and δ1 < δ2 .
The case cos(x) = 0. In this case x = ±π/2. The analysis for this case is different from the above
two cases. We will show the following result: There exist y and τ ≥ 0 such that w1 = 0 and wi > 0 for
i = 2, 3 if and only if: x = −π/2 when δ > 0; x = π/2 when δ < 0 (there is no value for x when δ = 0).
By Lemma 13, there exist y and τ ≥ 0 such that w1 = 0 and wi > 0 for i = 2, 3 if and only
there exist y and τ ≥ 0 such that wi > 0 for i = 1, 2, 3. For convenience, in this case, we will find all
directions rs such that there exist y and τ ≥ 0 with wi > 0 for i = 1, 2, 3.
26

Since cos(x) = 0, we have w1 = τ · cos(y). Since we require w1 > 0, τ cannot be 0 and thus τ > 0
w1
must hold. Therefore, we have cos(y) > 0 and y ∈ (−π/2, π/2). In addition, τ = cos(y)
. By replacing
w1
τ with cos(y) and setting cos(x) to 0 in Equation (6) for w2 , we obtain the following
w2 = cos(α2 − α1 ) · cos(x) − sin(α2 − α1 ) · sin(x)


w1
· cos(β2 − β1 ) · cos(y) − sin(β2 − β1 ) · sin(y)
+
cos(y)
= − sin(α2 − α1 ) · sin(x) + cos(β2 − β1 ) · w1 − sin(β2 − β1 ) · tan(y) · w1 .
Hence, w2 > 0 if and only if the following holds
sin(β2 − β1 ) · tan(y) · w1 < − sin(α2 − α1 ) · sin(x) + cos(β2 − β1 ) · w1 .
Recall that since β1 − β2 = b1 and b1 ∈ (0, π), sin(β2 − β1 ) < 0. Since w1 > 0, the above inequality
is equivalent to the following
tan(y) >

− sin(α2 − α1 ) · sin(x) + cos(β2 − β1 ) · w1
sin(β2 − β1 ) · w1

(10)

For w3 , by the similar analysis (we also need to use the fact that sin(β3 − β1 ) > 0), w3 > 0 if and
only if the following holds
tan(y) <

− sin(α3 − α1 ) · sin(x) + cos(β3 − β1 ) · w1
sin(β3 − β1 ) · w1

(11)

Based on the above discussion, wi > 0 for i = 1, 2, 3 if and only if we can find y ∈ (−π/2, π/2) such
that both Inequalities (10) and (11) hold. It is not difficult to see that we can find y ∈ (−π/2, π/2)
such that both Inequalities (10) and (11) hold if and only if the right side of Inequality (10) is strictly
less than the right side of Inequality (11), i.e.,
− sin(α3 − α1 ) · sin(x) + cos(β3 − β1 ) · w1
− sin(α2 − α1 ) · sin(x) + cos(β2 − β1 ) · w1
<
.
sin(β2 − β1 ) · w1
sin(β3 − β1 ) · w1

(12)

Since w1 > 0, we have the following observation.
Observation 5 wi > 0 for i = 1, 2, 3 if and only if there exits w1 > 0 such that
h
i
δ · sin(x) < w1 · cot(β3 − β1 ) − cot(β2 − β1 ) .
Proof: The left side of Inequality (12) is equal to cot(β2 − β1 ) −
is equal to cot(β3 − β1 ) −

sin(α3 −α1 )
sin(β3 −β1 )

·

sin(x)
w1 .

sin(α2 −α1 )
sin(β2 −β1 )

·

sin(x)
w1

and the right side

Hence, Inequality (12) is equivalent to the following

sin(x) h sin(α3 − α1 ) sin(α2 − α1 ) i
< cot(β3 − β1 ) − cot(β2 − β1 ).
·
−
w1
sin(β3 − β1 )
sin(β2 − β1 )
sin(α2 −α1 )
3 −α1 )
Recall that δ = sin(α
sin(β3 −β1 ) − sin(β2 −β1 ) . Since w1 > 0, the observation is obtained.
We also have the following observation.

Lemma 14. It holds that cot(β3 − β1 ) − cot(β2 − β1 ) < 0.
27



Proof: Note that β3 − β1 ≡ b3 and β2 − β1 ≡ b3 + b2 . Hence, to prove the lemma, it is sufficient to
prove cot(b3 ) < cot(b3 + b2 ).
Recall that bi is in (0, π) for each i = 1, 2, 3. Since b1 + b2 + b3 = 2π, it holds that b3 + b2 ∈ (π, 2π).
Note that cot(b3 ) = cot(b3 + π). Due to b3 ∈ (0, π), b3 + π ∈ (π, 2π). Hence, both b3 + b2 and b3 + π
are in (π, 2π). Since b2 ∈ (0, π), b3 + b2 < b3 + π. Because cot(·) is a strictly decreasing function on
(π, 2π), we obtain cot(b3 + b2 ) > cot(b3 + π) = cot(b3 ), which proves the lemma.

Recall that x is either π/2 or −π/2.
In light of Lemma 14, if δ > 0, then there exists w1 > 0 such that the inequality in Observation 5
is satisfied if and only if sin(x) < 0, i.e., x = −π/2. Therefore, if δ > 0, by Observation 5, wi > 0 for
i = 1, 2, 3 if and only if x = −π/2.
Similarly, we can obtain that if δ < 0, then wi > 0 for i = 1, 2, 3 if and only if x = π/2.
If δ = 0, then for any x and any w1 > 0, the inequality in Observation 5 can never be satisfied.
Therefore, for any x, it is not possible to have wi < 0 for all i = 1, 2, 3.
A summary of all three cases. Let R(x) be the set of values for x such that there exist y and
τ ≥ 0 with wi > 0 for i = 1, 2, 3. In other words, since x = α1 − θt , R(s) = {α1 − θt | θt ∈ Rπ (s, t)}. By
our discussions for all three cases cos(x) > 0, cos(x) < 0, and cos(x) = 0, we can obtain the following:
If δ > 0, we have

δ1 −δ2

for cos(x) > 0,
(−π/2, arctan( δ ))
δ1 −δ2
2
R(x) = (arctan( δ1 −δ
δ ) + π, 3π/2) = (arctan( δ ) − π, −π/2) for cos(x) < 0,


{−π/2}
for cos(x) = 0.
Therefore, if δ > 0, R(x) is the union of the above three
2
π, arctan( δ1 −δ
δ )).
Similarly, if δ < 0, we have

δ1 −δ2

for
(arctan( δ ), π/2)
2
R(x) = (π/2, arctan( δ1 −δ
δ ) + π) for


{π/2}
for

2
intervals, which is (arctan( δ1 −δ
δ ) −

cos(x) > 0,
cos(x) < 0,
cos(x) = 0.

δ1 −δ2
2
Therefore, if δ < 0, R(x) = (arctan( δ1 −δ
δ ), arctan( δ ) + π).
Finally, if δ = 0, depending on the values of δ1 and δ2 , there are three
(−π/2, π/2). If δ1 < δ2 , R(x) = (π/2, 3π/2). If δ1 = δ2 , R(x) = ∅.
As a summary, we obtain the following

δ1 −δ2
2

(arctan( δ1 −δ

δ ) − π, arctan( δ )) if δ > 0,


δ1 −δ2
δ1 −δ2


(arctan( δ ), arctan( δ ) + π) if δ < 0,
R(x) = (−π/2, π/2)
if δ = 0 and



(π/2, 3π/2)
if δ = 0 and




∅
if δ = 0 and

cases. If δ1 > δ2 , R(x) =

δ1 > δ2 ,
δ1 < δ2 ,
δ1 = δ2 ,

Since R(s) = {α1 − θt | θt ∈ Rπ (s, t)}, we obtain the range Rπ (s, t) for θs as follows.

δ1 −δ2
2

(α1 − arctan( δ1 −δ

δ ), α1 − arctan( δ ) + π) if δ > 0,


δ1 −δ2
δ1 −δ2


(α1 − arctan( δ ) − π, α1 − arctan( δ )) if δ < 0,
Rπ (s, t) = (α1 − π/2, α1 + π/2)
if δ = 0 and δ1 > δ2 ,


(α1 − 3π/2, α1 − π/2)
if δ = 0 and δ1 < δ2 ,




∅
if δ = 0 and δ1 = δ2 ,
28

To prove Lemma 11, it remains to show that δ = 0 and δ1 = δ2 if and only if ai = bi for each
i = 1, 2, 3. To this end, we first give the following lemma.
Lemma 15. If δ = 0 and δ1 = δ2 , then δ1 = δ2 = 0.
Proof: Recall that

sin(α3 − α1 ) sin(α2 − α1 )
−
,
sin(β3 − β1 )
sin(β2 − β1 )
cos(β2 − β1 ) − cos(α2 − α1 )
cos(β3 − β1 ) − cos(α3 − α1 )
δ1 =
, and δ2 =
.
sin(β2 − β1 )
sin(β3 − β1 )
δ=

For the purpose of differentiation, we use δ(1, 2, 3), δ1 (1, 2, 3), and δ2 (1, 2, 3) to represent the above
δ, δ1 , and δ2 , respectively. We use (1, 2, 3) because our previous discussion considered d′ui ,vi (s, t) in the
order of 1, 2, 3.
Suppose δ(1, 2, 3) = 0 and δ1 (1, 2, 3) = δ2 (1, 2, 3). In the following, we give an “indirect” approach
to prove δ1 (1, 2, 3) = δ2 (1, 2, 3) = 0.
Our previous discussion has proved that Rπ (s, t) = ∅ if and only δ(1, 2, 3) = 0 and δ1 (1, 2, 3) =
δ2 (1, 2, 3). In other words, there is no value for θs such that there exist θt and τ ≥ 0 with wi > 0 for
i = 1, 2, 3 if and only if δ(1, 2, 3) = 0 and δ1 (1, 2, 3) = δ2 (1, 2, 3).
Our previous analysis considered the three functions wi in the order of 1, 2, 3. If we consider them
in the order of 2, 3, 1, by using the same analysis, we can obtain that Rπ (s, t) = ∅ if and only if
δ(2, 3, 1) = 0 and δ1 (2, 3, 1) = δ2 (2, 3, 1), where
δ(2, 3, 1) =

sin(α1 − α2 ) sin(α3 − α2 )
−
,
sin(β1 − β2 )
sin(β3 − β2 )

cos(β3 − β2 ) − cos(α3 − α2 )
cos(β1 − β2 ) − cos(α1 − α2 )
, and δ2 (2, 3, 1) =
.
sin(β3 − β2 )
sin(β1 − β2 )
Another way to think about this is that we can replace 1, 2, 3 by 2, 3, 1, respectively, in δ(1, 2, 3),
δ1 (1, 2, 3), and δ2 (1, 2, 3). The main reason why the same analysis as before still works is that if we
follow the order of 2, 3, 1, the vertices of u2 , u3 , u1 are still in the counterclockwise order around s and
the vertices of v2 , v3 , v1 are still in the clockwise order around t. We omit the detailed analysis.
Similarly, if we consider the three functions wi in the order of 3, 1, 2, by using the same analysis,
we can obtain that Rπ (s, t) = ∅ if and only if δ(3, 1, 2) = 0 and δ2 (3, 1, 2) = δ3 (3, 1, 2), where
δ1 (2, 3, 1) =

δ(3, 1, 2) =

sin(α2 − α3 ) sin(α1 − α3 )
−
,
sin(β2 − β3 )
sin(β1 − β3 )

cos(β2 − β3 ) − cos(α2 − α3 )
cos(β1 − β3 ) − cos(α1 − α3 )
, and δ2 (3, 1, 2) =
.
sin(β1 − β3 )
sin(β2 − β3 )
Recall that δ(1, 2, 3) = 0 and δ1 (1, 2, 3) = δ2 (1, 2, 3). Thus, Rπ (s, t) = ∅. According to the above
discussion, δ(2, 3, 1) = 0 and δ1 (2, 3, 1) = δ2 (2, 3, 1), and δ(3, 1, 2) = 0 and δ2 (3, 1, 2) = δ3 (3, 1, 2). In the
following, we show that δ1 (1, 2, 3) = δ2 (1, 2, 3) = δ1 (2, 3, 1) = δ2 (2, 3, 1) = δ2 (3, 1, 2) = δ3 (3, 1, 2) = 0,
which will prove the lemma.
First of all, δ2 (1, 2, 3) = −δ1 (3, 1, 2) holds because cos(β3 − β1 ) = cos(β1 − β3 ), cos(α3 − α1 ) =
cos(α1 − α3 ), and sin(β3 − β1 ) = − sin(β1 − β3 ).
Similarly, we can obtain δ1 (2, 3, 1) = −δ2 (3, 1, 2) and δ1 (1, 2, 3) = −δ2 (2, 3, 1).
Due to δ2 (1, 2, 3) = −δ1 (3, 1, 2) and δ1 (2, 3, 1) = −δ2 (3, 1, 2), we derive δ1 (1, 2, 3) = δ2 (1, 2, 3) =
−δ1 (3, 1, 2) = −δ2 (3, 1, 2) = δ1 (2, 3, 1) = δ2 (2, 3, 1). In particular, we have δ1 (1, 2, 3) = δ2 (2, 3, 1).
The above has obtained that both δ1 (1, 2, 3) = −δ2 (2, 3, 1) and δ1 (1, 2, 3) = δ2 (2, 3, 1) hold, implying that δ1 (1, 2, 3) = δ2 (2, 3, 1) = 0. Consequently, δ1 (1, 2, 3) = δ2 (1, 2, 3) = δ1 (2, 3, 1) = δ2 (2, 3, 1) =
δ2 (3, 1, 2) = δ3 (3, 1, 2) = 0.
The lemma thus follows.

δ1 (3, 1, 2) =

29

Lemma 16. δ = 0 and δ1 = δ2 if and only if ai = bi for each i = 1, 2, 3.
Proof: Recall that a1 ≡ α2 − α1 , a2 ≡ α3 − α2 , a3 ≡ α1 − α3 , b1 ≡ β1 − β2 , b2 ≡ β2 − β3 , and
b3 ≡ β3 − β1 . We first prove one direction of the lemma. Suppose ai = bi for each i = 1, 2, 3. Then,
δ=

− sin(a3 )
sin(a1 )
sin(α3 − α1 ) sin(α2 − α1 )
−
=
−
= 0.
sin(β3 − β1 )
sin(β2 − β1 )
sin(b3 )
− sin(b1 )

Also, we have cos(β2 − β1 ) = cos(b1 ) and cos(α2 − α1 ) = cos(a1 ). Since a1 = b1 , we obtain δ1 = 0.
Similarly, we have cos(β3 − β1 ) = cos(b3 ) and cos(α3 − α1 ) = cos(a3 ). Since a3 = b3 , we obtain δ2 = 0.
This proves that δ = 0 and δ1 = δ2 .
Next we prove the other direction of the lemma. Suppose δ = 0 and δ1 = δ2 . In the following we
prove ai = bi for i = 1, 2, 3. By Lemma 15, we know that δ1 = δ2 = 0.
Since δ1 = 0, it holds that cos(β2 − β1 ) = cos(α2 − α1 ), i.e., cos(b1 ) = cos(a1 ).
Similarly, since δ2 = 0, it holds that cos(β3 − β1 ) = cos(α3 − α1 ), i.e., cos(b3 ) = cos(a3 ).
sin(a1 )
3)
On the other hand, δ = 0 implies that sin(a
sin(b3 ) = sin(b1 ) .
Note that b1 + b2 + b3 = 2π. Recall that two or even all three of u1 , u2 , u3 may be the same.
According to our definitions of the three angles a1 , a2 , a3 , if u1 = u2 = u3 , then a1 = a2 = a3 = 0;
otherwise, a1 + a2 + a3 = 2π although one of the three angles may still be zero. In either case, it holds
that a1 + a2 + a3 ≤ 2π.
In the sequel, we first prove a1 = b1 and a3 = b3 .
Note that bi ∈ (0, π) for each i = 1, 2, 3, and ai ∈ [0, 2π) for each i = 1, 2, 3.
Assume to the contrary that b1 6= a1 and b3 6= a3 . Due to cos(b1 ) = cos(a1 ), it must be that
a1 = 2π − b1 . Since b1 ∈ (0, π), we obtain a1 ∈ (π, 2π). Similarly, due to cos(b3 ) = cos(a3 ), it must be
that a3 = 2π − b3 . Since b3 ∈ (0, π), we obtain a3 ∈ (π, 2π). This yields that a1 + a3 > 2π, contradicting
with a1 + a2 + a3 ≤ 2π.
Therefore, at least one of b1 6= a1 and b3 6= a3 must be true. Without loss of generality, we assume
b1 = a 1 .
sin(a1 )
3)
Since sin(a
sin(b3 ) = sin(b1 ) and b1 = a1 , it is obviously true that sin(a3 ) = sin(b3 ). Recall that we
already have cos(a3 ) = cos(b3 ). Therefore, it must hold that a3 = b3 mod 2π. Since ai ∈ [0, 2π) and
b3 ∈ (0, π), we obtain that a3 = b3 .
This proves that a1 = b1 and a3 = b3 . Since neither b1 nor b3 is zero, we obtain a1 6= 0 and a3 6= 0,
and thus a1 + a2 + a3 = 2π. This implies that a2 = b2 since b1 + b2 + b3 = 2π. The lemma thus follows.


5

Computing the Candidate Points

In this section, with the help of the observations in Sections 3 and 4, we compute a set S of candidate
points such that all geodesic centers must be in S.
Let s be any geodesic center. Recall that F (s) is the set of all farthest points of s. Depending on
whether s is in V, E, or I, the size |F (s)|, whether some points of F (s) are in V, E, or I, whether s
has a degenerate farthest point, there are a significant (but still constant) number of cases. For each
case, our algorithm uses an exhaustive-search approach to compute a set of candidate points such
that s must be in the set. In particular, there are four cases, called dominating cases, for which the
number of candidate points is O(n11 ). But the total number of the candidate points for all other cases
is only O(n10 ). Therefore, the set S has a total of O(n11 ) candidate points. We will show that S can
be computed in O(n11 log n) time.
To find the geodesic centers in S, a straightforward algorithm works as follows. For each point
ŝ ∈ S, we can compute dmax (ŝ) in O(n log n) time by first computing the shortest path map SPM (ŝ)
of ŝ in O(n log n) time [12] and then obtaining the maximum geodesic distance from ŝ to all vertices
30

of SPM (ŝ). Since all geodesic centers are in S, the points of S with the smallest dmax (ŝ) are geodesic
centers of P.
Since |S| = O(n11 ), the above algorithm runs in O(n12 log n) time. Let Sd denote the set of the
candidate points for the four dominating cases. Clearly, the bottleneck is on finding the geodesic centers
from Sd . To improve the algorithm, when we compute the candidate points of Sd , we will maintain
the corresponding path information. By using these path information and based on new observations,
we will present in Section 6 an O(n11 log n) time “pruning algorithm” that can eliminate most of
the points from Sd such that none of the eliminated points is a geodesic center and the number of
remaining points in Sd is only O(n10 ). Consequently, we can use the above straightforward algorithm
to find all geodesic centers in O(n11 log n) time.
In the rest of this section, we focus on computing the set S. Our algorithm for finding the geodesic
centers from S (in particular, the pruning algorithm) will be given in Section 6.
In the following, we adopt the follow convention on notation: s represents a true geodesic center
and ŝ represents a corresponding candidate point.
First of all, for the case s ∈ V, we consider all polygon vertices of V as candidate points. In the
following, we only consider the case s ∈ E or s ∈ I. If s has a degenerate farthest point, we refer to
it as the degenerate case; otherwise it is a non-degenerate or general case. We will compute candidate
points for the general case and the degenerate case in Sections 5.2 and 5.3, respectively. The four
dominating cases are all general cases. We begin with computing the candidate points for a special
case in Section 5.1.
5.1

A Special Case

Consider a non-degenerate farthest point t of s such that t is in E or I. If t is in E, then there are
exactly two shortest s-t paths; we say that t is a special farthest point of s if the π-range Rπ (s, t) of
s with respect to t and the two shortest paths is ∅ (i.e., the special case in Lemma 8). Similarly, if t
is in I, then there are exactly three shortest s-t paths; we say that t is a special farthest point of s if
the π-range Rπ (s, t) of s with respect to t and the three shortest paths is ∅ (i.e., the special case in
Lemma 11).
If s has a special farthest point, we refer to it as the special case. Let s be any geodesic center in
the special case. In this subsection, we will compute a set S1 of O(n5 ) candidate points in O(n5 log n)
time for the special case, such that s must be in S1 .
Let t be a special farthest point of s. By the above definition, t is in E or I. We discuss the two
cases below.
The case t ∈ E. Let e be the polygon edge that contains t. Let π1 (s, t) and π2 (s, t) be the two
shortest s-t paths. For each i = 1, 2, let ui and vi be the s-pivot and t-pivot of πi (s, t), respectively
(i.e., πi (s, t) = πui ,vi (s, t)). Then, we have |su1 | + d(u1 , v1 ) + |v1 t| = |su2 | + d(u2 , v2 ) + |v2 t|. We define
the angles α1 , α2 , β1 , β2 in the same way as those for Lemma 8 in Section 4.2. Since Rπ (s, t) = ∅, by
Lemma 8, β1 + β2 = π and α2 − α1 = ±π.
Note that α2 − α1 = ±π implies that s is on the line segment u1 u2 . β1 + β2 = π implies that lt
bisects the angle ∠v1 tv2 , where lt is the line through t and perpendicular to e.
In summary, s and t satisfy the following “constraints”: (1) t ∈ e; (2) |su1 | + d(u1 , v1 ) + |v1 t| =
|su2 | + d(u2 , v2 ) + |v2 t|; (3) s ∈ u1 u2 ; (4) lt bisects the angle ∠v1 tv2 .
If we consider the coordinates of s and t as four variables, the above four (independent) constraints
can determine s and t. An easy observation is that s must be in a bisector edge of two cells of SPM (t)
whose roots are u1 and u2 , respectively (in fact s is the intersection of the bisector edge and u1 u2 ).
Correspondingly, we compute the candidate points in an exhaustive way as follows.
We enumerate all possible combinations of a polygon edge as e and two polygon vertices as v1 and
v2 . For each combination, we find a point t on e such that the above condition (4) can be satisfied.
31

Next we compute the shortest path map SPM (t) of t. For each bisector edge of SPM (t), we consider it
as e and let u1 and u2 be the roots of the two cells of SPM (t) incident to e; we report the intersection
e ∩ u1 u2 (if any) as a candidate point ŝ. In this way, we can compute at most O(n) candidate points
on SPM (t) since the combinatorial complexity of SPM (t) is O(n). Thus, for each combination of e, v1 ,
and v2 , we can compute O(n) candidate points. Since there are O(n3 ) combinations, we can compute
O(n4 ) candidate points and we add these points to S1 . By our above discussions, the geodesic center
s must be in S1 .
Since computing a shortest path map takes O(n log n) time [12], the running time of the above
algorithm is bounded by O(n4 log n).
The case t ∈ I. In this case, there are exactly three shortest s-t paths: πi (s, t) = πui ,vi (s, t) with
i = 1, 2, 3. Then we have |su1 | + d(u1 , v1 ) + |v1 t| = |su2 | + d(u2 , v2 ) + |v2 t| = |su3 | + d(u3 , v3 ) + |v3 t|.
We define the angles ai , bi , for i = 1, 2, 3, in the same way as those for Lemma 11 in Section 4.4. By
Lemma 11, ai = bi for i = 1, 2, 3.
If we consider the coordinates of s and t as four variables, the above equation on the lengths of
the three shortest paths provide two constraints and the identities of the three pairs of angles provide
other two (independent) constraints, and thus the total four (independent) constraints can determine
s and t. Correspondingly, we compute the candidate points for s as follows.
We enumerate all possible combinations of three polygon vertices as v1 , v2 , v3 . We compute the
shortest path maps of v1 , v2 , and v3 in O(n log n) time. Next we compute the overlay of the three
shortest path maps. The overlay is of size O(n2 ) and can compute in O(n2 log n) time [3,7]. Then,
for each cell of the overlay, we obtain the three roots of the cell in the three shortest path maps
and consider them as u1 , u2 , u2 . Finally, we use the above four constraints to determine a constant
number of pairs (ŝ, t) (we assume this can be done in constant time since the angles ai and bi can be
parameterized by the coordinates of ŝ and t), and we add each ŝ to S1 as a candidate point. In this
way, for each combination of v1 , v2 , v3 , we can compute O(n2 ) candidate points in O(n2 log n) time.
Since there are O(n3 ) combinations, we can compute O(n5 ) candidate points in O(n5 log n) time.
5.2

The General Case

Recall that in the general case s does not have a degenerate farthest point. Depending on whether s
is in I or in E, there are two main cases. We first consider the case s ∈ I.
The case s ∈ I. Depending on whether |F (s)| is 1, 2, or at least 3, there are further three cases.
The case |F (s)| = 1. If |F (s)| = 1, let t be the only farthest point of s. Thus, R(s) = R(s, t). By
Lemma 1, R(s) = ∅. Hence, R(s, t) = ∅. Since s ∈ I, by our observations in Section 4 (in particular,
Lemmas 6, 7, 8, 9, 11, 12), t is either in E or I, and in either case Rπ (s, t) = ∅ since s ∈ I and Rf (s)
consists of all directions. Hence, t must be a special farthest point of s, which implies that s has been
computed in the candidate point set S1 .
The case |F (s)| = 2. If |F (s)| = 2, we assume that F (s) does not have any special farthest points
since otherwise s would have already been computed in S1 . Let F (s) = {t1 , t2 }. Depending on whether
each of t1 and t2 is in V, E, or I, there are several cases. In the following, we use (x, y, z) to refer to
the case where x, y, z points of F (s) are in I, E, and V, respectively, with x + y + z = 2. For example,
(1, 1, 0) refers to the case where one point of F (x) is in I and the other is in E.
1. Case (2, 0, 0). We first consider the most general case where ti ∈ I for i = 1, 2. Other cases are
very similar. For each i = 1, 2, since ti ∈ I, ti has three shortest paths to s: πuij ,vij (s, ti ) with
32

j = 1, 2, 3. Hence, we have the following
|t1 v11 | + d(v11 , u11 ) + |u11 s| = |t1 v12 | + d(v12 , u12 ) + |u12 s| = |t1 v13 | + d(v13 , u13 ) + |u13 s|
=|t2 v21 | + d(v21 , u21 ) + |u21 s| = |t2 v22 | + d(v22 , u22 ) + |u22 s| = |t2 v23 | + d(v23 , u23 ) + |u23 s|.
Further, since s has only two farthest points and s ∈ I, it must hold that R(s) = Rπ (s, t1 ) ∩
Rπ (s, t2 ) = ∅ by Lemma 1. Recall that we have assumed that F (s) does not have any special
farthest points. Therefore, neither Rπ (s, t1 ) nor Rπ (s, t2 ) is ∅. By Lemma 11, each of Rπ (s, t1 ) and
Rπ (s, t2 ) is an open range of size π. For each i = 1, 2, the directions of Rπ (s, ti ) are delimited by an
open half-plane whose bounding line contains s, and we refer to the bounding line as the bounding
line of the range Rπ (s, ti ). Since Rπ (s, t1 ) ∩ Rπ (s, t2 ) = ∅, we can obtain that the bounding line of
Rπ (s, t1 ) is the same as that of Rπ (s, t2 ).
If we consider the coordinates of s, t1 , and t2 as six variables, the above system of equations on the
distances of the six shortest paths provide five constraints and that the bounding lines of the two
π-ranges overlap provides another constraint (note that the bounding lines of the two π-range can
be parameterized by the coordinates of s, t1 , and t2 ). Hence, the six (independent) constraints can
determine the triple (s, t1 , t2 ). Correspondingly, our algorithm for computing the candidate points
works as follows.
We enumerate all possible combinations of six polygon vertices as vij for i = 1, 2 and j = 1, 2, 3.
We compute overlay of the shortest path maps of the six vertices. For each cell of the overlay, we
obtain the six roots in the six shortest path maps as uij for i = 1, 2 and j = 1, 2, 3. Using the six
constraints as discussed above, we can obtain a constant number of triples (ŝ, t1 , t2 ), and each such
ŝ is a candidate point.
In this way, for each combination, we can compute O(n2 ) candidate points in O(n2 log n) time.
Since there are O(n6 ) combinations, we can compute O(n8 ) candidate points in overall O(n8 log n)
time. As analyzed above, s must be one of these candidate points.
2. Case (1, 1, 0). In this case, one of t1 and t2 is in I and the other is in E. Without loss of generality,
we assume t1 ∈ I and t2 ∈ E. Hence, t1 has three shortest paths to s: πu1j ,v1j (s, t1 ) for j = 1, 2, 3,
and t2 has two shortest paths to s: πu2j ,v2j (s, t2 ) for j = 1, 2. Hence, we have the following
|t1 v11 | + d(v11 , u11 ) + |u11 s| = |t1 v12 | + d(v12 , u12 ) + |u12 s| = |t1 v13 | + d(v13 , u13 ) + |u13 s|
=|t2 v21 | + d(v21 , u21 ) + |u21 s| = |t2 v22 | + d(v22 , u22 ) + |u22 s|.
As in the previous case, Rπ (s, t1 )∩ Rπ (s, t2 ) = ∅ and each of the two π-ranges is nonempty; further,
and the two bounding lines of these two π-ranges must overlap.
Let e be the polygon edge that contains t.
The above equations provide four constraints and the overlap of the two bounding lines of the
two π-ranges provides another constraint. In addition, t2 ∈ e gives the sixth constraint. As in the
previous case, the six constraints can determine s, t1 , and t2 if we consider their coordinates as six
variables. Correspondingly, we compute candidate points as follows.
We enumerate all possible combinations of a polygon edge as e and five polygon vertices as
v11 , v12 , v13 , v21 , v22 . We compute the overlay of the shortest path maps of the five vertices. For each
cell of the overlay, we obtain the five roots in the five shortest path maps as u11 , u12 , u13 , u21 , u22 .
Then we obtain the equations as above. Along with the constraint that t2 ∈ e and the constraint
that the two bounding lines of the π-ranges Rπ (ŝ, t1 ) and Rπ (ŝ, t2 ) overlap, we can obtain a constant
number of triples (ŝ, t1 , t2 ), and each such ŝ is a candidate point. In this way, for each combination,
we can compute O(n2 ) candidate points in O(n2 log n) time. Since there are O(n8 ) combinations,
we can compute O(n8 ) candidate points for s in O(n8 log n) time.
3. Other Cases. The other cases are all very similar (i.e., (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2)), and we
can compute a total of O(n8 ) candidate points in O(n8 log n) time. We omit the details.
As a summary, for the case |F (s)| = 2, we can compute at most O(n8 ) candidate centers in
O(n8 log n) time.
33

The case |F (s)| ≥ 3. In this case, the geodesic center s has at least three farthest points. We assume
s does not have any special farthest points since otherwise s would have already been computed in
S1 . Hence, for each t ∈ F (s), the π-range Rπ (s, t) is not empty and thus is an open range of size π.
Together with Lemma 1, this further implies that s must have three farthest points t1 , t2 , t3 such that
Rπ (s, t1 ) ∩ Rπ (s, t2 ) ∩ Rπ (s, t3 ) = ∅. Depending on whether each of ti for i = 1, 2, 3 is in I, E, V, there
are several cases. Similarly, we use (x, y, z) to refer to the case where x, y, and z points of t1 , t2 , t3 are
in I, E, and V, respectively, with x + y + z = 3.
We begin our discussion with the most general case (3, 0, 0), where t1 , t2 , t3 are all in I. This is
one of the four dominating cases and we will need to compute O(n11 ) candidate points. Further, our
algorithm is slightly different from the previous cases in the following sense: First, in addition to the
candidate points, we will also maintain the corresponding path information; second, when computing
the candidate points, we will have a “validation procedure”. Recall that Sd is the set of candidate
points for all four dominating cases. The path information will be used in the next section to quickly
prune most of the points in Sd and the validation procedure can be considered as a “preliminary
pruning step”. The details are given below.
For each i = 1, 2, 3, since ti is in I, there are exactly three shortest paths from s to ti : πuij ,vij (s, t)
with j = 1, 2, 3. Hence, we have the following
|t1 v11 | + d(v11 , u11 ) + |u11 s| = |t1 v12 | + d(v12 , u12 ) + |u12 s| = |t1 v13 | + d(v13 , u13 ) + |u13 s|
=|t2 v21 | + d(v21 , u21 ) + |u21 s| = |t2 v22 | + d(v22 , u22 ) + |u22 s| = |t2 v23 | + d(v23 , u23 ) + |u23 s|
=|t3 v31 | + d(v31 , u31 ) + |u31 s| = |t3 v32 | + d(v32 , u32 ) + |u32 s| = |t3 v33 | + d(v33 , u33 ) + |u33 s|.
If we consider the coordinates of s, t1 , t2 , and t3 as eight variables, the above equations on the
lengths of nine paths provide eight constraints, which are sufficient to determine all four points.
Correspondingly, we compute the candidate points as follows.
We enumerate all possible combinations of nine polygon vertices as vi1 , vi2 , vi3 , with i = 1, 2, 3. For
each combination, we compute the overlay of the shortest path maps of these nine vertices. The size of
the overlay is O(n2 ). For each cell C of the overlay, we obtain nine roots of the shortest path maps and
consider them as ui1 , ui2 , ui3 for i = 1, 2, 3. We form the above system of eight equations and solve it to
obtain a constant number of quadruples of points (ŝ, t̂1 , t̂2 , t̂3 ). We also obtain a path length, denoted
by d(ŝ), which is equal to the value in the above equations, e.g., d(ŝ) = |ŝu11 | + d(u11 , v11 ) + |v11 t̂1 |.
In addition, we perform a validation procedure on each such quadruple (ŝ, t̂1 , t̂2 , t̂3 ) as follows.
First, we check whether ŝ is in C, which can be done in O(log n) time by using a point location
data structure [9,14] with O(n2 ) time and space preprocessing on the overlay. If yes, for each ti with
i = 1, 2, 3, we check whether d(ŝ) is equal to d(ŝ, t̂i ), which can be computed in O(log n) time by using
the two-point shortest path query data structure given by Chiang and Mitchell [7] with O(n11 ) time
and space preprocessing on P. If yes, we check whether vi1 , vi2 , vi3 satisfy the condition in Observation
1(1), i.e., whether t̂i is in the interior of the triangle △vi1 vi2 vi3 for each i = 1, 2, 3. If yes, for each t̂i
with i = 1, 2, 3, we check whether the order of the vertices of vi1 , vi2 , vi3 around t̂i are consistent with
the order of the vertices of ui1 , ui2 , ui3 (we say that the two orders are consistent if after reordering
the indices, vi1 , vi2 , vi3 are clockwise around t̂i while ui1 , ui2 , ui3 are counterclockwise around s; note
that this consistency is needed for determining the π-range in Lemma 11). If yes, for each t̂i with
i = 1, 2, 3, we compute the π-range Rπ (s, t̂i ) determined by Lemma 11, and then check whether
Rπ (ŝ, t̂1 ) ∩ Rπ (ŝ, t̂2 ) ∩ Rπ (ŝ, t̂3 ) is empty. If yes, we say that the quadruple (ŝ, t̂1 , t̂2 , t̂3 ) passes the
validation procedure and we call ŝ a valid candidate point and add ŝ to the set Sd . In addition, we
maintain the following path information: d(ŝ), t̂i , vij , and uij , with 1 ≤ i ≤ 3 and 1 ≤ j ≤ 3. In
fact, only d(ŝ) will be used later in the algorithm and all other information are only for the reference
purpose in the analysis.
34

In this way, for each combination of nine polygon vertices, we can compute O(n2 ) valid candidate
for Sd in O(n2 log n) time (not including the preprocessing time). Since there are O(n9 ) combinations,
we can compute a total of O(n11 ) valid candidate points for Sd in O(n11 log n) time.
Note that the geodesic center s and the quadruple (s, t1 , t2 , t3 ) discussed above must pass the
validation procedure, and thus the quadruple (s, t1 , t2 , t3 ) will be computed by our exhaustive-search
algorithm and s will be computed as a valid candidate point in Sd .
Based on our validation procedure, the following observation summarizes the properties of the valid
candidate points. These properties will be used to prove the correctness of our pruning algorithm in
Section 6.
Observation 6 Suppose (ŝ, t̂1 , t̂2 , t̂3 ) is a quadruple that passes the validation procedure, with uij and
vij , i = 1, 2, 3 and j = 1, 2, 3 defined as above. Then the following hold.
1. For each i = 1, 2, 3, ŝuij ∪ π(uij , vij ) ∪ vij t̂i is a shortest path from ŝ to t̂i for each j = 1, 2, 3.
2. For each i = 1, 2, 3, vi1 , vi2 , vi3 satisfy the condition of Observation 1(1), i.e., t̂i is in the interior
of the triangle △vi1 vi2 vi3 .
3. d(ŝ) = d(ŝ, t̂i ) for each i = 1, 2, 3.
4. Rπ (ŝ, t̂1 ) ∩ Rπ (ŝ, t̂2 ) ∩ Rπ (ŝ, t̂1 ) = ∅.
The above computes the candidate points for the case (3, 0, 0). In the following, we compute
candidate points for other cases. The algorithms are similar.
1. Case (2, 1, 0). In this case, two of t1 , t2 , t3 are in I and the third one is in E. Without loss of
generality, we assume t1 and t2 are in I and t3 is in E. Let e be the polygon edge containing t3 .
This is the second dominating case. We will also perform a validation procedure and maintain the
corresponding path information.
For each i = 1, 2, since ti is in I, there are three shortest paths from s to ti : πuij ,vij (s, t) for
j = 1, 2, 3. Since t3 ∈ E, there are two shortest paths from s to t3 : πu3j ,v3j (s, t) for j = 1, 2. Hence,
we have the following
|t1 v11 | + d(v11 , u11 ) + |u11 s| = |t1 v12 | + d(v12 , u12 ) + |u12 s| = |t1 v13 | + d(v13 , u13 ) + |u13 s|
=|t2 v21 | + d(v21 , u21 ) + |u21 s| = |t2 v22 | + d(v22 , u22 ) + |u22 s| = |t2 v23 | + d(v23 , u23 ) + |u23 s|
=|t3 v31 | + d(v31 , u31 ) + |u31 s| = |t3 v32 | + d(v32 , u32 ) + |u32 s|.
If we consider the coordinates of s, t1 , t2 , t3 as eight variables, the above equations give seven
constraints. With the additional constraint that t3 is on e, we can determine (s, t1 , t2 , t3 ). Correspondingly, we compute the candidate points as follows.
We enumerate all combinations of eight polygon vertices (as v11 , v12 , v13 , v21 , v22 , v23 , v31 , v32 ) and
one polygon edge (as e). For each combination, we can compute O(n2 ) quadruples (ŝ, t̂1 , t̂2 , t̂3 ). For
each such quadruple, we also perform the validation procedure similarly as before with the following
differences. For t̂3 , since there is no vertex v33 , we ignore all operations that involve v33 . Further,
we check whether {v11 , v12 } satisfy the condition in Observation 1(2) (instead of Observation 1(1)).
We determine the range Rπ (s, t3 ) by using Lemma 8 (instead of Lemma 11).
In this way, we can compute at most O(n11 ) valid candidate points in O(n11 log n) time and
add them to Sd , and also, we maintain the corresponding path information similarly as before.
Observation 6 still holds correspondingly with the following difference: in (1) there are only two
shortest paths for t̂3 ; in (2) for t̂3 , {v11 , v12 } satisfy the condition of Observation 1(2).
2. Cases (1, 2, 0) and (0, 3, 0). These are the other two dominating cases. We can compute O(n11 )
valid candidate points in O(n11 log n) time. The algorithms are very similar to the previous two
cases. For each case, we also need a validation procedure and keep the path information. We omit
the details.
35

We have discussed all four dominating cases. Note that the candidate points for all four dominating
cases are in I. The rest of the cases are not dominating cases. For each of the remaining cases, the
validation procedure and the path information will not be needed any more.
3. Other cases. Our algorithms for all other cases (e.g. (2, 0, 1), (1, 1, 1), (1, 0, 2), (0, 2, 1), (0, 1, 2),
(0, 0, 3)) are very similar as before (except that the validation procedure and the path information
are not needed). We can compute a total of O(n10 ) candidate points in O(n10 log n) time. We omit
the details.
As a summary for the case s ∈ I, for the four dominating cases, we have computed O(n11 ) valid
candidate points in O(n11 log n) time with the corresponding path information. For all other cases, we
have computed O(n10 ) candidate points.
The case s ∈ E. Our algorithm for computing candidate points for this case is slightly different.
Consider a geodesic center s in E. Let es denote the polygon edge that contains s. Depending on
whether |F (s)| is 1 or not, there are two cases.
The case |F (s)| = 1. If |F (s)| = 1, let t be the only farthest point of s. We assume that t is not a
special farthest point of s since otherwise s would have already been computed in S1 in Section 5.1.
Thus, by Lemma 8, the π-range Rπ (s, t) is an open range of size π. Since t is the only farthest point
of s, by Lemma 1, R(s) = R(s, t) = ∅. By Lemma 9, R(s, t) = ∅ implies that the bounding line of
the range Rπ (s, t) contains es , and this provides a constraint for determining s and t. Depending on
whether t is in I, E, or V, there are three cases.
1. The case t ∈ I. We first consider the most general case in which t ∈ I. There are three shortest
s-t paths: πui vi (s, t) for i = 1, 2, 3. Thus, we have the following
|tv1 | + d(v1 , u1 ) + |u1 s| = |tv2 | + d(v2 , u2 ) + |u2 s| = |tv3 | + d(v3 , u3 ) + |u3 s|.
If we consider the coordinates of s and t as four variables, then the above equations provide two
constraints and s ∈ es gives another constraint. In addition, that the bounding line of the range
Rπ (s, t) contains es provides the fourth constraint. Hence, the four constraints can determine s
and t. Correspondingly, we compute the candidate points as follows.
We enumerate all possible combinations of three polygon vertices as v1 , v2 , v3 . For each combination, we compute the overlay of the shortest path maps of v1 , v2 , and v3 . For each cell C of the
overlay, if it contains a portion of a polygon edge, we consider the edge as es and obtain three
roots of the shortest path maps as u1 , u2 , and u3 . Using the four constraints discussed above, we
can obtain a constant number of tuples (ŝ, t) and each such ŝ is a candidate point. In this way, we
can compute O(n5 ) candidate points in O(n5 log n) time.
2. The case t ∈ E. Let et be the polygon edge that contains t. There are two shortest s-t paths, which
gives one constraint for determining s and t. s ∈ es and t ∈ et provide two constraints. Finally,
that the bounding line of the range Rπ (s, t) contains es gives the fourth constraint. Hence, we still
have four constraints to determine s and t.
The algorithm is similar to the previous case. We can compute O(n5 ) candidate points in O(n5 log n)
time. We omit the details.
3. The case t ∈ V. In this case, t is a polygon vertex, which provides two constraints (or t is fixed
already). s ∈ es is another constraint. As before, that the bounding line of the range Rπ (s, t)
contains es provides the fourth constraint. We compute the candidate points as follows.
We enumerate all polygon vertices. For each vertex, we consider it as t and compute the shortest
path map SPM (t). For each cell C of SPM (t), if it contains a portion of polygon edge on its
boundary, then we consider that edge as es . Next, we find a candidate point ŝ on that portion of
es in C such that the π-range Rπ (ŝ, t) (determined by Lemma 8) has its bounding line contain es .
In this way, we can compute O(n2 ) candidate points in O(n2 log n) time.
36

In summary, for the case |F (s)| = 1, we compute O(n5 ) candidate points in O(n5 log n) time.
The case |F (s)| ≥ 2. Let t1 and t2 be the two farthest points of s. We assume s does not have
any special farthest points since otherwise s would have already been computed in S1 . Then, neither
Rπ (s, t1 ) nor Rπ (s, t2 ) is empty. Depending on whether each of t1 and t2 is in I, E, or V, there are
several cases.
We first consider the most general case where both t1 and t2 are in I. Other cases are very similar.
For each i = 1, 2, since ti ∈ I, there are three shortest paths from s to ti : πuij ,vij (s, t) with j = 1, 2, 3.
Hence, we have the following
|t1 v11 | + d(v11 , u11 ) + |u11 s| = |t1 v12 | + d(v12 , u12 ) + |u12 s| = |t1 v13 | + d(v13 , u13 ) + |u13 s|
=|t2 v21 | + d(v21 , u21 ) + |u21 s| = |t2 v22 | + d(v22 , u22 ) + |u22 s| = |t2 v23 | + d(v23 , u23 ) + |u23 s|.
The above equations provide five constraints for s and t. With the constraint that s ∈ es , we can
determine s, t1 , and t2 , if we consider their coordinates as six variables. Correspondingly, we compute
the candidate points as follows.
We enumerate all possible combinations of six polygon vertices as v11 , v12 , v13 , v21 , v22 , v23 . For each
combination, we compute the overlay of the shortest path maps of the six vertices. For each cell C of
the overlay, if C contains a portion of a polygon edge, then we consider the edge as es and using the
six constraints mentioned above to compute at most a constant number of triples (ŝ, t1 , t2 ). Hence, for
each combination, we can compute at most O(n2 ) candidate points in O(n2 log n) time. In this way,
we can compute O(n8 ) candidate points in O(n8 log n) time.
Candidate points for other cases can be computed similarly. We can compute O(n8 ) candidate
points in O(n8 log n) time. We omit the details.
As a summary for the case s ∈ E, we can compute a total of O(n8 ) candidate points in O(n8 log n)
time.
5.3

The Degenerate Case

In the degenerate case, the geodesic center s has at least one degenerate farthest point. Depending on
whether s is in I or E, there are two main cases.
The Case s ∈ I. Depending on whether |F (s)| is 1 or not, there are further two cases.
The case |F (s)| = 1. Let t be the only point of F (s). Then t is a degenerate farthest point of s.
Depending on whether t is in V, E, or I, there are three cases.
1. If t ∈ V, then since t is degenerate, there are at least two shortest s-t paths. Further, since t is
polygon vertex and due to our general position assumption that no two polygon vertices have more
than one shortest path, it holds that |Us (t)| ≥ 2.
If |Us (t)| ≥ 3, then s is a vertex of SPM (t). Correspondingly, we can compute candidate points as
follows. For each polygon vertex, we consider it as t and compute its shortest path map SPM (t).
Then, we report each vertex of SPM (t) as a candidate points. In this way, we can compute O(n2 )
candidate points for s in O(n2 log n) time.
If |Us (t)| = 2, let Us (t) = {u1 , u2 }. We first prove a claim: s ∈ u1 u2 .
Indeed, suppose to the contrary that the claim is not true. Then, su1 and su2 form an angle
∠u1 su2 ∈ (0, π). Consider the direction rs for moving s along the bisector of ∠v1 sv2 and towards
the interior of ∠v1 sv2 . If we move s along rs with unit speed, since ∠u1 su2 is strictly less than π
and Us (t) = {u1 , u2 }, each vertex v ∈ Ut (s) has a coupled s-pivot u ∈ Us (t) with d′u,v (s, t) < 0.
Since s ∈ I, rs is a free direction. By Lemma 4, rs is an admissible direction of s with respect
37

to t, i.e., rs ∈ R(s, t). Since R(s) = R(s, t), we obtain that R(s) is not empty, contradicting with
Lemma 1. The claim thus follows.
s ∈ u1 u2 provides a constraint for determining s (if we consider t ∈ V as fixed at a polygon vertex).
Further, there are two shortest s-t paths πui vi (s, t) with i = 1, 2. Hence, s must be in the bisector
edge that is incident to the two cells whose roots are u1 and u2 , respectively, in the shortest path
map SPM (t). Correspondingly, we compute the candidate points as follows.
We enumerate all polygon vertices. For each polygon vertex, we consider it as t and compute
SPM (t). For each bisector edge of SPM (t), we obtain the roots of the two cells incident to the
bisector edge as u1 and u2 . Then, we compute a candidate point ŝ on the bisector edge such that
ŝ ∈ u1 u2 (i.e., ŝ is the intersection of u1 u2 and the bisector edge). In this way, we can compute
O(n2 ) candidate points in O(n2 log n) time.
2. If t ∈ E, then since t is degenerate, there are at least three shortest s-t paths. Let et be the polygon
edge that contains t. Since t is a farthest point of s, t must have two vertices v1 and v2 that satisfy
the condition in Observation 1. Hence, there are two shortest s-t paths πui ,vi (s, t) for i = 1, 2.
Since s ∈ I, we claim that the π-range Rπ (s, t) with respect to the two shortest paths πui ,vi (s, t)
for i = 1, 2 must be empty. Assume to the contrary that this is not true. Then, by Lemma 5(2),
R(s, t) is not empty (in fact, Rπ (s, t) ⊆ R(s, t)). Since t is the only farthest point of s, we obtain
that R(s) = R(s, t) 6= ∅, which contradicts with Lemma 1.
Since Rπ (s, t) = ∅, one can check that s has already been computed in S1 in Section 5.1 (for the
case t ∈ E).
3. If t ∈ I, since t is degenerate, there are at most four shortest s-t paths. By Observation 1,
|Ut (s)| ≥ 3. Depending on whether |Ut (s)| = 3, there are two cases.
We first discuss the case where |Ut (s)| = 3. Let v1 , v2 , v3 be the three vertices in Ut (s). By Observation 1, t is in the interior of the triangle △v1 v2 v3 . Then, there must exist three shortest s-t
paths πui ,vi (s, t) such that no two paths cross each other, and this implies that the three paths
are canonical. Let Rπ (s, t) denote the π-range of s with respect to t and the above three shortest
paths.
If Rπ (s, t) = ∅, then one can check that s has already been computed in S1 in Section 5.1. Otherwise,
as the above second case, since s ∈ I and F (s) = {t}, by Lemma 5(1) any direction in Rπ (s, t) is
in R(s, t), implying that R(s) = R(s, t) 6= ∅, which contradicts with Lemma 1.
Next we discuss the case where |Ut (s)| > 3.
By Observation 1, t is in the interior of the convex hull of all vertices of Ut (s). If there exist
three vertices v1 , v2 , v3 of Ut (s) such that t is in the interior of △v1 v2 v3 , then we can still use
the same approach as the above case for |Ut (s)| = 3. Otherwise, there must exist four vertices
v1 , v2 , v3 , v4 ∈ Ut (s) such that t is the intersection of the two line segments v1 v2 and v3 v4 .
On the other hand, since s ∈ I and t is the only farthest point of s, we claim that |Us (t)| ≥ 2.
Indeed, suppose to the contrary that |Us (t)| = 1. Then, if we move s towards the only vertex u of
Us (t) with unit speed, then for each vertex v ∈ Ut (s), d′u,v (s, t) < 0 holds. Hence, by Lemma 2(1),
the above direction for s is in R(s, t), implying that R(s) = R(s, t) 6= ∅, which contradicts with
Lemma 1. Therefore, the claim follows.
Depending on whether |Us (t)| ≥ 3, there are two cases.
(a) If |Us (t)| ≥ 3, then s is a vertex of the shortest path map SPM (t). Correspondingly, we compute
the candidate points as follows.
We enumerate all possible combinations of four polygon vertices as vi for 1 ≤ i ≤ 4. For each
such combination, we compute the intersection of v1 v2 and v3 v4 and consider the intersection as
t. Then we compute SPM (t) and return all vertices of SPM (t) as candidate points. In this way,
for each combination, we can compute at most O(n) candidate points in O(n log n) time. Since
there are O(n4 ) combinations, we can compute a total of O(n5 ) candidate points in O(n5 log n)
time.
38

(b) If |Us (t)| = 2, let Us (t) = {u1 , u2 }. An easy observation is that s must be on the bisector edge
of u1 and u2 in SPM (t). Further, by the same analysis as before, we can show that s must be
on u1 u2 . Correspondingly, we can compute the candidate points as follows.
We enumerate all possible combinations of four polygon vertices as vi for 1 ≤ i ≤ 4. For each
such combination, we compute the intersection of v1 v2 and v3 v4 and consider the intersection
as t. Then, we compute SPM (t). For each bisector edge of SPM (t), we obtain the roots of the
two cells incident to the bisector edge as u1 and u2 , respectively. Then, we find the intersection
of u1 u2 and the bisector edge as a candidate point. Since there are O(n) bisector edges, we can
find O(n) candidate points. In this way, we can compute O(n5 ) candidate points in O(n5 log n)
time.
This finishes the case for |F (s)| = 1.
The case |F (s)| ≥ 2. Recall that s has at least one degenerate farthest point. Let t1 and t2 be any two
points of F (s) such that t1 is degenerate.
We first consider the most general case where both t1 and t2 are in I. For each i = 1, 2, ti has at
least three shortest paths from s and |Uti (s)| ≥ 3. Since t1 is degenerate, t1 has at least four shortest
paths from s. Depending on whether |Ut1 (s)| = 3, there are two cases.
If |Ut1 (s)| > 3, let v1j for 1 ≤ j ≤ 4 be any four vertices of Ut1 (s). Hence, there are four shortest
paths from s to t1 : πu1j ,v1j (s, t1 ) with 1 ≤ j ≤ 4. For t2 , let v2j for 1 ≤ j ≤ 3 be any three vertices
of Ut2 (s), and there are three shortest paths from s to t2 : πu2j ,v2j (s, t2 ) with 1 ≤ j ≤ 3. We can form
a system of equations with the lengths of the above seven shortest paths, which give six constraints
to determine (s, t1 , t2 ). Correspondingly, we can compute O(n9 ) candidate points in O(n9 log n) time.
The algorithm is similar to the previous algorithms and we omit the details.
If |Ut1 (s)| = 3, let v1j for 1 ≤ j ≤ 3 be the three vertices of Ut1 (s). Since there are at least four
shortest paths from s to t1 and due to our general position assumption that no two polygon vertices
have more than one shortest path, there exists a vertex, say v11 , in Ut1 (s) such that there are at
least two shortest paths from s to v11 . Hence, s must be on a bisector edge of the shortest path map
SPM (v11 ).
Let πu1j ,v1j (s, t1 ) for j = 1, 2, 3 be three shortest paths from s to t1 . Let πu2j ,v2j (s, t2 ) for j = 1, 2, 3
be three shortest paths from s to t2 . We can form a system of equations with the lengths of the six
paths. These equations can give five constraints, and along with that s is on a bisector edge of SPM (t1 ),
we can determine (s, t1 , t2 ) (equivalently, one may also consider that the seven shortest paths give six
constraints). Correspondingly, we compute the candidate points as follows.
We enumerate all possible combinations of six polygon vertices as vij for i = 1, 2 and j = 1, 2, 3.
For each combination, we compute the overlay of the shortest path maps of these vertices. For each
cell of the overlay, if its boundary has a portion of a bisector edge of SPM (v11 ), then based on the
above system of equations on the lengths of the six paths, we determine a constant number of triples
(ŝ, t1 , t2 ) and each such ŝ is a candidate point. Since the size of the overlay is O(n2 ), we can determine
O(n2 ) candidate points for each combination. Since there are O(n6 ) combinations, we can compute
O(n8 ) candidate points in O(n8 log n) time.
The above computes O(n9 ) candidate points for the case where both t1 and t2 are in I.
Other cases are very similar. For example, consider the case where t1 ∈ I and t2 is on a polygonal
edge e ∈ E. Comparing with the previous case, since t2 is in E, there will be one less constraint on the
equations of shortest path lengths, but t2 ∈ e gives one more constraint. All other cases are similar.
We can compute at most O(n9 ) candidate points in O(n9 log n) for all other cases. The details are
omitted.
This finishes the case for |F (s)| ≥ 2 and thus the case for s ∈ I.
The Case s ∈ E. Let es be the polygon edge that contains s. Let t be a degenerate farthest point
of s. Depending on whether t is in V, E, or I, there are three cases.
39

1. If t ∈ V, then there are at least two shortest s-t paths. Further, since t is a polygon vertex, due
to our general position assumption that any two polygon vertices have no more than one shortest
path, Us (t) has at least two vertices. This implies that s is in a bisector edge of SPM (t). Further,
as s is on es , s is at the intersection of a bisector edge of SPM (t) and es . Correspondingly, we
compute the candidate points as follows.
We consider all polygon vertices. For each vertex, we consider it as t and compute SPM (t). For
each bisector edge, if it intersects a polygon edge, we compute the intersection as a candidate point.
In this way, we can compute O(n2 ) candidate points in O(n2 log n) time.
2. If t ∈ E, let et be the polygon edge that contains t. Since t ∈ E and t is degenerate, there are at
least three shortest paths from s to t. Since t ∈ et , Ut (s) must have two vertices v1 and v2 that
satisfy the condition of Observation 1(2). Hence, |Ut (s)| ≥ 2. Depending on whether |Ut (s)| ≥ 3,
there are two cases.
(a) If |Ut (s)| ≥ 3, let vi with i = 1, 2, 3 be any three vertices of Ut (s). Then, there are three shortest
s-t paths πui ,vi (s, t) for i = 1, 2, 3. We have the following
|tv1 | + d(v1 , u1 ) + |u1 s| = |tv2 | + d(v2 , u2 ) + |u2 s| = |tv3 | + d(v3 , u3 ) + |u3 s|.
The above equations provide two constraints, and along with the constraints that s ∈ es and
t ∈ et , the four constraints can determine s and t. Correspondingly, we compute the candidate
points as follows.
We enumerate all possible combinations of three vertices as vi for i = 1, 2, 3 and a polygon edge
as et . For each combination, we compute the overlay of the shortest path maps of v1 , v2 , and
v3 . For each cell C of the overlay, if it has an edge that is a portion of a polygon edge, then we
consider the polygon edge as es and obtain the three roots of the three shortest path maps as ui
for i = 1, 2, 3. Next, using the four constraints mentioned above, we can determine a constant
number of tuples (ŝ, t) and each such ŝ is a candidate point. Since the size of the overlay is
O(n2 ), for each combination we can obtain O(n2 ) candidate points in O(n2 log n) time. Since
there are O(n4 ) combinations, we can compute O(n6 ) candidate points in O(n6 log n) time.
(b) If |Ut (s)| = 2, let v1 and v2 be the two vertices of Ut (s). Since there are at least three shortest
s-t paths and due to our general position assumption that no two polygon vertices have more
than one shortest path, one of v1 and v2 , say v1 , must have at least two shortest paths to s such
that |Us (v1 )| ≥ 2. Hence, s is on a bisector edge of SPM (v1 ). Since s ∈ es , s is the intersection
of es and a bisector edge of SPM (v1 ). Correspondingly, we can compute the candidate points
as follows.
We enumerate all polygon vertices. For each vertex, we consider it as v1 and compute its
shortest path map SPM (v1 ). Then, for each intersection between a bisector edge of SPM (v1 )
and a polygon edge, we consider it as a candidate point. Since the size of SPM (v1 ) is O(n),
there are O(n) such candidate points. In this way, we can compute at most O(n2 ) candidate
points in O(n2 log n) time.
3. If t ∈ I, then there are at least four shortest s-t paths, and |Ut (s)| ≥ 3 by Observation 1. Depending
on whether |Ut (s)| ≥ 4, there two cases.
(a) If |Ut (s)| ≥ 4, then let vi with 1 ≤ i ≤ 4 be any four vertices of Ut (s). Then, there are four
shortest s-t paths πui ,vi (s, t) for 1 ≤ i ≤ 4. We have the following
|tv1 | + d(v1 , u1 ) + |u1 s| = |tv2 | + d(v2 , u2 ) + |u2 s|
= |tv3 | + d(v3 , u3 ) + |u3 s| = |tv4 | + d(v4 , u4 ) + |u4 s|.
The above equations provide three constraints, and along with the constraints that s ∈ es ,
the four constraints can determine s and t. Correspondingly, we can compute O(n6 ) candidate
points in O(n6 log n) time. The algorithm is similar as before and we omit the details.
40

(b) If |Ut (s)| = 3, let vi with i = 1, 2, 3 be the three vertices of Ut (s). Since there are at least four
shortest s-t paths and due to our general position assumption that no two polygon vertices
have more than one shortest path, one of vi with i = 1, 2, 3, say v1 , must have at least two
shortest paths to s such that |Us (v1 )| ≥ 2. Hence, s is on a bisector edge of SPM (v1 ). Since
s ∈ es , s is the intersection of es and a bisector edge of SPM (v1 ). Correspondingly, by using the
same approach as the above case 2(b), we can compute O(n2 ) candidate points in O(n2 log n)
time.
This finishes the case for s ∈ E.
This also finishes our algorithms for computing candidate points for the degenerate case. In summary, we can compute a total of O(n9 ) candidate points in O(n9 log n) time such that s is one of these
candidate points.

6

Computing the Geodesic Centers

In this section, we find all geodesic centers from the candidate point set S. Let S ′ denote the set of
candidate points for all cases other than the four dominating cases. Recall that Sd is the set of candidate
points for the four dominating cases. Hence, S = S ′ ∪ Sd . As discussed in Section 5, |S ′ | = O(n10 ) and
we can find all geodesic centers in S ′ in O(n11 log n) time by computing their shortest path maps. In
the following, we focus on finding all geodesic centers in Sd .
We first remove all points from Sd that are also in S ′ , which can be done in O(n11 log n) time (e.g.,
by first sorting these points by their coordinates). Then, for any point s ∈ Sd , if s is a geodesic center,
s does not have any degenerate farthest point since otherwise s was also in S ′ and thus would have
already been removed from Sd .
Recall that each point s of Sd is a valid candidate point and we have maintained its path information
for s (in particular, the value d(s)).
We first perform the following duplication-cleanup procedure: for each point s ∈ Sd , if there are
many copies of s, we only keep the one with the largest value d(s) (if more than one copy has the
largest value, we keep an arbitrary one). This procedure can be done in O(n11 log n) time (e.g., by first
sorting all points of Sd by their coordinates). According to our algorithm for computing the candidate
points of Sd , we have the following observation.
Observation 7 After the duplication-cleanup procedure, for any point s ∈ Sd , if s is a geodesic center,
then dmax (s) = d(s).
Proof: For differentiation, we use Sd to denote the original set of Sd before the duplication-cleanup
procedure and use Sd′ to denote the set after the procedure. Note that Sd and Sd′ contain the same
physical points and the difference is that for each point of Sd′ , Sd may contain multiple copies of the
point, and each copy is associated with different path information. Recall that none of the point of Sd
is in S ′ .
Consider any point s ∈ Sd′ and suppose s is a geodesic center. According to our algorithm for
computing candidate points of Sd , there must be a copy of s in Sd for which we have maintained its
path information that includes a farthest point t of s and d(s) = d(s, t) by Observation 6. Since t is
a farthest point of s, d(s, t) = dmax (s). Therefore, there exists a copy of s in Sd with d(s) = dmax (s).
Let s′ denote any other copy of s in Sd . Again, by Observation 6, d(s′ ) is equal to the shortest path
distance from s′ to a point t′ . Hence, d(s′ ) ≤ dmax (s′ ) = dmax (s) = d(s).
According to our duplication-cleanup procedure, if d(s′ ) < d(s), then the copy s′ will be removed
from Sd′ . Otherwise, either copy may be removed, but in either case, the d(·) value of the remaining
copy is always equal to dmax (s). Hence, the observation follows.

Recall that all points of Sd are in I.
41

In the following, we give a pruning algorithm that can eliminate most of the points from Sd such
that none of these eliminated points is a geodesic center and the number of remaining points of Sd
is O(n10 ). Our pruning algorithm relies on the property that each candidate point s of Sd is valid.
Specifically, if s is computed for the dominating case (3, 0, 0), then s is associated with the following
path information d(s), ti , vij , and uij for 1 ≤ i ≤ 3 and 1 ≤ j ≤ 3, such that Observation 6 holds (i.e.,
s is ŝ and each ti is t̂i ). For other three dominating cases (e.g., (2, 1, 0), (1, 2, 0), and (0, 3, 0)), there
are similar properties. By using these properties, we have the following lemma.
Lemma 17. Let s be any point in Sd . If s is in the interior of a cell or an edge of Dspm, then for any
other point s′ in the interior of the same cell or edge of Dspm , it holds that dmax (s′ ) > d(s).
Proof: The proof uses similar techniques as that for Lemma 3. We only prove the case for s being a
candidate point for Case (3, 0, 0), and other cases are similar.
Recall that s is associated with the following path information d(s), ti , vij , and uij for 1 ≤ i ≤ 3
and 1 ≤ j ≤ 3, such that Observation 6 holds.
If s′ be any other point in the same cell or edge of Dspm that contains s. Hence, SPM (s) and
SPM (s′ ) are topologically equivalent. Consider any ti with 1 ≤ i ≤ 3. By Observation 6, for each
j = 1, 2, 3, πuij ,vij (s, t) is a shortest paths from s to ti . Since SPM (s) and SPM (s′ ) are topologically
equivalent, SPM (s′ ) has one and only one vertex t′i corresponding to ti and for each j = 1, 2, 3,
πuij ,vij (s′ , t′i ) is a shortest path from s′ to t′i .
Let r be the direction from s to s′ . By Observation 6, Rπ (s, t1 )∩Rπ (s, t2 )∩Rπ (s, t3 ) = ∅. Therefore,
r is not in Rπ (s, ti ) for some i with 1 ≤ i ≤ 3. Without loss of generality, we assume r is not in Rπ (s, t1 ).
Suppose we move s along the direction r with unit speed and move t1 to t′1 with speed |t1 t′1 |/|ss′ |.
Hence, when s arrives at s′ , t1 arrives at t′1 simultaneously. Since r is not in Rπ (s, t1 ), there must be a
path πu1j ,v1j (s, t1 ) for some j with 1 ≤ j ≤ 3 such that d′u1j ,v1j (s, t1 ) < 0 does not hold. Without loss
of generality, we assume j = 1. In other words, either d′u11 ,v11 (s, t1 ) > 0 or d′u11 ,v11 (s, t1 ) = 0.
1. If d′u11 ,v11 (s, t1 ) > 0, then since d′′u11 ,v11 (s, t1 ) ≥ 0 always holds, we have du11 ,v11 (s, t1 ) < du11 ,v11 (s′ , t′1 ).
Since d(s) = du11 ,v11 (s, t1 ) and dmax (s′ ) ≥ d(s′ , t′1 ) = du11 ,v11 (s′ , t′1 ), we obtain that dmax (s′ ) > d(s),
which proves the lemma.
2. If d′u11 ,v11 (s, t1 ) = 0, recall that d′′u11 ,v11 (s, t1 ) ≥ 0 always holds. If d′′u11 ,v11 (s, t1 ) > 0, then we again
obtain du11 ,v11 (s, t1 ) < du11 ,v11 (s′ , t′1 ), and consequently, dmax (s′ ) > d(s).
Otherwise, d′′u11 ,v11 (s, t1 ) = 0. We claim that this case cannot happen. Indeed, suppose to the contrary that d′′u11 ,v11 (s, t1 ) = 0. Then, we have du11 ,v11 (s, t1 ) = du11 ,v11 (s′ , t′1 ). Since πu1j ,v1j (s′ , t′1 ) for
j = 2, 3 is also a shortest path from s to t′1 , we have du11 ,v11 (s′ , t′1 ) = du12 ,v12 (s′ , t′1 ) = du13 ,v13 (s′ , t′1 ),
and thus, du12 ,v12 (s, t1 ) = du12 ,v12 (s′ , t′1 ) and du13 ,v13 (s, t1 ) = du13 ,v13 (s′ , t′1 ). This is only possible if
d′u1j ,v1j (s, t1 ) = 0 and d′′u1j ,v1j (s, t1 ) = 0 for both j = 2, 3. However, by Observation 6, t1 is in the
interior of the triangle △v11 v12 v13 ; as discussed earlier (i.e., the discussions for Fig. 6), this implies
that it is not possible to have d′u1j ,v1j (s, t1 ) = 0 and d′′u1j ,v1j (s, t1 ) = 0 for all j = 1, 2, 3, incurring
contradiction.
This completes the proof of the lemma.



Lemma 18. For any two points s1 and s2 of Sd that are in the interior of the same cell or the same
edge of Dspm , if d(s1 ) < d(s2 ), then s1 cannot be a geodesic center, and if d(s1 ) = d(s2 ), then neither
s1 nor s2 is a geodesic center.
Proof: Consider any two points s1 and s2 of Sd that are in the interior of the same cell or the same
edge of Dspm. By Lemma 17, dmax (s1 ) > d(s2 ) and dmax (s2 ) > d(s1 ).
If d(s1 ) < d(s2 ), then we obtain dmax (s1 ) > d(s2 ) > d(s1 ). Thus, s1 cannot be a geodesic center
since otherwise d(s1 ) would be equal to dmax (s1 ) by Observation 7.
42

Similarly, if d(s1 ) = d(s2 ), then we have both dmax (s1 ) > d(s2 ) = d(s1 ) and dmax (s2 ) > d(s1 ) =
d(s2 ). Thus, neither s1 nor s2 is a geodesic center.

Based on Lemma 18, our pruning algorithm for Sd works as follows. For each point s of Sd , we
determine the cell, edge, or vertex of Dspm that contains s in its interior, which can be done in O(log n)
time by using a point location data structure [9,14] with O(n10 ) time and space preprocessing on Dspm .
For each edge or cell, let Sd′ be the set of points of Sd that are contained in its interior. We find the
point s of Sd′ with the largest value d(s). If there are more than one such point in Sd′ , we remove all
points of Sd′ from Sd ; otherwise, remove all points of Sd′ except s from Sd . By Lemma 18, none of
the points of Sd that are removed above is a geodesic center. After the above pruning algorithm, Sd
contains at most one point in the interior of each cell, edge, or vertex of Dspm . Hence, |Sd | = O(|Dspm |).
Since |Dspm | = O(n10 ) [7], we obtain |Sd | = O(n10 ).
Theorem 1. All geodesic centers of P can be computed in O(n11 log n) time.

Acknowledgment
The author wishes to thank Yan Sun for the discussions on proving the π-range property.

References
1. H.-K. Ahn, L. Barba, P. Bose, J.-L. De Carufel, M. Korman, and E. Oh. A linear-time algorithm for the geodesic
center of a simple polygon. In Proc. of the 31st Annual Symposium on Computational Geometry (SoCG), pages
209–223, 2015.
2. T. Asano and G. Toussaint. Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32,
McGill University, Montreal, Canada, 1985.
3. S.W. Bae, M. Korman, and Y. Okamoto. The geodesic diameter of polygonal domains. Discrete and Computational
Geometry, 50:306–329, 2013.
4. S.W. Bae, M. Korman, and Y. Okamoto. Computing the geodesic centers of a polygonal domain. In Proc. of the 26th
Canadian Conference on Computational Geometry (CCCG), 2014. Journal version published online in Computational
Geometry: Theory and Applications, 2015.
5. S.W. Bae, M. Korman, Y. Okamoto, and H. Wang. Computing the L1 geodesic diameter and center of a simple
polygon in linear time. Computational Geometry: Theory and Applications, 48:495–505, 2015.
6. B. Chazelle. A theorem on polygon cutting with applications. In Proc. of the 23rd Annual Symposium on Foundations
of Computer Science, pages 339–349, 1982.
7. Y.-J. Chiang and J.S.B. Mitchell. Two-point Euclidean shortest path queries in the plane. In Proc. of the Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 215–224, 1999.
8. H.N. Djidjev, A. Lingas, and J.-R. Sack. An O(n log n) algorithm for computing the link center of a simple polygon.
Discrete and Computational Geometry, 8:131–152, 1992.
9. H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on
Computing, 15(2):317–340, 1986.
10. D. Halperin and M. Sharir. New bounds for lower envelopes in three dimensions, with applications to visibility in
terrains. Discrete and Computational Geometry, 12:313–326, 1994.
11. J. Hershberger and S. Suri. Matrix searching with the shortest-path metric. SIAM Journal on Computing, 26(6):1612–
1634, 1997.
12. J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on
Computing, 28(6):2215–2256, 1999.
13. Y. Ke. An efficient algorithm for link-distance problems. In Proc. of the 5th Annual Symposium on Computational
Geometry, pages 69–78, 1989.
14. D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28–35, 1983.
15. J.S.B. Mitchell. Geometric shortest paths and network optimization, in Handbook of Computational Geometry, J.-R
Sack and J. Urrutia (eds.), pages 633–702. Elsevier, Amsterdam, the Netherlands, 2000.
16. B.J. Nilsson and S. Schuierer. Computing the rectilinear link diameter of a polygon. In Proc. of the International
Workshop on Computational Geometry - Methods, Algorithms and Applications, pages 203–215, 1991.
17. B.J. Nilsson and S. Schuierer. An optimal algorithm for the rectilinear link center of a rectilinear polygon. Computational Geometry, 6:169–194, 1996.
18. R. Pollack, M. Sharir, and G. Rote. Computing the geodesic center of a simple polygon. Discrete and Computational
Geometry, 4(1):611–626, 1989.

43

19. S. Schuierer. An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon. International Journal of Compututational Geometry and Applications, 6:205–226, 1996.
20. S. Suri. Computing geodesic furthest neighbors in simple polygons. Journal of Computer and System Sciences,
39:220–235, 1989.

44

