Handbook of DISCRETE AND COMPUTATIONAL GEOMETRY Page 1 i “K25063” — 2017/9/15
— 18:58 — page 811 — i i i 31 SHORTEST PATHS AND NETWORKS Joseph SB Mitchell …

Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions
the polygon into regions based on distances to sites under the geodesic metric. We present …

Given in the plane a set S of m point sites in a simple polygon P of n vertices, we consider
the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known …

Given a set of m point sites in a simple polygon, the geodesic nearest-point Voronoi diagram
of the sites partitions the polygon into m Voronoi cells, one cell per site, such that every point …

We present an algorithm that computes the geodesic center of a given polygonal domain.
The running time of our algorithm is O (n 12+ ϵ) for any ϵ> 0, where n is the number of …

Given a simple polygon P with n vertices and a set Q of m points in P, we consider the
geodesic k-center problem where we want to find k points, called centers, in P to minimize …

In the geodesic 2-center problem in a simple polygon with n vertices, we find a set S of two
points in the polygon that minimizes the maximum geodesic distance from any point of the …

Let P be a simple polygon with n vertices. For any two points in P, the geodesic distance
between them is the length of the shortest path that connects them among all paths …

We study various clustering problems for a set D of n points in a polygonal domain P under
the geodesic distance. We start by studying the discrete k-median problem for D in P. We …

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 …