2026-04-13T09:54:19Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/202792026-02-11T08:07:13Zcom_2072_1033col_2072_452950

00925njm 22002777a 4500 dc Bae, SangWon author Korman Cozzetti, Matías author Okamoto, Yoshio author 2013-09 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. Peer Reviewed Postprint (published version) Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional Computational geometry Convex function Exact algorithm Geodesic diameter Lower envelope Polygonal domain Shortest path Geometria computacional The geodesic diameter of polygonal domains