Journal
DISCRETE & COMPUTATIONAL GEOMETRY
Volume 50, Issue 2, Pages 306-329Publisher
SPRINGER
DOI: 10.1007/s00454-013-9527-8
Keywords
Polygonal domain; Shortest path; Geodesic diameter; Exact algorithm; Convex function; Lower envelope
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available