# The Visibility Center of a Simple Polygon

Anna Lubiw and Anurag Murty Naredla

###### Abstract

We introduce the _visibility center_ of a set of points inside a polygon—a
point $c_{V}$ such that the maximum geodesic distance from $c_{V}$ to see any
point in the set is minimized. For a simple polygon of $n$ vertices and a set
of $m$ points inside it, we give an $O((n+m)\log{(n+m)})$ time algorithm to
find the visibility center. We find the visibility center of _all_ points in a
simple polygon in $O(n\log n)$ time.

Our algorithm reduces the visibility center problem to the problem of finding
the geodesic center of a set of half-polygons inside a polygon, which is of
independent interest. We give an $O((n+k)\log(n+k))$ time algorithm for this
problem, where $k$ is the number of half-polygons.

##  1 Introduction

Suppose you want to guard a polygon and you have many sensors but only one
guard to check on the sensors. The guard must be positioned at a point $c_{V}$
in the polygon such that when a sensor at any query point $u$ sends an alarm,
the guard travels from $c_{V}$ on a shortest path inside the polygon to _see_
point $u$; the goal is to minimize the maximum distance the guard must travel.
More precisely, we must choose $c_{V}$ to minimize the maximum, over points
$u$, of the geodesic distance from $c_{V}$ to a point that sees $u$. The
optimum guard position $c_{V}$ is called the visibility center of the set $U$
of possible query points. See Figure 1. We give an $O((n+m)\log{(n+m)})$ time
algorithm to find the visibility center of a set $U$ of size $m$ in an
$n$-vertex simple polygon. To find the visibility center of all points inside
a simple polygon, we can restrict our attention to the vertices of the
polygon, which yields an $O(n\log n)$ time algorithm.

Figure 1:  (left) Point $c_{V}$ is the visibility center of points
$U=\\{u_{1},\ldots,u_{6}\\}$. Starting from $c_{V}$, the three points we need
to travel (equally) farthest to see are $u_{1},u_{3}$ and $u_{5}$. The
shortest paths (in blue) to see these points must reach the half-polygons
bounded by the chords (in red) emanating from the points. (right)
Equivalently, $c_{V}$ is the geodesic center of five half-polygons (each shown
as a red boundary chord shaded on one side).

To the best of our knowledge, the idea of visibility centers is new, though it
is a very natural concept that combines two significant branches of
computational geometry: visibility problems [15]; and center problems and
farthest Voronoi diagrams [5].

There is a long history of finding “center points”, for various definitions of
“center”. The most famous of these is Megiddo’s linear time algorithm [22] to
find the center of a set of points in the plane (Sylvester’s “smallest circle”
problem).

Inside a polygon the relevant distance measure is not the Euclidean distance
but rather the shortest path, or _geodesic_ , distance. The geodesic center of
a simple polygon is a point $p$ that minimizes the maximum geodesic distance
from $p$ to any point $q$ of the polygon, or equivalently, the maximum
geodesic distance from $p$ to any vertex of the polygon. Pollack, Sharir, and
Rote [28] gave an $O(n\log n)$ time divide-and-conquer algorithm to find the
geodesic center of a polygon. Our algorithm builds on theirs. A more recent
algorithm by Ahn et al. [1] finds the geodesic center of a polygon in linear
time. Another notion of the center of a polygon is the link center, which can
be found in $O(n\log n)$ time [11].

Center problems are closely related to farthest Voronoi diagrams, since the
center is a vertex of the corresponding farthest Voronoi diagram, or a point
on an edge of the Voronoi diagram in case the center has only two farthest
sites. Finding the farthest Voronoi diagram of points in the plane takes
$\Theta(n\log n)$ time—thus is it strictly harder to find the farthest Voronoi
diagram than to find the center. However, working inside a simple polygon
helps for farthest Voronoi diagrams: the farthest geodesic Voronoi diagram of
the vertices of a polygon can be found in time $O(n\log\log n)$ [27].
Generalizing the two scenarios (points in the plane, and polygon vertices),
yields the problem of finding the farthest Voronoi diagram of $m$ points in a
polygon, which was first solved by Aronov et al. [3] with run-time
$O((n+m)\log(n+m))$, and improved in a sequence of papers [27, 6, 26], with
the current best run-time of $O(n+m\log m)$ [33].

Turning to visibility problems in a polygon, there are algorithms for the
“quickest visibility problem”—to find the shortest path from point $s$ to see
point $q$, and to solve the query version where $s$ is fixed and $q$ is a
query point [2, 32]. For a simple polygon [2], the preprocessing time and
space are $O(n)$ and the query time is $O(\log n)$. We do not use these
results in our algorithm to find the visibility center $c_{V}$, but they are
useful afterwards to find the actual shortest path from $c_{V}$ to see a query
point.

A more basic version of our problem is to find, if there is one, a point that
sees all points in $U$. The set of such points is the kernel of $U$. When $U$
is the set of vertices, the kernel can be found in linear time [21]. For a
general set $U$, Ke and O’Rourke [20] gave an $O(n+m\log(n+m))$ time algorithm
to compute the kernel, and we use some of their results in our algorithm.

Another problem somewhat similar to the visibility center problem is the
watchman problem [10, 12]—to find a minimum length tour from which a single
guard can see the whole polygon. Our first step is similar in flavour to the
first step for the watchman problem, namely, to replace the condition of
“seeing” everything by a condition of visiting certain “essential chords”.

##### Our Results

The distance to visibility from a point $x$ to point $u$ in $P$, denoted
$d_{V}(x,u)$ is the minimum distance in $P$ from $x$ to a point $y$ such that
$y$ sees $u$. For a set of points $U$ in $P$, the visibility radius of $x$
with respect to $U$ is $r_{V}(x,U):=\max\\{d_{V}(x,u):u\in U\\}$. The
visibility center $c_{V}$ of $U$ is a point $x$ that minimizes $r_{V}(x,U)$.
Our main result is:

######  Theorem 1.

There is an algorithm to find the visibility center of a point set $U$ of size
$m$ in a simple $n$-vertex polygon $P$ with run-time $O((n+m)\log(n+m))$.

The key to our algorithm is to reformulate the visibility center problem in
terms of distances to certain _half-polygons_ inside the polygon. We
illustrate the idea by means of the example in Figure 1 where the visibility
center of the 6-element point set $U$ is the _geodesic center_ of a set of
five half-polygons.

More generally, we will reduce the problem of finding the visibility center to
the problem of finding a geodesic center of a linear number of half-polygons.
The input to this problem is a set $\cal H$ of $k$ half-polygons (see Section
2 for precise definitions) and the goal is to find a _geodesic center_ $c$
that minimizes the maximum distance from $c$ to a half-polygon. More
precisely, the geodesic radius from a point $x$ to $\cal H$ is $r(x,{\cal
H}):=\max\\{d(x,H):H\in{\cal H}\\}$, and the geodesic center $c$ of $\cal H$
is a point $x$ that minimizes $r(x,{\cal H})$. Our second main result is:

######  Theorem 2.

There is an algorithm to find the geodesic center of a set $\cal H$ of $k$
half-polygons in a simple $n$-vertex polgyon $P$ with run-time
$O((n+k)\log(n+k))$.

Our algorithm extends the divide-and-conquer approach that Pollack et al. [28]
used to compute the geodesic center of the vertices of a simple polygon.

Our main motivation for finding the geodesic center of half-polygons is to
find the visibility center, but the geodesic center of half-polygons is of
independent interest. Euclidean problems of a similar flavour are to find the
center (or the farthest Voronoi diagram) of line segments or convex polygons
in the plane [7, 19]. These problems are less well-studied than the case of
point sites (e.g., see [4] for remarks on this). The literature for geodesic
centers is even more sparse, focusing almost exclusively on geodesic centers
of points in a polygon. It is thus interesting that the center of half-
polygons inside a polygon can be found efficiently. As a special case, we can
find the geodesic center of the edges of a simple polygon in $O(n\log n)$
time.

The reduction from the visibility center problem to the geodesic center of
half-polygons is in Section 3. The run time is $O((n+m)\log(n+m))$. The
algorithm that proves Theorem 2 (finding the geodesic center of half-polygons)
is in Section 4. Together these prove Theorem 1 (finding the visibility
center).

##  2 Preliminaries

We add a few more basic definitions to augment the main definitions given
above. We work with a simple polygon $P$ of $n$ vertices whose boundary
$\partial P$ is directed clockwise. A chord of $P$ is a line segment inside
$P$ with endpoints on $\partial P$. Any chord divides $P$ into two weakly
simple half-polygons. A half-polygon is specified by its defining chord
$(p,q)$ with the convention that the half-polygon contains the path clockwise
from $p$ to $q$.

The geodesic distance $d(x,y)$ (or simply, distance) between two points $x$
and $y$ in $P$ is the length of the shortest path $\pi(x,y)$ in $P$ from $x$
to $y$. For half-polygon $H$, the geodesic distance $d(x,H)$ is the minimum
distance from $x$ to a point in $H$.

Points $x$ and $y$ in $P$ are visible ($x$ “sees” $y$) if the segment $xy$
lies inside $P$. The distance to visibility from $x$ to $u$, denoted
$d_{V}(x,u)$ is the minimum distance from $x$ to a point $y$ such that $y$
sees $u$. If $x$ sees $u$, then this distance is 0, and otherwise it is the
distance from $x$ to the half-polygon defined as follows. Let $r$ be the last
reflex vertex on the shortest path from $x$ to $u$. Extend the ray
$\overrightarrow{ur}$ from $r$ until it hits the polygon boundary $\partial P$
at a point $p$ to obtain a chord $rp$ (which is an edge of the visibility
polygon of $u$). Of the two half-polygons defined by $rp$, let $H(u,r)$ be the
one that contains $u$. See Figure 1.

######  Observation 3.

$d_{V}(x,u)=d(x,H(u,r))$.

In the remainder of this section we establish the basic result that the
visibility center of a set of points $U$ and the geodesic center of a set of
half-polygons $\cal H$ are unique except in very special cases, and that two
or three tight constraints suffice to determine the centers. We explain this
for the geodesic center of half-polygons, but the same argument works for the
visibility center (or, alternatively, one can use the reduction from the
visibility center to the geodesic center in Section 3). Note that if the
geodesic radius is 0, then any point in the intersection of the half-polygons
is a geodesic center.

