A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

被引：15

作者：

Ahn, Hee-Kap ^{[1
]}

Barba, Luis ^{[2
,3
]}

Bose, Prosenjit ^{[2
]}

De Carufel, Jean-Lou ^{[2
]}

Korman, Matias ^{[4
]}

Oh, Eunjin ^{[1
]}

机构：

[1] POSTECH, Dept Comp Sci & Engn, 77 Cheongam Ro, Pohang, Gyeongbuk, South Korea

[2] Carleton Univ, Sch Comp Sci, Ottawa, ON, Canada

[3] Univ Libre Bruxelles, Dept Informat, Brussels, Belgium

[4] Tohoku Univ, Sendai, Miyagi, Japan

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2016年 / 56卷 / 04期

关键词：

Geodesic distance; Facility location; Simple polygons; LINK CENTER; DIAMETER;

D O I：

10.1007/s00454-016-9796-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let P be a closed 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 contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611-626, 1989) showed an -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.

引用

页码：836 / 859

页数：24

共 28 条

[1]

[Anonymous], SOCS8532 MCGILL U

[2] ON THE GEODESIC VORONOI DIAGRAM OF POINT SITES IN A SIMPLE POLYGON [J].

ARONOV, B .

ALGORITHMICA, 1989, 4 (01) :109-140

[3] THE FURTHEST-SITE GEODESIC VORONOI DIAGRAM [J].

ARONOV, B ;

FORTUNE, S ;

WILFONG, G .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (03) :217-255

[4]

Bae S.W., 2015, COMPUTATION IN PRESS

[5] Computing the L1 Geodesic Diameter and Center of a Polygonal Domain [J].

Bae, Sang Won ;

Korman, Matias ;

Mitchell, Joseph S. B. ;

Okamoto, Yoshio ;

Polishchuk, Valentin ;

Wang, Haitao .

33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47

[6] Computing the L1 geodesic diameter and center of a simple polygon in linear time [J].

Bae, Sang Won ;

Korman, Matias ;

Okamoto, Yoshio ;

Wang, Haitao .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (06) :495-505

[7] The Geodesic Diameter of Polygonal Domains [J].

Bae, Sang Won ;

Korman, Matias ;

Okamoto, Yoshio .

DISCRETE & COMPUTATIONAL GEOMETRY, 2013, 50 (02) :306-329

[8]

Chazelle B., 1982, 23rd Annual Symposium on Foundations of Computer Science, P339, DOI 10.1109/SFCS.1982.58

[9] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524

[10] AN 0(N-LOG-N) ALGORITHM FOR COMPUTING THE LINK CENTER OF A SIMPLE POLYGON [J].

DJIDJEV, HN ;

LINGAS, A ;

SACK, JR .

DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 8 (02) :131-152

← 1 2 3 →