The Geodesic Diameter of Polygonal Domains

被引：12

作者：

Bae, Sang Won ^{[1
]}

Korman, Matias ^{[2
]}

Okamoto, Yoshio ^{[3
]}

机构：

[1] Kyonggi Univ, Dept Comp Sci, Suwon, South Korea

[2] Univ Politecn Cataluna, Dept Matemat Aplicada 2, Barcelona, Spain

[3] Univ Electrocommun, Dept Commun Engn & Informat, Chofu, Tokyo 182, Japan

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2013年 / 50卷 / 02期

基金：

新加坡国家研究基金会; 日本学术振兴会;

关键词：

Polygonal domain; Shortest path; Geodesic diameter; Exact algorithm; Convex function; Lower envelope; SHORTEST-PATH QUERIES;

D O I：

10.1007/s00454-013-9527-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper studies the geodesic diameter of polygonal domains having holes and corners. For simple polygons (i.e., ), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with , however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time or . The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.

引用

页码：306 / 329

页数：24

共 21 条

[1] Star unfolding of a polytope with applications [J].

Agarwal, PK ;

Aronov, B ;

ORourke, J ;

Schevon, CA .

SIAM JOURNAL ON COMPUTING, 1997, 26 (06) :1689-1713

[2]

[Anonymous], SOCS8532 MCGILL U

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

ARONOV, B ;

FORTUNE, S ;

WILFONG, G .

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

[4] Querying two boundary points for shortest paths in a polygonal domain [J].

Bae, Sang Won ;

Okamoto, Yoshio .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2012, 45 (07) :284-293

[5]

Bae SW, 2010, LECT NOTES COMPUT SC, V6346, P500, DOI 10.1007/978-3-642-15775-2_43

[6] The Geodesic Farthest-Site Voronoi Diagram in a Polygonal Domain with Holes [J].

Bae, Sang Won ;

Chwa, Kyung-Yong .

PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, :198-207

[7]

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

[8]

Chiang YJ, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P215

[9]

Cook AF, 2009, LECT NOTES COMPUT SC, V5664, P156, DOI 10.1007/978-3-642-03367-4_14

[10] OPTIMAL SHORTEST-PATH QUERIES IN A SIMPLE POLYGON [J].

GUIBAS, LJ ;

HERSHBERGER, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 39 (02) :126-152

← 1 2 3 →