######  Claim 4.

Suppose that the geodesic radius $r$ satisfies $r>0$. There is a set ${\cal
H}^{\prime}\subseteq{\cal H}$ of two or three half-polygons such that the set
of geodesic centers of ${\cal H}$ is equal to the set of geodesic centers of
${\cal H}^{\prime}$ and furthermore

  1. 1.

if ${\cal H}^{\prime}$ has size 3 then the geodesic center is unique (e.g.,
see Figure 1)

  2. 2.

if ${\cal H}^{\prime}$ has size 2 then either the geodesic center is unique or
the two half-polygons of ${\cal H}^{\prime}$ have chords that are parallel and
the geodesic center consists of a line segment parallel to them and midway
between them.

The proof of this claim depends on a basic convexity property of the geodesic
distance function that was proved for the case of distance to a vertex by
Pollack et al. [28, Lemma 1] and that we extend to a half-polygon.

Figure 2:  Proving that $d(x,H)$ is a convex function of $d(a,x)$.

A subset $Q$ of $P$ is geodesically convex if for any two points $a$ and $b$
in $Q$, the shortest (or “geodesic”) path $\pi(a,b)$ in $P$ is contained in
$Q$. A function $f$ defined on $P$ is geodesically convex if $f$ is convex on
every geodesic path $\pi(a,b)$ in $P$, i.e., for points $x\in\pi(a,b)$, $f(x)$
is a convex function of $d(a,x)$.

######  Lemma 5.

For any half-polygon $H$, the distance function $d(x,H)$ is geodesically
convex. Furthermore, on any geodesic path $\pi(a,b)$ with $a$ and $b$ outside
$H$, the minimum of $d(x,H)$ occurs at a point or along a line segment
parallel to $h$, the defining chord of $H$.

###### Proof.

Pollack et al. [28] proved the version of this where $H$ is replaced by a
point—in particular, they proved that the distance function is strictly convex
which implies that the minimum occurs at a point.

If $a$ and $b$ are inside $H$, then so is $\pi(a,b)$ and the distance function
is constantly 0. So suppose $a\notin H$. If the path $\pi(a,b)$ intersects
$H$, then it does so at only one point $b^{*}\in h$ (otherwise $h$ provides a
shortcut for part of the path). Then $\pi(b^{*},b)$ lies inside $H$ and it
suffices to prove convexity for the path $\pi(a,b^{*})$. In other words, we
may assume that $b$ is not in the interior of $H$.

The shortest paths $\pi(x,H)$ for $x\in\pi(a,b)$ reach a subinterval
$[h_{1},h_{2}]$ of $h$. See Figure 2. In case this subinterval is a single
point, i.e., $h_{1}=h_{2}$, the convexity result of Pollack et al. proves the
lemma. Otherwise, since shortest paths do not cross, there are points $c$ and
$d$ on $\pi(a,b)$ such that for $x\in\pi(a,c)$ the path $\pi(x,H)$ arrives at
$h_{1}$, for $x\in\pi(c,d)$ the path $\pi(x,H)$ is a straight line segment
reaching $h$ at a right angle, and for $x\in\pi(d,b)$ the path $\pi(x,H)$
arrives at $h_{2}$. The convexity result of Pollack et al. applies to the
paths arriving at the points $h_{1}$ and $h_{2}$.

It remains to consider $x\in\pi(c,d)$. As $x$ moves along $\pi(c,d)$, the
endpoint of $\pi(x,H)$ moves continuously with a one-to-one mapping along the
segment $[h_{1},h_{2}]$. Since the curve $\pi(c,d)$ is convex, this implies
that $d(x,H)$ is a convex function of $d(a,x)$ for $x\in\pi(c,d)$.
Furthermore, the minimum is unique unless a segment of the geodesic is
parallel to $h$.

Finally, one can verify that convexity holds at the points $c$ and $d$, i.e.,
that the three convex functions join to form a single convex function. ∎

Because the intersection of geodesically convex sets is geodesically convex,
and the max of geodesically convex functions is geodesically convex, we get
the following consequences.

######  Corollary 6.

The geodesic radius function $r(x,{\cal H})$ is geodesically convex. The
geodesic ball $B(t,H):=\\{x\in P:d(x,H)\leq t\\}$ for any half-polygon $H$,
and the geodesic ball $B(t):=\\{x\in P:r(x,{\cal H})\leq t\\}$ are
geodesically convex.

###### Proof of Claim 4.

The set of geodesic centers is $C:=\\{x\in P:d(x,H)\leq r\text{ for all
}H\in{\cal H}\\}$. By Corollary 6, $C$ is geodesically convex. If $C$ contains
two distinct points $x_{1}$ and $x_{2}$ then it contains the geodesic path
$\gamma=\pi(x_{1},x_{2})$. By Lemma 5, along $\gamma$, for each $H\in{\cal
H}$, the minimum of the distance function $d(x,H)$ occurs at a point or along
a line segment parallel to $h$. This implies that $\gamma$ can only be a
single line segment parallel to two of the half-polygons of $\cal H$, which is
Case 2 of the Claim.

For Case 1, let us now suppose that $C$ consists of a single point. Because
the boundary of each geodesic ball $\\{x\in P:d(x,H)\leq r\\}$ consists of
circular arcs and line segments, the single point $C$ is uniquely determined
as the intersection of some circular arcs and line segments, and three of
those suffice to determine the point.  ∎

##  3 Reducing the Visibility Center to the Center of Half-Polygons

In this section we reduce the problem of finding the visibility center of a
set of points $U$ in a polygon $P$ to the problem of finding the geodesic
center of a linear number of “essential” half-polygons $\cal H$, which is
solved in Section 4.

By Observation 3 (and see Figure 1) the visibility center of $U$ is the
geodesic center of the set of $O(mn)$ half-polygons $H(u,r)$ where $u\in U$,
$r$ is a reflex vertex of $P$ that sees $u$, and $H(u,r)$ is the half-polygon
containing $u$ and bounded by the chord that extends $\overrightarrow{ur}$
from $r$ until it hits $\partial P$ at a point $t$. Note that finding $t$ is a
ray shooting problem and costs $O(\log n)$ time after an $O(n)$ time
preprocessing step [18].

However, this set of half-polygons is too large. We will find a set $\cal H$
of $O(n)$ “essential” half-polygons that suffice, i.e., such that the
visibility center of $U$ is the geodesic center of the half polygons of $\cal
H$. In fact, we give two possible sets of essential half-polygons, ${\cal
H}_{\rm reflex}$ and ${\cal H}_{\rm hull}$, where the latter set can be found
more efficiently. Although the bottleneck is still the algorithm for geodesic
center of half-polygons, it seems worthwhile to optimize the reduction.

We first observe that any half-polygon that contains another one is redundant.
For example, in Figure 1, $H(u_{4},r_{4})$ is redundant because it contains
$H(u_{5},r_{4})$. At each reflex vertex $r$ of $P$, there are at most two
minimal half-polygons $H(u,r)$. Define ${\cal H}_{\rm reflex}$ to be this set
of minimal half-polygons. Note that ${\cal H}_{\rm reflex}$ has size
$O(n_{r})$ where $n_{r}$ is the number of reflex vertices of $P$.

Observe that for the case of finding the visibility center of _all_ points of
$P$, ${\cal H}_{\rm reflex}$ consists of the half-polygons $H(v,r)$ where
$(v,r)$ is an edge of $P$, so ${\cal H}_{\rm reflex}$ can be found in time
$O(n+n_{r}\log n)$.

For a point set $U$, the set ${\cal H}_{\rm reflex}$ was also used by Ke and
O’Rourke [20] in their algorithm to compute the kernel of point set $U$ in
polygon $P$. (Recall from the Introduction that the kernel of $U$ is the set
of points in $P$ that see all points of $U$.) They gave a sweep line algorithm
(“Algorithm 2”) to find ${\cal H}_{\rm reflex}$ in time $O((n+m)\log(n+m))$.
To summarize:

######  Proposition 7.

The geodesic center of ${\cal H}_{\rm reflex}$ is the visibility center of
$U$. Furthermore, ${\cal H}_{\rm reflex}$ can be found in time
$O((n+m)\log(n+m))$.

In the remainder of this section we present a second approach using ${\cal
H}_{\rm hull}$ that eliminates the $O(n\log n)$ term. This does not change the
runtime to find the visibility center, but it means that improving the
algorithm to find the geodesic center of half-polygons will automatically
improve the visibility center algorithm. The idea is that ${\cal H}_{\rm
reflex}$ is wasteful in that a single point $u\in U$ can give rise to $n_{r}$
half-polygons. Note that we really only need three half-polygons in an
essential set, though the trouble is to find them!

We first eliminate the case where the kernel of $U$ is non-empty (i.e.,
$r_{V}=0$) by running the $O(n+m\log(n+m))$ time kernel-finding algorithm of
Ke and O’Rourke [20]. Next we find ${\cal H}_{\rm hull}$ in two steps. First
make a subset ${\cal H}_{0}$ as follows. Construct $R$, the geodesic convex
hull of $U$ in $P$ in time $O(n+m\log(m+n))$ [17, 31]. For each edge $(u,r)$
of $R$ where $u\in U$ and $r$ is a reflex vertex of $P$, put $H(u,r)$ into
${\cal H}_{0}$. Note that ${\cal H}_{0}$ has size $O(\min\\{n_{r},m\\})$ so
ray shooting to find the endpoints of the chords $H(u,r)$ takes time
$O(n+\min\\{n_{r},m\\}\log n)$. Unfortunately, as shown in Figure 3, ${\cal
H}_{0}$ can miss an essential half-polygon.

Next, construct a geodesic center $c_{0}$ of ${\cal H}_{0}$ using the
algorithm of Section 4. (Note that the geodesic center can be non-unique and
in such cases $c_{0}$ denotes any one point from the set of geodesic centers.)
Then repeat the above step for $U\cup\\{c_{0}\\}$, more precisely, construct
$R^{\prime}$, the geodesic convex hull of $U\cup\\{c_{0}\\}$ in $P$ and for
each edge $(u,r)$ of $R^{\prime}$ where $u\in U$ and $r$ is a reflex vertex of
$P$, add ${H}(u,r)$ to ${\cal H}_{0}$. This defines ${\cal H}_{\rm hull}$.
Again, ${\cal H}_{\rm hull}$ has size $O(\min\\{n_{r},m\\})$ and ray shooting
costs $O(n+\min\\{n_{r},m\\}\log n)$.

