2026-07-24T18:14:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24265 2025-11-12T13:39:37Z ddc:004 open_access

Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains Hagedoorn, Mart Polishchuk, Valentin Minimum-link paths link distance diameter center radius 2-point distance queries We show how to preprocess a polygonal domain with holes so that the link distance (the number of links in a minimum-link path) between two query points in the domain can be reported efficiently. Using our data structures, the link diameter of the domain (i.e., the maximum number of links that may be required in a minimum-link path between two points in the domain) as well as the link center and radius of the domain (i.e., the point minimizing the maximum link distance to the furthest point in the domain and this maximum link distance) can be found in polynomial time. We also give a simpler algorithm for finding the link diameter, not using the link distance query structures. Answering 2-point link distance queries and computing the link diameter/radius/center in polygonal domains have been open questions since these problems were studied for simple polygons in the 90’s. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mart Hagedoorn and Valentin Polishchuk 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.34 urn:nbn:de:0030-drops-242659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.34 eng https://creativecommons.org/licenses/by/4.0/legalcode