The Geodesic Diameter of Polygonal Domains

Sang Won Bae; Matias Korman; Yoshio Okamoto

doi:10.1007/s00454-013-9527-8

The Geodesic Diameter of Polygonal Domains

Sang Won Bae, Matias Korman, Yoshio Okamoto

Research output: Contribution to journal › Article › peer-review

17 Citations (Scopus)

Abstract

This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), 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 h ≥ 1, 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 O(n^7.73) or O(n⁷(log n + h)). 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.

Original language	English
Pages (from-to)	306-329
Number of pages	24
Journal	Discrete and Computational Geometry
Volume	50
Issue number	2
DOIs	https://doi.org/10.1007/s00454-013-9527-8
Publication status	Published - 2013 Sept
Externally published	Yes

Keywords

Convex function
Exact algorithm
Geodesic diameter
Lower envelope
Polygonal domain
Shortest path

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-013-9527-8

Cite this

@article{6b00ba6c49504788974be62662da4cb1,

title = "The Geodesic Diameter of Polygonal Domains",

abstract = "This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), 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 h ≥ 1, 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 O(n7.73) or O(n7(log n + h)). 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.",

keywords = "Convex function, Exact algorithm, Geodesic diameter, Lower envelope, Polygonal domain, Shortest path",

author = "Bae, {Sang Won} and Matias Korman and Yoshio Okamoto",

note = "Funding Information: We thank Hee-Kap Ahn, Jiongxin Jin, Christian Knauer, and Joseph Mitchell for fruitful discussion. We also thank Joseph O{\textquoteright}Rourke for pointing out the reference []. Work by S.W. Bae was supported by National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST) (No. 2010-0005974 and NRF-2013R1A1A1A05006927). M. Korman received the support of the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia, the European Union, and ESF EUROCORES Programme EuroGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306. Work by Y. Okamoto was supported by Global COE Program “Computationism as a Foundation for the Sciences” and Grant-in-Aid for Scientific Research from Ministry of Education, Science and Culture, Japan, and Japan Society for the Promotion of Science. ",

year = "2013",

month = sep,

doi = "10.1007/s00454-013-9527-8",

language = "English",

volume = "50",

pages = "306--329",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - The Geodesic Diameter of Polygonal Domains

AU - Bae, Sang Won

AU - Korman, Matias

AU - Okamoto, Yoshio

N1 - Funding Information: We thank Hee-Kap Ahn, Jiongxin Jin, Christian Knauer, and Joseph Mitchell for fruitful discussion. We also thank Joseph O’Rourke for pointing out the reference []. Work by S.W. Bae was supported by National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST) (No. 2010-0005974 and NRF-2013R1A1A1A05006927). M. Korman received the support of the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia, the European Union, and ESF EUROCORES Programme EuroGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306. Work by Y. Okamoto was supported by Global COE Program “Computationism as a Foundation for the Sciences” and Grant-in-Aid for Scientific Research from Ministry of Education, Science and Culture, Japan, and Japan Society for the Promotion of Science.

PY - 2013/9

Y1 - 2013/9

N2 - This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), 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 h ≥ 1, 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 O(n7.73) or O(n7(log n + h)). 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.

AB - This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), 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 h ≥ 1, 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 O(n7.73) or O(n7(log n + h)). 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.

KW - Convex function

KW - Exact algorithm

KW - Geodesic diameter

KW - Lower envelope

KW - Polygonal domain

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=84881613966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881613966&partnerID=8YFLogxK

U2 - 10.1007/s00454-013-9527-8

DO - 10.1007/s00454-013-9527-8

M3 - Article

AN - SCOPUS:84881613966

SN - 0179-5376

VL - 50

SP - 306

EP - 329

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

The Geodesic Diameter of Polygonal Domains

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this