Figure 3:  The geodesic convex hull of $U=\\{u_{1},\ldots,u_{5}\\}$ is shaded
grey. ${\cal H}_{0}$ consists of the two half-polygons $H(u_{2},r_{2})$ and
$H(u_{3},r_{3})$ (with solid red chords), but misses $H(u_{1},r_{1})$, which
is essential for the visibility center $c_{V}$. The point $c_{0}$ denotes a
geodesic center of ${\cal H}_{0}$.

######  Theorem 8.

Suppose the kernel of $U$ is empty. Then the geodesic center of ${\cal H}_{\rm
hull}$ is the visibility center of $U$. Furthermore ${\cal H}_{\rm hull}$ can
be found in time $O(n+m\log(n+m))$ plus the time to find the geodesic center
of $O(\min\\{n_{r},m\\})$ half-polygons.

###### Proof.

The run-time was analyzed above. Consider the visibility center $c_{V}$. By
assumption, $r_{V}>0$. We consider the half-polygons $H(u,r)\in{\cal H}_{\rm
reflex}$ such that $r_{V}=d(c_{V},H(u,r))$. By Claim 4 either there are three
of these half-polygons, $H_{1}$, $H_{2}$ and $H_{3}$, that uniquely determine
$c_{V}$, or there are two, $H_{1}$ and $H_{2}$, that determine $c_{V}$. Then
$c_{V}$ is the geodesic center of $H_{i}$ $i=1,2,3$ or $i=1,2$ depending on
which case we are in. Let $H_{i}=H(u_{i},r_{i})$.

If all the $H_{i}$’s are in ${\cal H}_{0}$, we are done. We will show that at
least two are in ${\cal H}_{0}$ and the third one (if it exists) is “caught”
by $c_{0}$. See Figure 3. Let $h_{i}$ be the chord defining $H_{i}$ and let
$\overline{H}_{i}$ be the other half-polygon determined by $h_{i}$.

######  Claim 9.

If $U$ contains a point in $\overline{H}_{i}$ then $(u_{i},r_{i})$ is an edge
of $R$ so $H_{i}\in{\cal H}_{0}$.

###### Proof.

Let $u$ be a point in $\overline{H}_{i}$. Observe that $\pi(u_{i},u)$ contains
the segment $u_{i}r_{i}$. Thus $r_{i}$ is a vertex of $R$. Furthermore
$u_{i}r_{i}$ is an edge of $R$. (Note that $H_{i}$ is extreme at $r$ since we
picked it from ${\cal H}_{\rm reflex}$.) Thus $H_{i}$ is in ${\cal H}_{0}$. ∎

######  Claim 10.

At least two of the ${H}_{i}$’s lie in ${\cal H}_{0}$.

###### Proof.

First observe that if two of the half-polygons are disjoint, say $H_{i}$ and
$H_{j}$, then they lie in ${\cal H}_{0}$, because $u_{i}\in H_{i}$ implies
$u_{i}\in\overline{H}_{j}$ so by Claim 9, $H_{i}\in{\cal H}_{0}$, and
symmetrically, $H_{j}\in{\cal H}_{0}$.

We separate the proof into cases depending on the number of $H_{i}$’s. If
there are two then they must be disjoint otherwise a point in their
intersection would be a visibility center with visibility radius $r_{V}=0$.
Then by the above observation, they are both in ${\cal H}_{0}$.

It remains to consider the case of three half-polygons. If two are disjoint,
we are done, so suppose each pair $H_{i},H_{j}$ intersects. Then the three
chords $h_{i}$ form a triangle. Furthermore, since $\bigcap{\overline{H}_{i}}$
is non-empty (it contains $c_{V}$), the inside of the triangle is
$\bigcap{\overline{H}_{i}}$. Now suppose $H_{1}\notin{\cal H}_{0}$. Then by
Claim 9, $u_{2},u_{3}\in H_{1}$. This implies (see Figure 3) that
$u_{2}\in\overline{H}_{3}$ and $u_{3}\in\overline{H}_{2}$, so by Claim 9,
$H_{2}$ and $H_{3}$ are in ${\cal H}_{0}$. ∎

We now complete the proof of the theorem. We only need to consider the case of
three $H_{i}$’s, where one of them, say $H_{1}$, is not in ${\cal H}_{0}$.
Our goal is to show that $c_{0}$, the geodesic center of ${\cal H}_{0}$, lies
in $\overline{H}_{1}$ and thus $H_{1}$ is in ${\cal H}_{\rm hull}$. Let
$X=\\{x\in P:d(x,{H}_{2})\leq r_{V}{\rm\ and\ }d(x,{H}_{3})\leq r_{V}\\}$.
Observe that $c_{0}\in X$ (because the radius is non-increasing as we
eliminate half-polygons). Now, $c_{V}$ is the unique point within distance
$r_{V}$ of the half-polygons ${H}_{1}$, ${H}_{2}$ and ${H}_{3}$. If $c_{0}\in
H_{1}$, then $c_{0}$’s distance to ${H}_{1}$ would be 0 which contradicts the
uniqueness property of $c_{V}$. Thus $c_{0}\in\overline{H}_{1}$. By the same
reasoning as in Claim 9, this implies that $u_{1}r_{1}$ is an edge of
$R^{\prime}$, the geodesic convex hull of $U\cup\\{c_{0}\\}$. Thus $H_{1}$ is
in ${\cal H}_{\rm hull}$ by definition of ${\cal H}_{\rm hull}$. ∎

##  4 The Geodesic Center of Half-Polygons

In this section, we give an algorithm to find the geodesic center of a set
$\mathcal{H}$ of $k$ half-polygons inside an $n$-vertex polygon $P$ with run
time $O((n+k)\log(n+k))$. (Note that although we say “the” geodesic center, it
need not be unique, see Claim 4.) We preprocess by sorting the half-polygons
in cyclic order of their first endpoints around $\partial P$ in time $O(k\log
k)$. We assume that no half-polygon contains another—such irrelevant non-
minimal half-polygons can be detected from the sorted order and discarded. We
also make the general position assumption that no point in $P$ has equal non-
zero distances to more than a constant number of half-polygons of $\cal H$.

We follow the approach that Pollack et al. [28] used to find the geodesic
center of the vertices of a polygon. Many steps of their algorithm rely, in
turn, on search algorithms of Megiddo’s [22].

The main ingredient of the algorithm is a linear time chord oracle that, given
a chord $K=ab$ of the polygon, finds the relative geodesic center, $c_{K}$
(the optimum center point restricted to points on the chord), and tells us
which side of the chord contains the center. We must completely redo the chord
oracle in order to handle paths to half-polygons instead of vertices, but the
main steps are the same. Our chord oracle runs in time $O(n+k)$. The chord
oracle of Pollack et al. was used as a black box in subsequent faster
algorithms [1], so we imagine that our version will be an ingredient in any
faster algorithm for the geodesic center of half-polygons.

Using the chord oracle, we again follow the approach of Pollack et al. to find
the geodesic center. The total run time is $O((n+k)\log(n+k))$.

We give a road-map for the remainder of this section, listing the main steps,
which are the same as those of Pollack et al., and highlighting the parts that
we must rework.

§ 4.1 A Linear Time Chord Oracle

  1. 1.

Test a candidate center point. Given the relative geodesic center $c_{K}$ on
chord $K=ab$, is the geodesic center to the left of right of chord $K$? This
test reduces the chord oracle to finding the relative geodesic center, which
is done via the following steps.

  2. 2.

Find shortest paths from $a$ and from $b$ to all half-polygons. The details of
this step are novel, because we need shortest paths to half-polygons rather
than vertices.

  3. 3.

Find a linear number of simple functions defined on $K$ whose upper envelope
is the geodesic radius function. We must redo this from the ground up.

  4. 4.

Find the relative center on $K$ (the point that minimizes the geodesic radius
function) using Megiddo’s technique.

§ 4.2 Finding the Geodesic Center of Half-Polygons

  1. 1.

Use the chord oracle to find a region of $P$ that contains the center and such
that for any half-polygon $H\in\cal H$, all geodesic paths from the region to
$H$ are combinatorially the same. We give a more modern version of this step
using epsilon nets.

  2. 2.

Solve the resulting Euclidean problem of finding a smallest disk that contains
given disks and intersects given half-planes. This is new because of the
condition about intersecting half-planes.

###  4.1 A Linear Time Chord Oracle

In this section we give a linear time chord oracle. Given a chord $K=ab$ the
chord oracle tells us whether the geodesic center of $\cal H$ lies to the
left, to the right, or on the chord $K$. It does this by first finding the
relative geodesic center $c_{K}=\operatorname*{argmin}\\{r(x,{\cal H}):x\in
K\\}$, together with the half-polygons that are farthest from $c_{K}$ and the
first segments of the shortest paths from $x$ to those farthest half-polygons.
From this information, we can identify which side of $K$ contains the geodesic
center $c$ in the same way as Pollack et al. by testing the vectors of the
first segments of the shortest paths from $c_{K}$ to its furthest half-
polygons. This test is described in Subsection 4.1.1.

The chord oracle thus reduces to the problem of finding the relative geodesic
center and its farthest half-polygons. The main idea here is to capture the
geodesic radius function along the chord (i.e., the function $r(x,{\cal H})$
for $x\in K$) as the upper envelope of a linear number of easy-to-compute
convex functions defined on overlapping subintervals of $K$. In order to find
the functions (Section 4.1.3) we first compute shortest paths from $a$ and
from $b$ to all the half-polygons (Section 4.1.2). Finally we apply Megiddo’s
techniques (Section 4.1.4) to find the point $c_{K}$ on $K$ that minimizes the
geodesic radius function.

####  4.1.1 Testing a Candidate Center Point

