2026-07-20T12:08:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26439 2026-07-01T07:16:10Z ddc:004 open_access

Touring a Sequence of Orthogonal Polygons Casel, Katrin Kisfaludi-Bak, Sándor Kleist, Linda Lamme, Jeroen S.K. Oh, Eunjin Wang, Yanheng shortest path subquadratic time dynamic planar distance oracle We study the problem of computing a shortest tour that visits a sequence of k polygons P₁,…,P_k with a total number of n vertices. A tour is an oriented curve such that there exist points p_i ∈ P_i for all i where p_i appears not after p_{i+1}. In a seminal paper, Dror, Efrat, Lubiw and Mitchell (STOC 2003) considered the problem under L₂ distance, and gave Õ(nk) and Õ(nk²) algorithms for disjoint and intersecting convex polygons, respectively. In this paper, we consider the orthogonal setting (with orthogonal polygons and Manhattan distance) and obtain the following results: - a truly subquadratic Õ(n^{2-1/48}) algorithm when consecutive polygons in the sequence are disjoint; - an Õ(n) algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an O(n) algorithm for axis-aligned rectangles; - Õ(n²) and Õ(n^{1.5}k²) algorithms without restrictions. Our algorithms build on a wide range of techniques, including additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles for weighted planar graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katrin Casel and Sándor Kisfaludi-Bak and Linda Kleist and Jeroen S.K. Lamme and Eunjin Oh and Yanheng Wang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.50 urn:nbn:de:0030-drops-264391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.50 eng https://creativecommons.org/licenses/by/4.0/legalcode