2026-04-18T05:57:07Zhttps://recercat.cat/oai/request

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

The geodesic diameter of polygonal domains Bae, SangWon Korman Cozzetti, Matías Okamoto, Yoshio Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II À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 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) 2013-09 Article Bae, S.; Korman, M.; Okamoto, Y. The geodesic diameter of polygonal domains. "Discrete and computational geometry", Setembre 2013, vol. 50, núm. 2, p. 306-329. 0179-5376 https://hdl.handle.net/2117/20279 10.1007/s00454-013-9527-8 eng Restricted access - publisher's policy 24 p. application/pdf