In this section we show how to test in constant time whether a candidate point
is a geodesic center, or relative center, and if not, in which direction the
center lies. The basic idea is that a local optimum is a global optimum, so a
local test suffices. In more detail, the input is a point $x$ on a chord
$K=ab$ together with its geodesic radius $r(x,{\cal H})$ and the first
segments of the shortest paths from $x$ to its farthest half-polygons. The
goal is to test in constant time: (1) whether $x$ is a relative geodesic
center of $K$, and if not, which direction to go on $K$ to reach a relative
center; and (2) if $x$ is a relative geodesic center, whether $x$ is a
geodesic center of $P$, and if not, which side of $K$ contains a geodesic
center of $P$. These tests are illustrated in Figure 4. Note that if
$r(x,{\cal H})$ is zero, then $x$ is a geodesic center and no further work is
required.

Figure 4:  Points $x_{i}$ on chord $K=ab$ with directions of paths to farthest
half-polygons in dashed blue, wedge $W_{\alpha}$ shaded, and the direction for
improvement in dotted red. (a) $x_{1}$ is not a relative center of $K$,
whereas $x_{2}$ is a relative center but not the geodesic center of $P$. (b,c)
$x_{3}$ (a reflex vertex of the polygon) and $x_{4}$ are geodesic centers.

The tests are accomplished via the following lemma, which is analogous to
Lemmas 2 and 3 of Pollack et al. [28].

######  Lemma 11.

Let $x$ be a point on chord $K$, and let $V$ be the vectors of the first
segments of the shortest paths from $x$ to its farthest half-polygons $\cal
F$. Let $\alpha$ be the smallest angle of a wedge $W_{\alpha}$ with apex $x$
that contains all the vectors of $V$ and such that $W_{\alpha}$, restricted to
a small neighbourhood of $x$, is contained in $P$.

  1. 1.

Location of the relative center. Let $L$ be the line through $x$ perpendicular
to $K$. If one of the open half-planes determined by $L$ contains
$W_{\alpha}$, then $x$ is not a relative center, and all relative centers lie
on that side of $L$. Otherwise, $x$ is a relative center.

  2. 2.

Location of the center. Now suppose that $x$ is a relative geodesic center. If
$\alpha<\pi$ then $x$ is not a geodesic center, and all geodesic centers lie
on the side of $K$ that contains the ray bisecting the angle of $W_{\alpha}$.
If $\alpha>\pi$, then $x$ is the unique geodesic center, and furthermore, $x$
is determined by two or three vectors of $V$—the two that bound $W_{\alpha}$,
plus one inside $W_{\alpha}$ unless $x$ is on the boundary of $P$. Finally, if
$\alpha=\pi$ then $x$ is a geodesic center (though not necessarily unique),
and furthermore, $x$ is determined by the two vectors of $V$ that bound
$W_{\alpha}$.

###### Proof.

We prove the two parts separately.

  1. 1.

Suppose $W_{\alpha}$ lies in an open half-plane determined by $L$ (say, the
left side of $L$). Then moving $x$ an epsilon distance left along $K$ gives a
point with smaller geodesic radius since the distance to any half-polygon in
$\cal F$ decreases, and no other half-polygon becomes a farthest half-polygon.
Therefore $x$ is not a relative center. Furthermore, because the geodesic
radius function $r(x,{\cal H})$ is convex on $K$ (by Corollary 6), the
relative center lies to the left on $K$.

Next suppose $W_{\alpha}$ does not lie in an open half-plane of $L$. Then any
epsilon movement of $x$ along $K$ increases the distance to some half-polygon
in $\cal F$, so $x$ is a local minimum on $K$ and therefore $x$ is the
relative center (again using the face that the geodesic radius function is
convex on $K$).

  2. 2.

Suppose $\alpha<\pi$. Let $b$ be the ray that bisects $W_{\alpha}$. Moving $x$
an epsilon distance along $b$ gives a point $x^{\prime}$ with smaller geodesic
radius. Therefore $x$ is not the center. Next we prove that the center $c$
lies on the side of $K$ that contains $b$. Suppose not. Consider the geodesic
$\pi(c,x^{\prime})$. By Corollary 6, the geodesic radius function is convex on
$\pi(c,x^{\prime})$. But then the point where the geodesic crosses $K$ has a
smaller geodesic radius than $x$, a contradiction to $x$ being the relative
center.

Next suppose $\alpha>\pi$. Let $v_{1}$ and $v_{2}$ be the two vectors that
bound $W_{\alpha}$. If $x$ is on the boundary of $P$ it must be at a reflex
vertex of $P$. Otherwise, since no smaller wedge contains $V$, there must be a
third vector $v_{3}$ in $V$, making an angle $<\pi$ with each of $v_{1}$ and
$v_{2}$. In either case ($x$ on the boundary of $P$ or not) any epsilon
movement of $x$ in $P$ increases the distance to the half-polygon
corresponding to one of the $v_{i}$’s. Thus $x$ is a local minimum in $P$ and
(by geodesic convexity of the radius function) $x$ is the center. Furthermore,
$x$ is determined by $v_{1}$ and $v_{2}$—and $v_{3}$ if $x$ is interior to
$P$.

Finally, suppose $\alpha=\pi$. As in the previous case, $x$ is a geodesic
center and is determined by the two vectors $v_{1}$ and $v_{2}$ of $V$ that
bound $W_{\alpha}$. Furthermore, $x$ is unique unless the two corresponding
half-polygons have parallel defining chords, and $v_{1}$ and $v_{2}$ reach
those chords at right angles. In this case the set of geodesic centers
consists of a line segment through $x$ parallel to the chords.

∎

####  4.1.2 Shortest Paths to Half-Polygons

In this section we give a linear time algorithm to find the shortest path tree
from point $a$ on the polygon boundary to all the half-polygons $\cal H$.
Recall that each half-polygon is specified by an ordered pair of endpoints on
$\partial P$, and the half-polygons are sorted in clockwise cyclic order by
their first endpoints. From this, we identify the half-polygons that contain
$a$, and we discard them—their distance from $a$ is 0. Let
$H_{1},\ldots,H_{k^{\prime}}$ be the remaining half-polygons where $H_{i}$ is
bounded by endpoints $p_{i}q_{i}$, and the $H_{i}$’s are sorted by $p_{i}$,
starting at $a$.

The idea is to first find the shortest path map $T_{a}$ from $a$ to the set
consisting of the polygon vertices and the points $p_{i}$ and $q_{i}$. Recall
that the shortest path map is an augmentation of the shortest path tree that
partitions the polygon into triangular regions in which the shortest path from
$a$ is combinatorially the same (see Figure 5). The shortest path map can be
found in linear time [16]. Note that $T_{a}$ is embedded in the plane (none of
its edges cross) and the ordering of its leaves matches their ordering on
$\partial P$. Our algorithm will traverse $T_{a}$ in depth-first order, and
visit the triangular regions along the way.

Our plan is to augment $T_{a}$ to a shortest path tree $\bar{T}_{a}$ that
includes the shortest paths from $a$ to each half-polygon $H_{i}$. Note that
$\bar{T}_{a}$ is again an embedded ordered tree. We can find $\pi(a,H_{i})$ by
examining the regions of the shortest path map intersected by $p_{i}q_{i}$.
These lie in the _funnel_ between the shortest paths $\pi(a,p_{i})$ and
$\pi(a,q_{i})$. Note that edges of the shortest path map $T_{a}$ may cross the
chord $p_{i}q_{i}$. Also, the funnels for different half-polygons may overlap.
The key to making the search efficient is the following lemma:

######  Lemma 12.

The ordering $H_{1},H_{2},\ldots,H_{k^{\prime}}$ matches the ordering of the
paths $\pi(a,H_{i})$ in the tree $\bar{T}_{a}$.

###### Proof.

Consider two half-polygons $H_{i}=p_{i}q_{i}$ and $H_{j}=p_{j}q_{j}$, with
$i<j$. We prove that $\pi(a,H_{i})$ comes before $\pi(a,H_{j})$ in
$\bar{T}_{a}$. If $H_{i}$ and $H_{j}$ are disjoint, the result is immediate
since the corresponding funnels do not overlap. Otherwise (because neither
half-polygon is contained in the other) $p_{i}q_{i}$ and $p_{j}q_{j}$ must
intersect, say at point $x$. See Figure 5. Let $t_{i}$ and $t_{j}$ be the
terminal points of the paths $\pi(a,H_{i})$ and $\pi(a,H_{j})$, respectively.
If $t_{i}$ lies in $p_{i}x$ and $t_{j}$ lies in $xq_{j}$ then the result
follows since $t_{i}$ and $t_{j}$ lie in order on the boundary of the
truncated polygon formed by removing $H_{i}$ and $H_{j}$. So suppose that
$t_{j}$ lies in $p_{j}x$ (the other case is symmetric). Then $\pi(a,t_{j})$
crosses $p_{i}q_{i}$ at a point $z$ in $p_{i}x$. From $z$ to $t_{j}$ the path
$\pi(a,t_{j})$ lies inside the  cone with apex $x$ bounded by the rays from
$x$ through $z$ and from $x$ through $t_{j}$. Within that cone, the path only
turns left. The angle $\alpha_{j}$ at $t_{j}$ is $\geq 90^{\circ}$ (it may be
$>90^{\circ}$ if $t_{j}=p_{j}$), which implies that the angle $\alpha_{i}$ at
$z$ is $>90^{\circ}$. Therefore $t_{i}$ lies to the left of $z$, as required.
∎

Figure 5: The shortest path map $T_{a}$ (thin blue) and the augmentation
(dashed red) to include shortest paths to the two half-polygons bounded by
chords $p_{i}q_{i}$ and $p_{j}q_{j}$ (thick red).

Based on the Lemma, the algorithm traverses the regions of the shortest path
map $T_{a}$ in depth first search order, and traverses the half-polygons
$H_{i}$ in order $i=1,2,\ldots,k^{\prime}$. It is easy to test if one region
contains the shortest path to $H_{i}$ (either to $p_{i}$, or to $q_{i}$, or
reaching an internal point of $p_{i}q_{i}$ at a right angle); if it does, we
increment $i$, and otherwise we proceed to the next region. The total time is
$O(n+k)$.

####  4.1.3 Functions to Capture the Distance to Farthest Half-Polygons

In this section we capture the geodesic radius function for points on a chord
$K=ab$ as the upper envelope of functions defined on overlapping subintervals
of $K$. Besides extending the method of Pollack et al. [28] to deal with half-
polygons (rather than vertices), our aim is to give a clearer and easier-to-
verify presentation.

