2026-07-21T23:58:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6051 2024-03-06T10:37:32Z ddc:004 open_access

Constrained Geodesic Centers of a Simple Polygon Oh, Eunjin Son, Wanbin Ahn, Hee-Kap Geodesic distance simple polygons constrained center facility location farthest-point Voronoi diagram For any two points in a simple polygon P, the geodesic distance between them is the length of the shortest path contained in P that connects them. A geodesic center of a set S of sites (points) with respect to P is a point in P that minimizes the geodesic distance to its farthest site. In many realistic facility location problems, however, the facilities are constrained to lie in feasible regions. In this paper, we show how to compute the geodesic centers constrained to a set of line segments or simple polygonal regions contained in P. Our results provide substantial improvements over previous algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh and Wanbin Son and Hee-Kap Ahn 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.29 urn:nbn:de:0030-drops-60516 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.29 eng https://creativecommons.org/licenses/by/3.0/legalcode