{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia55iovibjvw43agcfgwudflolhu46zab75ye64t576weao5o4zkm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mlkmadv7la52"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.07882v1",
  "publishedAt": "2026-05-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Katrin Casel",
    "Sándor Kisfaludi-Bak",
    "Linda Kleist",
    "Jeroen S. K. Lamme",
    "Eunjin Oh",
    "Yanheng Wang"
  ],
  "textContent": "**Authors:** Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S. K. Lamme, Eunjin Oh, Yanheng Wang\n\nWe study the problem of computing a shortest tour that visits a sequence of $k$ polygons $P_1,\\dots, P_k$ with a total number of $n$ vertices. A tour is an oriented curve such that there exist points $p_i\\in 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_2$ distance, and gave $\\widetilde O(nk)$ and $\\widetilde O(nk^2)$ algorithms for disjoint and intersecting convex polygons, respectively. This paper considers the orthogonal setting, where the input polygons have axis-aligned edges and the distance metric is the Manhattan distance. We obtain the following results: - as our main contribution, a truly subquadratic $\\widetilde O(n^{2-\\frac{1}{48}})$ algorithm when consecutive polygons in the sequence are disjoint; - an $\\widetilde O(n)$ algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an $O(n)$ algorithm for axis-aligned rectangles; - $\\widetilde O(n^2)$ and $\\widetilde O(n^{1.5}k^2)$ 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.",
  "title": "Touring a Sequence of Orthogonal Polygons"
}