In more detail, we give a linear time algorithm to find a linear number of
easy-to-compute convex functions defined on the chord $K=ab$ whose upper
envelope is the geodesic radius function $r(x,{\cal H})$ for $x\in K$.
Specifically, a coarse cover is a set of triples $(I,f,H)$ where:

  1. 1.

$I$ is a subinterval of $K$, $f$ is a function defined on domain $I$, and
$H\in{\cal H}$.

  2. 2.

$f(x)=d(x,H)$ for all $x\in I$, and $f$ has one of the following forms:

     * •

$f(x)=0$.

     * •

$f(x)=d_{2}(x,v)+\kappa$ where $d_{2}$ is Euclidean distance, $\kappa$ is a
constant, $v$ is a vertex of $P$, and the segment $xv$ is the first segment of
the path $\pi(x,H)$.

     * •

$f(x)=d_{2}(x,{\bar{h}})$, where $d_{2}$ is Euclidean distance, $\bar{h}$ is
the line through the defining chord of $H$, and the path $\pi(x,H)$ is the
straight line segment from $x$ to $\bar{h}$ (meeting $\bar{h}$ at right
angles).

  3. 3.

For any point $x\in K$ and any half-polygon $H$ that is farthest from $x$,
there is a triple $(I,f,H)$ in the coarse cover with $x\in I$—with the
exception that if two triples have identical $I$ and identical
$f=d_{2}(x,v)+\kappa$, then we may eliminate one of them.

In particular, this implies that the upper envelope of the functions is the
geodesic radius, i.e., for any $x\in K$, the maximum of $f(x)$ over intervals
$I$ containing $x$ is equal to $r(x,{\cal H})$.

For intuition, see Figure 6, which shows several intervals and their
associated functions. We will find the elements of the coarse cover separately
for the two pieces of the polygon on each side of $K$, and then take the union
of the two sets. In this section we visualize $K$ as horizontal and deal with
the upper piece of the polygon.

Figure 6:  An illustration of functions and intervals. For $x$ in interval
$I_{1}$, $d(x,H_{1})=d_{2}(x,u)+\kappa_{1}$. For $x$ in $I_{2}$,
$d(x,H_{1})=d_{2}(x,v)+\kappa_{2}$. For $x$ in $I_{3}$,
$d(x,H_{2})=d_{2}(x,H_{2})$.

A large coarse cover. We first describe a coarse cover of $O(nk)$ triples and
then show how to reduce to linear size. Consider a half-polygon $H$ with
defining chord $h$. Suppose first that $K$ does not intersect $H$, i.e., $a$
and $b$ lie outside $H$. All shortest paths from points on $K$ to $H$ lie in
the funnel $Y(H)$ which is a subpolygon bounded by the chord $K$, the path
$\pi(a,H)$ (which is a path in ${\bar{T}}_{a}$), the path $\pi(b,H)$ (in
${\bar{T}}_{b}$), and the segment along $h$ between the terminals of those two
paths. See Figure 7. If the paths $\pi(a,H)$ and $\pi(b,H)$ are disjoint then
they are both reflex paths and all vertices on the paths are visible from $K$
(see Figure 7(a)). Otherwise, the paths are reflex and visible from $K$ until
they reach the first common vertex $u$, and then they have a common subpath
from $u$ to $H$ that is not visible from $K$ (see Figure 7(b)).

Before describing how to obtain triples of the coarse cover from $Y(H)$, we
first consider the case when $K$ intersects $H$, i.e., $a$ or $b$ lies inside
$H$. If both $a$ and $b$ are inside $H$, then we add the triple $(I=ab,f=0,H)$
to the coarse cover. If $b$ is outside but $a$ is inside (the other case is
symmetric), then $h$ and $K$ intersect at a point $p$. If $\pi(b,H)$ reaches
$H$ below $K$, then $H$ will be handled when we deal with the piece of the
polygon below $K$. Otherwise (see Figure 7(c)) we add the triple
$(I=ap,f=0,H)$ to the coarse cover, and we deal with the $pb$ portion of the
chord as in the general case above but modifying the funnel $Y(H)$ so that the
path $\pi(a,H)$ is replaced by $p$.

Figure 7: The funnel $Y(H)$ (shaded) and its shortest path map which is
bounded by edge extensions (dashed segments). (a) The case of disjoint paths
$\pi(a,H)$ and $\pi(b,H)$. For $x\in I_{1}$, $d(x,H)=d_{2}(x,u)+\kappa$. For
$x\in I_{2}$, $d(x,H)=d_{2}(x,{\bar{h}})$. (b) The case of paths that meet at
vertex $u$. (c) The case where $a\in H$.

Each funnel $Y(H)$ can be partitioned into its shortest path map $M(H)$ where
two points are in the same region of $M(H)$ if their paths to $H$ are
combinatorially the same. (We consider a path that arrives at an endpoint of
$h$ and a path that arrives at an interior point of $h$ to be combinatorially
different.) Observe that boundaries of the regions of $M(H)$ are extensions of
tree edges plus lines perpendicular to $h$. See Figure 7. The regions of
$M(H)$ are triangles, plus possibly one trapezoid. A triangle region has a
base segment $I\subseteq K$, and an apex vertex $u$ on $\pi(a,H)$ [or
$\pi(b,H)$]; the shortest path from any point $x\in I$ to $H$ consists of the
line segment $xu$ plus the path in ${\bar{T}}_{a}$ [or ${\bar{T}}_{b}$] from
$u$ to $H$, so $d(x,H)=d_{2}(x,u)+\kappa$ where $\kappa$ is the tree distance
from $u$ to the leaf corresponding to $H$. A trapezoid region has a base
segment $I\subseteq K$, and two sides orthogonal to $h$; the shortest path
from any point $x\in I$ to $H$ consists of the line segment orthogonal to $h$
from $x$ to $h$, so $d(x,H)=d_{2}(x,{\bar{h}})$ where $\bar{h}$ is the line
through $h$. Thus each region of $M(H)$ gives rise to a triple $(I,f,H)$
satisfying properties (1) and (2) of a coarse cover.

We claim that the set of triples defined above, i.e., all the triples defined
from $Y(H)$ together with the special triples when $H$ intersects $K$, form a
coarse cover. Properties (1) and (2) are satisfied, and property (3) is
satisfied because we have captured all shortest paths from $x$ to $H$ for all
$x\in K$ and all half-polygons $H$. Since each $Y(H)$ has size $O(n)$, this
coarse cover has size $O(nk)$.

Intuition for a linear-size coarse cover. The secret to reducing the size of
the coarse cover is to observe that if the funnels for some half-polygons
${\cal H}^{\prime}\subseteq{\cal H}$ share an edge $uv$ of ${\bar{T}}_{a}$
with $u$ closer to the root, and both $u$ and $v$ visible from $K$, then their
shortest path maps share the same triangle with apex $u$, base $I$, and sides
bounded by the extension of the edge from $v$ to $u$ and the extension of the
edge from $u$ to its parent in ${\bar{T}}_{a}$ (see Figure 8(a)). In this
case, we claim that for this triangle, we only need a coarse cover element for
one of the half-polygons in ${\cal H}^{\prime}$, specifically, for one half-
polygon that has the maximum distance from $v$ in the tree ${\bar{T}}_{a}$.
This is because only half-polygons farthest from $v$ matter, and furthermore,
we need not keep more than one half-polygon that has the maximum distance
because the interval $I$ and the function $f(x)=d_{2}(x,u)+\kappa$ are the
same. We first specify the coarse cover precisely and then prove correctness,
which makes the above observation formal.

Definitions. Let ${\bar{T}}_{a}$ and ${\bar{T}}_{b}$ be directed from root to
leaves. For any node $v$ in $\bar{T}_{a}$ define $\ell_{a}(v)$ to be the
maximum length of a directed path in $\bar{T}_{a}$ from $v$ to a leaf node
representing a terminal point on some half-polygon, and define $F_{a}(v)$ to
be that farthest half-polygon (breaking ties arbitrarily). Define functions
$\ell_{b}$ and $F_{b}$ similarly. We can compute these functions in linear
time in leaf-to-root order. In particular, we compute $\ell_{a}(u)$ for the
nodes $u$ of $\bar{T}_{a}$ as follows. Initialize $\ell_{a}(u)$ to 0 if $u$
represents a terminal point of a half-polygon chord, and to $-\infty$
otherwise. Then from leaf-to-root order, update $\ell_{a}(u)$ to
$\max\\{\ell_{a}(u),\max\\{|uv|+\ell_{a}(v):v$ a child of $u\\}\\}$. We can
compute $\ell_{b}(u)$ similarly. The runtime is $O(n+k)$.

Define $p_{a}(u)$ and $p_{b}(u)$ to be the parents of node $u$ in
$\bar{T}_{a}$ and $\bar{T}_{b}$, respectively. As noted by Pollack et al.
[28], a vertex $u$ is visible from some point on $K$ if and only if
$p_{a}(u)\neq p_{b}(u)$. Furthermore, we note that if $u$ is visible from some
point on $K$, then extending the edge from $u$ through $p_{a}(u)$ reaches a
point $x_{a}(u)$ on $K$ from which $u$ is visible. Similarly, extending the
edge from $u$ through $p_{b}(u)$ reaches a point $x_{b}(u)$ on $K$ from which
$u$ is visible.

In defining the shortest path map $M(H)$, we added boundary lines orthogonal
to the defining chord $h$ at the terminals of the paths $\pi(a,H)$ and
$\pi(b,H)$. If a path terminates at an internal point of $h$ then the last
edge of the path is orthogonal to $h$, and the boundary line extends the last
edge. In order to avoid special cases, it will be convenient if all boundary
lines are extensions of tree edges, i.e., to assume that even the paths that
terminate at endpoints of $h$ end with a segment orthogonal to $H$. We add
$0$-length segments to the trees ${\bar{T}}_{a}$ and ${\bar{T}}_{b}$ to make
this true. The extension of such a $0$-length edge is orthogonal to $H$. Note
that it is possible that both $\pi(a,H)$ and $\pi(b,H)$ terminate at the same
endpoint of $h$, in which case the added 0-length segment is common to both
trees, so we regard the terminal point of the paths as _not_ visible from $K$.
See Figure 8(c). (The other endpoint of the 0-length segment may or may not be
visible.)

