# Computing the Geodesic Center of a Simple Polygon 1000800311

of 34

date post

06-Jul-2018Category

## Documents

view

218download

0

Embed Size (px)

### Transcript of Computing the Geodesic Center of a Simple Polygon 1000800311

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

1/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

2/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

3/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

4/34

http://www.forgottenbooks.com/redirect.php?where=fb&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=it&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=es&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=fr&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=de&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=co.uk&pibn=1000800311 http://www.forgottenbooks.com/redirect.php?where=com&pibn=1000800311

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

5/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

6/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

7/34

Robotics Research lischnical

Report

^ 4,.., ' '^C/7,

r)^

j^ - -1 ii ']*V''-* ni%f'?.\'̂ ' il'W^

^ ox; (0

H -H ^

to 2

Computing the Geodesic Center of a Simple Polygon

by

R. Pollack

M. Sharir

Technical Report No. 231

Robotics Report No. 74

July, 1986

S j^ M W

g o o o

New York University It Institute of Mathematical Sciences

Computer Science Division

251 Mercer Street NewYork,N.Y 10012

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

8/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

9/34

Computing the Geodesic Center of a Simple Polygon

by

R. Pollack

M. Sharir

Technical Report No. 231

Robotics Report No. 74

July, 1986

New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012

Work on

this paper by the first author has been supported by National Science Foundation

Grant DMS-8501947. Work on this paper by the second author has been supported by Office

of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-

DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM

Corporation. Part of the work on this paper has been carried out at the Workshop on

Movable Separability of Sets at the Billairs Research Institute of McCiill University.

Barbados, Feb. 1986.

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

10/34

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

11/34

Computing the Geodesic Center of a Simple Polygon

R. Pollack (^) and M. Sharir (^'^^

^ ' Courant Institute of Mathematical Sciences

New York University

and

^ ' School of Mathematical Sciences

Tel Aviv University

ABSTRACT

The geodesic center of a simple polygon is a point inside the

polygon which minimizes the maximum internal distance to any

point in the

polygon. We

present an

algorithm which calculates

the geodesic center of a simple polygon with n vertices in time

1. Introduction

The problem addressed in this paper, to locate the point inside a simple

polygon P whose maximal internal distance (by a route inside P) from any

point inside P is minimal, is a generalization of the Euclidean facility location

problem which asks for the location of the point (facility) hich is least far

(in the Euclidean metric) from the furthest of a finite set of points (the

community which the facility is to serve) [Me], [Dy]. Indeed, since the

furthest point from a point inside a polygon is always a vertex of the

polygon, the geodesic center of the convex hull of the community to be

served is the solution to the standard facility location problem. We can

consider the problem of finding the geodesic center as another kind of

constrained facility location problem where we want e.g. to locate an

emergency service on a polygonal island or a nurses station on a polygonal

hospital floor. See Fig. 1 for an illustration of the geodesic center problem.

The standard Euclidean facility location problem can be solved in time 0{n)

([Me], [Dy]), but its extension to the problem of finding the geodesic center

of a simple polygon appears to be more difficult.

Work on this paper by the first author has been supported by National Science Foundation Grant

DMS-8501947, Work on this paper by the second author has been supported by Office of Naval

Research Grant N(X)014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and

by grants from the Digital Equipment Corporation, and the IBM Corporation. Part of the work on this

paper has been carried out at the Workshop on Movable Separabihty of Sets at the Bellairs Research

Institute of McGill University, Barbados, February 1986.

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

12/34

-2-

The problem of computing the geodesic center of a simple polygon has

been considered by T. Asano and G. Toussaint [AT]. They show that the

geodesic center is unique and present an algorithm to compute it in time

0{nHog n), where n is the number of vertices in the given polygon. The main idea of their algorithm is to construct the geodesic furthest-point

Voronoi diagram of the vertices of the polygon and then to locate the

geodesic center at either a vertex of the Voronoi diagram or at the midpoint of a geodesic diameter (i e. s shortest path inside the polygon joining two vertices which has maximal length over all choices of pairs of vertices). e will also use the term geodesic iameter to denote the length of that path. There have been

many algorithms to find the geodesic diameter of a simple

polygon. The best result at the present time is an 0(n log n) time and 0(n)

space algorithm due to S. Suri [Su].

A related problem is to compute the link diameter and the link center of

a simple polygon, where the link distance between two points is the minimum number of edges in a polygonaa path joining them inside the polygon and where the link center and diametei are defined in an analogous manner to the definition of geodesic center drid diameter. In this case the link center is no

longer unique but consists of a polygon wliich may be as large as the entire

given polygon. Suri [Su2] has an 0(n iog^/i) ime and 0{n) space algorithm which computes the hnk diameter of a simple polygon and [Lea] presents an O(n^) algorithm for computing the link center of a simple polygon. Suri and El-Gindy (private communication) also report similarly fficient algorithms for computing the link center.

Our algorithm proceeds as follows. We start with a triangulation f the

polygon P, then perform something

like a binary

search through

the

diagonals of the triangulation, etermining at each tested diagonal, via the

algorithm RELCEN to be describe in Section 3 below, on which side of that

diagonal the geodesic center lies. In this way we locate a triangle which contains the geodesic center. However, as we move around in this triangle the combinatorial structure of the shortest path to a given vertex can change. We next use a modification of Megiddo's method for doing linear

programming in linear time [Me] to find a polygon R within this triangle

where the structure of the path from each point x ^ R to each vertex v of P remains constant, and consists of the straight egment from x to some, possibly different, ertex followed by a fixed path of known length to v. In other words, in our final subregion R, the internal distance from a point x to the j-th vertex of P has a fixed analytic expression of the form [xw,|+c,, or 1 = 1,2,

. . . ,n. The problem that remains is equivalent to that of finding a smallest circle that contains a given collection of n circles (where the z-th circle is centered at u, and has radius c,). This final task is accomplished by

8/18/2019 Computing the Geodesic Center of a Simple Polygon 1000800311

13/34

-3-

another technique of Megiddo [Me2] for deriving efficient sequential

optimization lgorithms from parallel lgorithms.

The total time complexity of our algorithm is 0{n log^n). he final stage (that of finding the smallest spanning circle of circles), hich may be of

independent interest in location theory, runs in time 0{n log n loglog n).

The paper is organized as follows. In section 2 we present the geometric

preliminaries eeded to justify he algorithm RELCEN which is presented in

section 3. In section 4 we present the complete algorithm, nd concluding remarks are given in Section 5.

i

2. Geometric Preliminaries

Definitions. Let P be a simple polygon with n vertices (more precisely is a closed simply-connected planar region whose boundary is a given simple

pol