DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.50

Touring a Sequence of Orthogonal Polygons

Authors: Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S.K. Lamme, Eunjin Oh, and Yanheng Wang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S.K. Lamme, Eunjin Oh, and Yanheng Wang. Touring a Sequence of Orthogonal Polygons. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 50:1-50:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{casel_et_al:LIPIcs.ICALP.2026.50,
  author =	{Casel, Katrin and Kisfaludi-Bak, S\'{a}ndor and Kleist, Linda and Lamme, Jeroen S.K. and Oh, Eunjin and Wang, Yanheng},
  title =	{{Touring a Sequence of Orthogonal Polygons}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{50:1--50:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.50},
  URN =		{urn:nbn:de:0030-drops-264391},
  doi =		{10.4230/LIPIcs.ICALP.2026.50},
  annote =	{Keywords: shortest path, subquadratic time, dynamic planar distance oracle}
}

Search Results

Documents authored by Lamme, Jeroen S.K.

Touring a Sequence of Orthogonal Polygons

Abstract

Cite as

Thanks for your feedback!

Could not send message