The coarse cover $\cal T$. Define $\cal T$ to have elements of the following
four types. See Figure 8.

  1. 0.

For each half-polygon $H$ that intersects $K$ there is a coarse cover element
$(I,f,H)$ where $I=K\cap H$ and $f(x)=0$.

  2. 1.

For each edge $(u,v)$ in ${\bar{T}}_{a}$ where $u=p_{a}(v)$, $u\neq a$, and
$u$ and $v$ are both visible from $K$, there is an associated $a$-side
triangle that has apex $u$ and base $I=[x_{a}(u),x_{a}(v)]\subseteq K$. The
associated coarse cover element is $(I,f,H)$ where $H=F_{a}(v)$ and
$f(x)=d_{2}(x,u)+|uv|+\ell_{a}(v)$. Define $b$-side triangles and their
associated coarse cover elements symmetrically.

  3. 2.

For each edge $(u,v)$ that is common to ${\bar{T}}_{a}$ and ${\bar{T}}_{b}$
where $u$ is visible from $K$ and $v$ is not (i.e., $u=p_{a}(v)=p_{b}(v)$)
there is an associated central triangle that has apex $u$ and base
$I=[x_{a}(u),x_{b}(u)]\subseteq K$. The associated coarse cover element is
$(I,f,H)$ where $H=F_{a}(v)=F_{b}(v)$ and $f(x)=d_{2}(x,u)+|uv|+\ell_{a}(v)$.

  4. 3.

For each half-polygon $H$ such that the terminal points $t(a,H)$ of $\pi(a,H)$
and $t(b,H)$ of $\pi(b,H)$ are distinct, there is a central trapezoid with
base $I\subseteq K$ bounded by the two lines perpendicular to $h$ emanating
from $t(a,H)$ and $t(b,H)$—these lines are the extensions of the (possibly
$0$-length) last edges of the paths. The associated coarse cover element is
$(I,f,H)$ where $H$ is the given half-polygon and $f(x)=d_{2}(x,{\bar{h}})$
where $\bar{h}$ is the line through the defining chord of $H$.

Figure 8:  Elements of the coarse cover: (a) $I$ is the base of an $a$-side
triangle associated with edge $uv$; (b) $I$ is the base of a central triangle
associated with edge $uv$; (c) $I$ is the base of a central triangle
associated with $0$-length edge $uv$; (d) $I_{1}$ is the base of a central
trapezoid associated with terminal points $v$ and $v^{\prime}$ on $H$; $I_{2}$
is the base of an $a$-side triangle associated with $0$-length edge $uv$.

Note that we include $0$-length edges in cases 1 and 2 above. Altogether,
$\cal T$ contains $O(n+k)$ triples—at most one associated with each edge of
the trees, and at most two associated with each half-polygon $H\in{\cal H}$.

######  Lemma 13.

$\cal T$ is a coarse cover.

###### Proof.

There are three properties for a coarse cover. For each triple $(I,f,H)$ it is
clear that $I$ is a subinterval of $K$ and $f$ is defined on $I$—this is
property (1). For property (2), $f$ is defined to have one of the three forms.
Furthermore, we claim that for each triple $(I,f,H)$, and each $x\in I$,
$f(x)=d(x,H)$. This is clear for Case 0. For the other three Cases, the
triangle or trapezoid is part of the shortest path map $M(H)$, so the formula
for $f(x)$ matches the distance $d(x,H)$.

Finally, we must prove property (3). Let ${\cal T}^{0}$ be the initial large
coarse cover defined above, consisting of the set of triples $(I,f,H)$ from
Case 0 and the union of all the triples arising from the shortest path maps
$\\{M(H):H\in{\cal H}\\}$. Then ${\cal T}\subseteq{\cal T}^{0}$, and we must
show that no triple of ${\cal T}^{0}$ that is omitted from $\cal T$ causes a
violation of property (3). Any triple from the shortest path maps corresponds
to a triangle that arises in Case 1 or 2 (i.e., with the same $u,v,I$), or to
a trapezoid considered in Case 3. No trapezoids are omitted in $\cal T$, so it
suffices to consider Cases 1 and 2.

We first examine Case 1. Consider an edge $(u,v)$ in ${\bar{T}}_{a}$ where
$u=p_{a}(v)$ and $u$ and $v$ are both visible from $K$, and consider the
interval $I=[x_{a}(u),x_{a}(v)]$. Suppose that for some $f,H$, there is a
triple $(I,f,H)$ that is included in the triples from the shortest path maps,
but omitted from $\cal T$. Then there is a directed path in ${\bar{T}}_{a}$
from $v$ to a leaf corresponding to $H$, and $f(x)$ is
$d_{2}(x,u)+|uv|+\kappa$ where $\kappa$ is the length of the tree path from
$v$ to the leaf corresponding to $H$. But then $f(x)\leq
d_{2}(x,u)+|uv|+\ell_{a}(v)$, since $\ell_{a}(v)$ is the maximum distance from
$v$ to a leaf corresponding to farthest half-polygon $F_{a}(v)$. If the
inequality is strict, then $H$ is not a farthest half-polygon from any $x\in
I$ so property (3) is satisfied without the triple $(I,f,H)$. And if equality
holds, then property (3) allows us to omit the triple $(I,f,H)$ since the
triple $(I,f,F_{a}(v))$ has the same $I$ and $f$. The case of triples omitted
in Case 2 is similar. ∎

####  4.1.4 Finding the Relative Geodesic Center on a Chord

The last step of the chord oracle is exactly the same as in Pollack et al.
[28]. Given a chord $K$ and the coarse cover $\cal T$ from Section 4.1.3—which
provides a set of $O(n+k)$ functions whose upper envelope is the geodesic
radius function on chord $K$—we want to find the relative center, $c_{K}$,
that minimizes the geodesic radius function. Pollack et al. use a technique of
Megiddo’s to do this in $O(n+k)$ time by recursively reducing to a smaller
subinterval of $K$ while eliminating elements of the coarse cover whose
functions are strictly dominated by others. In brief, the idea is to pair up
the functions, define a set of at most 6 “extended intersection points” for
each pair, and test medians of those points in order to restrict the search to
a subinterval of $K$ and eliminate a constant fraction of the functions.
Testing median points is done via the test from Section 4.1.1 of whether the
relative center is left/right of a query point $x$ on $K$. This test depends
on having the first segments of the shortest paths from $x$ to its farthest
half-polygons. Observe that the initial coarse cover from Section 4.1.3
captures these segments, and they are preserved throughout the recursion
because only strictly dominated functions are eliminated.

We fill in a bit more detail. In each round we have a subinterval $K^{\prime}$
of $K$ that contains $c_{K}$ and a subset ${\cal T}^{\prime}$ of the coarse
cover $\cal T$ such that any function omitted from ${\cal T}^{\prime}$ is
strictly dominated on interval $K^{\prime}$ by a function of ${\cal
T}^{\prime}$. We want to eliminate a constant fraction of ${\cal T}^{\prime}$
in time $O(|{\cal T}^{\prime}|)$. We pair up the functions of ${\cal
T}^{\prime}$. Consider a pair of functions $f_{1}$ and $f_{2}$. Each function
is defined on a subinterval of $K$ and we define it to be $-\infty$ outside
its interval. The upper envelope of $f_{1}$ and $f_{2}$ switches between
$f_{1}$ and $f_{2}$ at extended intersection points which include the points
where $f_{1}$ and $f_{2}$ intersect (are equal), and also possibly the
endpoints of their intervals. If a subinterval of $K$ does not contain an
extended intersection point for $f_{1}$ and $f_{2}$, then one of $f_{1},f_{2}$
is irrelevant because it is dominated by the other (or both are $-\infty$). We
know from Section 4.1.3 that each function has the form $f(x)=0$ or
$f(x)=d_{2}(x,s)+\kappa$ where $\kappa$ is a constant, $d_{2}$ is Euclidean
distance, and $s$ is a point or line. This implies that there are at most two
intersection points of the functions $f_{1}$ and $f_{2}$, and thus at most six
extended intersection points. In fact, a closer examination shows that there
are at most four extended intersection points.

Pollack et al. show how to successively test three medians of extended
intersections in order to reduce the interval $K^{\prime}$ and eliminate a
constant fraction of the functions of ${\cal T}^{\prime}$. The first median
test reduces the domain to a subinterval containing half the extended
intersections, so three successive median tests reduce the domain to a
subinterval containing one eighth of the extended intersections. This implies
that for at least half the pairs $f_{1},f_{2}$, all four of their extended
intersections lie outside the domain, and one of $f_{1},f_{2}$ is dominated by
the other and can be eliminated.

This completes one round of their procedure, with a runtime of $O(|{\cal
T}^{\prime}|)$. When ${\cal T}^{\prime}$ is reduced to constant size, the
relative center $c_{K}$ can be found directly. The total run time is then
$O(n+k)$.

###  4.2 Finding the Geodesic Center of Half-Polygons

In this section we show how to use the $O(n+k)$ time chord oracle from Section
4.1 to find the geodesic center of the $k$ half-polygons in
$O((n+k)\log(n+k))$ time. The basic structure of the algorithm is the same as
that of Pollack et al. [28].

In the first step we use the chord oracle to restrict the search for the
geodesic center to a small region where the problem reduces to a Euclidean
problem of finding a minimum radius disk that intersects some half-planes and
contains some disks. This step takes $O((n+k)\log(n+k))$ time. In the second
step we solve the resulting Euclidean problem in linear time, which involves
some new ingredients to handle our case of half-polygons.

####  4.2.1 Finding a Region that Contains the Geodesic Center

Triangulate $P$ in linear time [8]. Choose a chord of the triangulation that
splits the polygon into two subpolygons so that the number of triangles on
each side is balanced (the dual of a triangulation is a tree of maximum degree
3, which has a balanced cut vertex). Run the chord oracle on this chord, and
recurse in the appropriate subpolygon. In $O(\log n)$ iterations, we narrow
our search down to one triangle $T^{*}$ of the triangulation. This step takes
$O((n+k)\log n)$ time.

