Paper Info
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), it is known that the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time. 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 algorithm that computes the geodesic diameter of a given polygonal domain in worst-case time O(n7.73) or O(n7(log n+h)). Among other results, we show the following geometric observation: the geodesic diameter can be determined by two points in its interior. In such a case, there are at least five shortest paths between the points.
Year
DOI
Venue
2010
https://doi.org/10.1007/s00454-013-9527-8
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
Polygonal domain,Shortest path,Geodesic diameter,Exact algorithm,Convex function,Lower envelope
Conference
50
Issue
ISSN
ISBN
2
0179-5376
3-642-15774-2
Citations 
PageRank 
References 
5
0.51
17
Authors
3
Name
Order
Citations
PageRank
Sang Won Bae118931.53
Matias Korman217837.28
Yoshio Okamoto317028.50