Next, we refine $T^{*}$ to a region $R$ that contains the center and such that
$R$ is homogeneous, meaning that for any $H\in\cal H$ the shortest paths from
points in $R$ to $H$ have the same combinatorial structure, i.e., the same
sequence of polygon vertices along the path.

The idea is to subdivide $T^{*}$ by $O(n+k)$ lines so that each cell in the
resulting line arrangement is homogeneous, and then to find the cell
containing the center. Construct the shortest path trees to $\cal H$ from each
of the three corners of triangle $T^{*}=(a^{*},b^{*},c^{*})$ using the
algorithm of Section 4.1.2. For each edge $(u,v)$ of each tree, add the line
through $uv$ if it intersects $T^{*}$. (In fact, we do not need all these
lines—as in the construction of the coarse cover in Section 4.1.3, it suffices
to use tree edges $(u,v)$ such that $u$ is visible from an edge of $T^{*}$.)
We add three more lines for each half-polygon $H\in{\cal H}$, specifically,
the chord $h$ that defines $H$, and the two lines perpendicular to $h$ through
the endpoints of $h$. The result is a set $L$ of $O(n+k)$ lines that we obtain
in time $O(n+k)$. It is easy to see that the resulting line arrangement has
homogeneous regions.

All that remains is to find the cell of the arrangement that contains the
geodesic center. It is simpler to state the algorithm in terms of
$\epsilon$-nets instead of the rather involved description of Megiddo’s
technique used by Pollack et al. [28].  For background on $\epsilon$-nets see
the survey by Mustafa and Varadarajan [30, Chapter 47] or the book by Mustafa
[25]. The high-level idea is to define a range space with ground set $L$ and
to find a constant-sized $\epsilon$-net in time $O(|L|)$. Then the lines of
the $\epsilon$-net divide our region into a constant number of subregions and
we can find which subregion contains the geodesic center by applying the chord
oracle $O(1)$ times. By the property of $\epsilon$-nets the subregion is
intersected by only a constant fraction of the lines of $L$, so repeating this
step for $O(\log(n+k))$ times, we arrive at a region $R$ with the required
properties.

We fill in a bit more detail. The range space has ground set $L$. To define
the ranges, let $\mathcal{T}$ be the (infinite) set of all triangles contained
in $T^{*}$. For $t\in\mathcal{T}$, let $\Delta_{t}=\\{\ell\in L:\ell\ {\rm
intersects}\ t\\}$. Let $\Delta=\\{\Delta_{t}:t\in{\cal T}\\}$. Then the range
space is $S=(L,\Delta)$. To show that constant-sized $\epsilon$-nets exist, we
must show that $S$ has constant VC-dimension, or constant shattering
dimension. We argue that the shattering dimension is 6, i.e., that for any
subset $L^{\prime}$ of $L$ of size $m$ the number of ranges is $O(m^{6})$. The
lines intersecting a triangle $t$ are the same as the lines intersecting the
convex hull of the three cells of the arrangement of $L^{\prime}$ that contain
the endpoints of $t$. There are $O(m^{2})$ cells in the arrangement and we
choose three of them, giving the bound of $O(m^{6})$ possible ranges. Thus, a
constant sized $\epsilon$-net of size
$O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon}))$ exists for our range space. In
order to construct an $\epsilon$-net in deterministic $O(|L|)$ time, we need a
subspace oracle that, given a subset $L^{\prime}$ of $L$ of size $m$, computes
the set of ranges of $L^{\prime}$ in time proportional to the output size,
$O(m^{6+1})$. Begin by finding, for each line in $L^{\prime}$, which cells of
the arrangement lie to each side of the line. Then, for every choice of three
cells (there are $O(m^{6})$ choices), the lines intersecting their convex hull
can be listed in time $O(m)$ time.

For the algorithm, we choose $\epsilon=\frac{1}{2}$, and construct an
$\epsilon$-net $N$. Triangulate each cell of the arrangement of $N$—this is a
constant time operation since the arrangement has constant complexity. We can
locate the triangle $T^{\prime}$ of this triangulated arrangement that
contains the visibility center in $O(n+k)$ time by running the chord oracle a
constant number of times. By the $\epsilon$-net property, no more than
$\epsilon\cdot|L|$ lines of $L$ intersect the interior of $T^{\prime}$. Thus,
in $O(|L|)$ time, we have halved the number of lines going through our domain
of interest (the region that contains the geodesic center). Repeating the same
sequence of steps $O(\log|L|)=O(\log(n+k))$ times, we will arrive at a
triangle containing a constant number of these lines. At this point, a brute
force method suffices to locate a region $R$ that satisfies the properties
stated in the beginning of this section.

In each iteration of the process, we apply the $O(n+k)$ chord oracle a
constant number of times and thus the total runtime for this step is
$O((n+k)\log(n+k))$.

####  4.2.2 Solving an Unconstrained Problem

At this point, we have a homogeneous polygonal region $R$ that contains a
geodesic center of the set $\mathcal{H}$ of half-polygons. Our goal is to find
the point $x\in R$ that minimizes the maximum over $H\in{\cal H}$ of $d(x,H)$.
We give a linear time algorithm (in this final step there is no need for an
extra logarithmic factor). We show that the problem reduces to one in the
Euclidean plane, i.e., the polygon no longer matters. Pick an arbitrary point
$p$ in $R$ and find the shortest path tree from $p$ to all half-polygons (this
takes linear time). If $p$ has distance 0 to half-polygon $H$, then the same
is true for all points in $R$, so $H$ is irrelevant and can be discarded. If
$\pi(p,H)$ consists of a single line segment that reaches an internal point of
the chord defining $H$ (we denote these half-polygons by ${\cal H}_{1}$), then
$d(x,H)=d_{2}(x,{\bar{H}})$ for all $x\in R$, where $\bar{H}$ is the half-
plane defined by $H$. And if the first segment of $\pi(x,H)$ reaches a vertex
$u$ (we denote these half-polygons by ${\cal H}_{2}$), then
$d(x,H)=d_{2}(x,u)+\kappa$ for all $x\in R$, where $\kappa$ is a constant.
Thus we seek a point $x=(x_{1},x_{2})$ and a value $\rho$ to solve:

$\begin{array}[]{ll@{}ll}\text{minimize}&\rho&\\\ \text{subject
to}&d_{2}(x,{\bar{H}})\leq\rho&H\in{\cal H}_{1}\\\
&d_{2}(x,u)+\kappa\leq\rho&\text{ for point $u$ and constant $\kappa$
corresponding to }H\in{\cal H}_{2}\\\ \end{array}$

Because $x$ is guaranteed to lie in the region $R$, we can completely
disregard the underlying polygon $P$ in solving the problem.

In the Euclidean plane, the problem may be reinterpreted in a geometric
manner. We wish to find the disk of smallest radius $\rho$ that intersects
each of a given set of half-planes and contains each of a given set of disks.
For $H\in{\cal H}_{1}$, we have $d(x,H)\leq\rho$ if and only if the disk of
radius $\rho$ centered at $x$ intersects $\bar{H}$. For $H\in{\cal H}_{2}$,
with $d(x,H)=d_{2}(x,u)+\kappa$, we have $d(x,H)\leq\rho$ if and only if the
disk of radius $\rho$ centered at $x$ contains the disk of radius $\kappa$
centered at $u$.  We will call this Euclidean problem the “minimum feasible
disk” problem. The constraints of the problem that correspond to the set of
half-polygons ${\cal H}_{1}$ will be referred to as half-plane constraints,
while the constraints for ${\cal H}_{2}$ will be called disk constraints.

We observe here that the minimum feasible disk problem belongs to the class of
‘LP-type’ problems described by Sharir and Welzl [29]. In fact, it satisfies
the computational assumptions that allow a derandomization of the Sharir-Welzl
algorithm yielding a deterministic linear-time algorithm for the problem (see
Chazelle and Matousek [9]). However, as this approach is rather complex, we
will outline a more direct linear-time algorithm to solve the problem.

The minimum feasible disk problem is a combination of two well-known problems
that have linear time algorithms. If all the constraints are half-plane
constraints, then, because each such constraint can be written as a linear
inequality, we have a 3-dimensional linear program, which can be solved in
linear time as shown by Meggido [22] and independently by Dyer [14]. On the
other hand, if all the constraints are disk constraints, then this is the
“spanning circle problem”—to find the smallest disk that contains some given
disks. This problem arose from the geodesic vertex center problem [28] and
generalizes the Euclidean 1-center problem where the disks degenerate to
points. The problem was solved in linear time by Megiddo [24] using an
approach similar to that for the 1-center problem and for linear programming.
Because the approaches are similar, it is not difficult to combine them, as we
show below.

We begin by describing the main idea of Megiddo’s prune-and-search approach
for both linear programming in 3D and for the spanning circle problem (also
see the survey by Dyer et al. in the Handbook of Discrete and Computational
Geometry [13, Chapter 49]). The goal is to spend linear time to prune away a
constant fraction of the constraints that do not define the final answer, and
to repeat this until there are only a constant number of constraints left,
after which a brute force method may be employed. The idea is to pair up the
constraints, and for each pair of constraints $c_{1},c_{2}$ compute a
“bisecting” plane $\Pi$ such that on one side of the $\Pi$ the constraint
$c_{1}$ is redundant, and on the other side of $\Pi$ the constraint $c_{2}$ is
redundant. If we could identify which side of $\Pi$ contains the optimum
solution, then one of the constraints $c_{1},c_{2}$ can be removed. We address
the existence of such bisecting planes below. There are two other issues.
Issue 1 is to identify which side of a plane contains the optimum solution, a
subproblem that Megiddo calls an “oracle”. This is done by finding the optimum
point restricted to the plane (a problem one dimension down), from which the
side of the plane can be decided. (The Chord Oracle from Section 4.1 was doing
a similar thing.) Issue 2 is to identify the position of the optimum point
relative to “many” of the bisecting planes, while testing only a “small”
sample of them—this can be done using _cuttings_. We will not discuss these
two issues since they are the same as in Megiddo’s papers [22, 23] (or see the
survey by Dyer et al. [13]).

For our minimum feasible disk problem, we have two types of constraints—half-
plane constraints and disk constraints. Megiddo’s prune-and-search approach
based on pairing up the constraints can still be applied so long as we pair
each constraint with another constraint of the same type. (We note that this
idea was previously used by Bhattacharya et al. [7] in their linear time
algorithm to find the smallest disk that contains some given points and
intersects some lines, a problem they call the “intersection radius problem”.)
Thus it suffices to describe what are the bisecting planes for the two types
of constraints in our minimum feasible disk problem.

A half-plane constraint has the form $d_{2}(x,{\bar{H}})\leq\rho$. If the
halfplane $\bar{H}$ is given by $a_{i}^{T}x\leq b_{i}$, normalized so that
$||a_{i}||=1$, then the constraint is $a_{i}^{T}x\leq b_{i}+\rho$, a linear
inequality. For two such constraints indexed by $i$ and $j$, the bisecting
plane is given by $(a_{i}^{T}-a_{j}^{T})x-(b_{i}-b_{j})=0$.

A disk constraint has the form $d_{2}(x,u_{i})+\kappa_{i}\leq\rho$,
corresponding to a disk with center $u_{i}$ and radius $\kappa_{i}$. As
Megiddo [24] noted, by adding the constraint $\rho\geq\kappa_{i}$, this can be
written as

$||x-u_{i}||^{2}\leq(\rho-\kappa_{i})^{2}$

or as

$f_{i}(x,\rho)\leq 0$

where $f_{i}$ is defined as

$f_{i}(x,\rho)=||x||^{2}-2u_{i}^{T}x+||u_{i}||^{2}-\rho^{2}+2\kappa_{i}\rho-\kappa_{i}^{2}.$

This is not a linear constraint, but for $i\neq j$, the equation
$f_{i}(x,\rho)=f_{j}(x,\rho)$ defines a plane since the quadratic terms,
$||x||^{2}$ and $\rho^{2}$, cancel out. So the bisecting plane is
$f_{i}(x,\rho)=f_{j}(x,\rho)$.

This completes the summary of how to solve the minimum feasible disk problem
in linear time, and completes our algorithm to find the geodesic center of
half-polygons.

##  5 Conclusions

We introduced the notion of the visibility center of a set of points in a
polygon and gave an algorithm with run time $O((n+m)\log(n+m))$ to find the
visibility center of $m$ points in an $n$-vertex polygon. To do this, we gave
an algorithm with run time $O((n+k)\log(n+k))$ to find the geodesic center of
a given set of $k$ half-polygons inside a polygon, a problem of independent
interest. We conclude with some open questions.

Can the visibility center of a simple polygon be found more efficiently? Note
that the geodesic center of the vertices of a simple polygon can be found in
linear time [1]. Our current method involves ray shooting and sorting (Section
3 and the preprocessing in Section 4) , which are serious barriers. A more
reasonable goal is to find the visibility center of $m$ points in a polygon in
time $O(n+m\log m)$.

Is there a more efficient algorithm to find the geodesic center of (sorted)
half-polygons? In forthcoming work we give a linear time algorithm for the
special case of finding the geodesic center of the _edges_ of a polygon (this
is the case where the half-polygons hug the edges).

How hard is it to find the farthest visibility Voronoi diagram of a polygon?
Finally, what about the 2-visibility center of a polygon, where we can deploy
two guards instead of one?

## References

  * [1] Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman, and Eunjin Oh.  A linear-time algorithm for the geodesic center of a simple polygon.  Discrete & Computational Geometry, 56(4):836–859, 2016.  doi:10.1007/s00454-016-9796-0.
  * [2] Esther M Arkin, Alon Efrat, Christian Knauer, Joseph S B Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie.  Shortest path to a segment and quickest visibility queries.  Journal of Computational Geometry, 7:77–100, 2016.  URL: https://jocg.org/index.php/jocg/article/view/3001, doi:10.20382/jocg.v7i2a5.
  * [3] Boris Aronov, Steven Fortune, and Gordon Wilfong.  The furthest-site geodesic Voronoi diagram.  Discrete & Computational Geometry, 9(3):217–255, 1993.  doi:10.1007/bf02189321.
  * [4] Franz Aurenhammer, Robert L Scot Drysdale, and Hannes Krasser.  Farthest line segment Voronoi diagrams.  Information Processing Letters, 100(6):220–225, 2006.  doi:10.1016/j.ipl.2006.07.008.
  * [5] Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee.  Voronoi Diagrams and Delaunay Triangulations.  World Scientific Publishing Company, 2013.  doi:10.1142/8685.
  * [6] Luis Barba.  Optimal algorithm for geodesic farthest-point Voronoi diagrams.  In 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.SoCG.2019.12.
  * [7] Binay K Bhattacharya, Shreesh Jadhav, Asish Mukhopadhyay, and J-M Robert.  Optimal algorithms for some intersection radius problems.  Computing, 52(3):269–279, 1994.  doi:10.1007/bf02246508.
  * [8] Bernard Chazelle.  Triangulating a simple polygon in linear time.  Discrete & Computational Geometry, 6(3):485–524, 1991.  doi:10.1007/bf02574703.
  * [9] Bernard Chazelle and Jiri Matousek.  On linear-time deterministic algorithms for optimization problems in fixed dimension.  Journal of Algorithms, 21(3):579–597, 1996.  doi:10.1006/jagm.1996.0060.
  * [10] Wei-Pang Chin and Simeon Ntafos.  Shortest watchman routes in simple polygons.  Discrete & Computational Geometry, 6(1):9–31, 1991.  doi:10.1007/bf02574671.
  * [11] Hristo N Djidjev, Andrzej Lingas, and Jörg-Rüdiger Sack.  An ${O}(n\log n)$ algorithm for computing the link center of a simple polygon.  Discrete & Computational Geometry, 8(2):131–152, 1992.  doi:10.1007/bf02293040.
  * [12] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S B Mitchell.  Touring a sequence of polygons.  In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003), pages 473–482, 2003.  doi:10.1145/780542.780612.
  * [13] Martin Dyer, Bernd Gärtner, Nimrod Megiddo, and Emo Welzl.  Linear programming.  In Csaba D. Tóth Jacob E. Goodman, Joseph O’Rourke, editor, Handbook of Discrete and Computational Geometry, pages 1291–1309. Chapman and Hall/CRC, 2017.  doi:10.1201/9781420035315.pt6.
  * [14] Martin E. Dyer.  Linear time algorithms for two- and three-variable linear programs.  SIAM Journal on Computing, 13(1):31–45, 1984.  doi:10.1137/0213003.
  * [15] Subir Kumar Ghosh.  Visibility Algorithms in the Plane.  Cambridge University Press, 2007.  doi:10.1017/cbo9780511543340.
  * [16] Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E Tarjan.  Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.  Algorithmica, 2(1-4):209–233, 1987.  doi:10.1007/bf01840360.
  * [17] Leonidas J Guibas and John Hershberger.  Optimal shortest path queries in a simple polygon.  Journal of Computer and System Sciences, 39(2):126–152, 1989.  doi:10.1016/0022-0000(89)90041-x.
  * [18] John Hershberger and Subhash Suri.  A pedestrian approach to ray shooting: Shoot a ray, take a walk.  Journal of Algorithms, 18(3):403–431, 1995.  doi:10.1006/jagm.1995.1017.
  * [19] Shreesh Jadhav, Asish Mukhopadhyay, and Binay Bhattacharya.  An optimal algorithm for the intersection radius of a set of convex polygons.  Journal of Algorithms, 20(2):244–267, 1996.  doi:10.1006/jagm.1996.0013.
  * [20] Yan Ke and Joseph O’Rourke.  Computing the kernel of a point set in a polygon.  In Workshop on Algorithms and Data Structures (WADS 1989), pages 135–146. Springer, 1989.  doi:10.1007/3-540-51542-9_12.
  * [21] Der-Tsai Lee and Franco P Preparata.  An optimal algorithm for finding the kernel of a polygon.  Journal of the ACM (JACM), 26(3):415–421, 1979.  doi:10.1145/322139.322142.
  * [22] Nimrod Megiddo.  Linear-time algorithms for linear programming in ${R}^{3}$ and related problems.  SIAM Journal on Computing, 12(4):759–776, 1983.  doi:10.1137/0212052.
  * [23] Nimrod Megiddo.  Linear programming in linear time when the dimension is fixed.  Journal of the ACM (JACM), 31(1):114–127, 1984.  doi:10.1145/2422.322418.
  * [24] Nimrod Megiddo.  On the ball spanned by balls.  Discrete & Computational Geometry, 4(6):605–610, 1989.  doi:10.1007/bf02187750.
  * [25] Nabil H Mustafa.  Sampling in Combinatorial and Geometric Set Systems, volume 265 of Mathematical Surveys and Monographs.  American Mathematical Society, 2022.  doi:10.1090/surv/265.
  * [26] Eunjin Oh and Hee-Kap Ahn.  Voronoi diagrams for a moderate-sized point-set in a simple polygon.  Discrete & Computational Geometry, 63(2):418–454, 2020.  doi:10.1007/s00454-019-00063-4.
  * [27] Eunjin Oh, Luis Barba, and Hee-Kap Ahn.  The geodesic farthest-point Voronoi diagram in a simple polygon.  Algorithmica, 82(5):1434–1473, 2020.  doi:10.1007/s00453-019-00651-z.
  * [28] Richard Pollack, Micha Sharir, and Günter Rote.  Computing the geodesic center of a simple polygon.  Discrete & Computational Geometry, 4(6):611–626, 1989.  doi:10.1007/bf02187751.
  * [29] Micha Sharir and Emo Welzl.  A combinatorial bound for linear programming and related problems.  In Annual Symposium on Theoretical Aspects of Computer Science (STACS 1992), pages 567–579. Springer, 1992.  doi:10.1007/3-540-55210-3_213.
  * [30] Csaba D Toth, Joseph O’Rourke, and Jacob E Goodman, editors.  Handbook of Discrete and Computational Geometry.  CRC press, 2017.  doi:10.1201/9781315119601.
  * [31] Godfried T Toussaint.  Computing geodesic properties inside a simple polygon.  Revue d’Intelligence Artificielle, 3(2):9–42, 1989.  URL: https://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=6661941.
  * [32] Haitao Wang.  Quickest visibility queries in polygonal domains.  Discrete & Computational Geometry, 62(2):374–432, 2019.  doi:10.1007/s00454-019-00108-8.
  * [33] Haitao Wang.  An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons.  In 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.SoCG.2021.59.