pith. machine review for the scientific record. sign in

arxiv: 2605.07882 · v2 · submitted 2026-05-08 · 💻 cs.CG · cs.DS

Recognition: 2 theorem links

· Lean Theorem

Touring a Sequence of Orthogonal Polygons

Eunjin Oh, Jeroen S.K. Lamme, Katrin Casel, Linda Kleist, S\'andor Kisfaludi-Bak, Yanheng Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-14 22:02 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords orthogonal polygonsshortest tourManhattan distancesequence of polygonssubquadratic algorithmVoronoi diagramscomputational geometry
0
0 comments X

The pith

A truly subquadratic algorithm computes shortest tours visiting sequences of disjoint orthogonal polygons.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops algorithms for computing a shortest oriented tour that visits a sequence of k orthogonal polygons in order under Manhattan distance. When consecutive polygons are disjoint it reaches truly subquadratic Õ(n^{2-1/48}) time. Special cases of disjoint ortho-convex polygons and axis-aligned rectangles admit Õ(n) and O(n) algorithms respectively. Without the disjointness assumption the running times are Õ(n²) or Õ(n^{1.5}k²). The methods rely on geometric diagrams and dynamic data structures to enforce the visit order while exploiting orthogonality.

Core claim

In the orthogonal setting with Manhattan distance the shortest tour visiting points p_i in each polygon P_i of a sequence can be found in Õ(n^{2-1/48}) time whenever consecutive polygons are disjoint. The same setting yields Õ(n) time for ortho-convex polygons and O(n) time for rectangles. General intersecting instances are solved in Õ(n²) time or Õ(n^{1.5}k²) time.

What carries the argument

Additively weighted Voronoi diagrams combined with rectangle decompositions, persistent data structures, and dynamic distance oracles on weighted planar graphs.

If this is right

  • Routing or inspection paths through separated rectangular regions become practical for large n under the disjointness condition.
  • Linear-time solutions exist for touring sequences of axis-aligned rectangles or ortho-convex shapes.
  • General sequences without disjointness still require near-quadratic time but improve when k is small.
  • The ordering constraint is handled by combining static geometric diagrams with dynamic shortest-path oracles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same geometric toolkit might yield subquadratic results for other distance measures once orthogonality is relaxed.
  • Grid-based path planning in manufacturing or VLSI routing could adopt the disjoint-case algorithm directly.
  • Further exponent improvements would follow from tighter analysis of the persistent structures or Voronoi diagram construction.

Load-bearing premise

Consecutive polygons are disjoint or the polygons belong to the restricted classes of ortho-convex shapes or axis-aligned rectangles.

What would settle it

A concrete sequence of n vertices forming disjoint consecutive orthogonal polygons whose shortest tour length differs from the length returned by the algorithm, or whose running time exceeds the stated bound.

Figures

Figures reproduced from arXiv: 2605.07882 by Eunjin Oh, Jeroen S.K. Lamme, Katrin Casel, Linda Kleist, S\'andor Kisfaludi-Bak, Yanheng Wang.

Figure 1
Figure 1. Figure 1: A tour visiting a sequence of five orthogonal polygons. All polygons but [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (Left) An illustration of a segment tree over [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The structure of the plane graph 𝐺 (𝑦) for a batch of three polygons 𝑃4, 𝑃5, 𝑃6. Active nodes are drawn as dots, and inactive nodes are drawn as crosses. Edges are oriented downwards, whose weights are omitted for clarity. It is clear from the construction that 𝐺 (𝑦) is planar. Note that |𝑆 | = 𝑂(𝑛 𝛼 · |𝑌 |) = 𝑂(𝑛), and Í𝑏 𝑖=𝑎 |𝑋𝑖 | ⩽ 2 Í𝑏 𝑖=𝑎 𝑛(𝑃𝑖) = 𝑂(𝑛) by sparsity. So the number of nodes is bounded by … view at source ↗
Figure 3
Figure 3. Figure 3: Left: an illustration of a segment tree over [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of a canonical path that visits four polygons [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The structure of the plane graph 𝐺 (𝑦) for a batch of three polygons 𝑃4, 𝑃5, 𝑃6. Active nodes are drawn as dots, and inactive nodes are drawn as crosses. The nodes that correspond to 𝑋 are drawn as squares. Edges are oriented downwards, whose weights are omitted for clarity. When we sweep 𝑦 for one step, the graph 𝐺 (𝑦) changes only marginally. The set of nodes do not change, and at most two edges are inse… view at source ↗
Figure 5
Figure 5. Figure 5: An illustration of a tour that visits four polygons [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A zig step of the splay tree. Under this interpretation, we can later speak of inserting a vertex (𝑥, 𝑦) to the tree. What we really mean is that we create a new node 𝑢 with 𝑥𝑢 := 𝑥, insert it to the splay tree, and set up the 𝛿𝑣’s so that 𝑦𝑢 = 𝑦 and the remaining 𝑦𝑣’s do not change. The time cost is dominated by the cost of inserting an element to the tree. Later we also invoke a well-known fact: Given an… view at source ↗
Figure 6
Figure 6. Figure 6: The structure of the plane graph 𝐺 (𝑦) for a batch of three polygons 𝑃4, 𝑃5, 𝑃6. Active nodes are drawn as dots, and inactive nodes are drawn as crosses. The nodes that correspond to 𝑋 are drawn as squares. Edges are oriented downwards, whose weights are omitted for clarity. When we sweep 𝑦 for one step, the graph 𝐺 (𝑦) changes only marginally. The set of nodes do not change, and at most two edges are inse… view at source ↗
Figure 7
Figure 7. Figure 7: A shortest tour that visits a sequence of rectangles. The tour decomposes into horizontal [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Left: the 𝑖-th segments in 𝐴𝑡 and 𝑉 , together with the 𝑗-th segments in 𝐵𝑡 and 𝐻. Right: the comb 𝐴𝑡 that corresponds to (𝑎1 [𝑡], 𝑎2 [𝑡], 𝑎3 [𝑡], 𝑎4 [𝑡]) = (0, 1, 1, 0), and the comb 𝐵𝑡 that corresponds to (𝑏1 [𝑡], 𝑏2 [𝑡], 𝑏3 [𝑡], 𝑏4 [𝑡]) = (0, 0, 1, 0). For each dimension 1 ⩽ 𝑡 ⩽ 𝑑, we construct a vertical comb𝐴𝑡 and a horizontal comb 𝐵𝑡 . The comb 𝐴𝑡 has 𝑁 vertical line segments, where the 𝑖-th segment … view at source ↗
Figure 9
Figure 9. Figure 9: The cases of 𝑞𝑗−1 when 𝑞𝑗 is on a horizontal edge. The first row illustrates the case, and the second row illustrates how we move the points. The thin curves in the background shows the local view of a shortest path. Lemma 9. In time 𝑂(𝑛), we can partition R 2 into 𝑛 + 1 rectangles such that (i) no rectangle contains a vertex of 𝑃1, . . . , 𝑃𝑘 in its interior; (ii) every vertical/horizontal line intersects… view at source ↗
Figure 9
Figure 9. Figure 9: Left: the 𝑖-th segments in 𝐴𝑡 and 𝑉 , together with the 𝑗-th segments in 𝐵𝑡 and 𝐻. Right: the comb 𝐴𝑡 that corresponds to (𝑎1 [𝑡], 𝑎2 [𝑡], 𝑎3 [𝑡], 𝑎4 [𝑡]) = (0, 1, 1, 0), and the comb 𝐵𝑡 that corresponds to (𝑏1 [𝑡], 𝑏2 [𝑡], 𝑏3 [𝑡], 𝑏4 [𝑡]) = (0, 0, 1, 0). as {𝑐𝑖 + 𝑎𝑖[𝑡]} × [𝑐, 𝐷] × {4 − 4𝑎𝑖[𝑡]}. Similarly, the comb 𝐵𝑡 has 𝑁 vertical segments, where the 𝑗-th segment encodes the coordinate 𝑏𝑗 [𝑡] and is defi… view at source ↗
read the original abstract

We 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. In this paper, we consider the orthogonal setting (with orthogonal polygons and Manhattan distance) and obtain the following results: - 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the shortest tour visiting a sequence of k orthogonal polygons (total n vertices) under Manhattan distance, where a tour is an oriented curve hitting each polygon in order. It claims a truly subquadratic Õ(n^{2-1/48}) algorithm when consecutive polygons are disjoint, an Õ(n) algorithm for disjoint ortho-convex polygons, an O(n) algorithm for axis-aligned rectangles, and Õ(n²) / Õ(n^{1.5}k²) algorithms in the unrestricted case. The results rely on additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles for weighted planar graphs, extending the Dror et al. (STOC 2003) framework to the orthogonal setting.

Significance. If the claimed bounds hold, the subquadratic result for disjoint consecutive polygons is a meaningful advance over the Õ(nk) bound for disjoint convex polygons in the Euclidean setting, as the exponent 2-1/48 is independent of k and exploits disjointness via dynamic oracles and decompositions. The linear-time special cases for ortho-convex polygons and rectangles are strong if they avoid hidden factors and align with the general technique. The work ships concrete complexity improvements and reproducible algorithmic structure (Voronoi + persistent structures) that could be verified or extended.

minor comments (3)
  1. Abstract: the phrase 'truly subquadratic' is used for the Õ(n^{2-1/48}) bound; clarify whether the Õ notation hides polylog factors that could affect the 'truly' qualifier relative to the prior Õ(nk) result.
  2. The manuscript should include a brief table or paragraph comparing the new bounds to Dror et al. (STOC 2003) and any intermediate orthogonal results, citing the exact prior exponents.
  3. Section on rectangle decompositions: the reduction from ortho-convex to rectangles is stated as linear-time; confirm that the constant factors and any auxiliary structures remain linear under the disjointness assumption.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation of minor revision. The referee's summary correctly reflects our main results: the Õ(n^{2-1/48}) algorithm for disjoint consecutive orthogonal polygons, the linear-time algorithms for ortho-convex polygons and rectangles, and the unrestricted bounds. We appreciate the recognition that the exponent is independent of k and that the techniques extend the Dror et al. framework. No specific major comments were listed in the report, so we have no point-by-point revisions to address at this stage. We are happy to incorporate any minor clarifications the editor may request.

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper derives new algorithmic results for shortest tours visiting sequences of orthogonal polygons under Manhattan distance, achieving subquadratic time for disjoint consecutive polygons via combinations of additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles. These build on external prior literature (e.g., Dror et al. STOC 2003) without self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations. The exponent 2-1/48 arises from recurrence analysis under the stated disjointness assumption, which is an independent combinatorial condition rather than a tautology. Special cases (ortho-convex, rectangles) use linear-time reductions aligned with the general method but not circularly dependent on the main bound. The derivation chain is self-contained against external benchmarks with no equations or steps reducing by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, new axioms, or invented entities are visible. All cited techniques (Voronoi diagrams, persistent structures) are standard in the literature.

pith-pipeline@v0.9.0 · 5582 in / 926 out tokens · 28793 ms · 2026-05-14T22:02:04.292277+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Com- puting smallest convex intersecting polygons.Journal of Computational Geometry, 16(1):167–202, 2025.doi:10.20382/jocg.v16i1a6

    [AdBKS25] Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. Com- puting smallest convex intersecting polygons.Journal of Computational Geometry, 16(1):167–202, 2025.doi:10.20382/jocg.v16i1a6. [AGTG21] Charles Joseph Argue, Anupam Gupta, Ziye Tang, and Guru Guruganesh. Chasing con- vex bodies with linear competitive ratio.Jour...

    work page doi:10.20382/jocg.v16i1a6 2025

  2. [2]

    24 [BBE+20] Nikhil Bansal, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh

    doi:10.1145/3450349. 24 [BBE+20] Nikhil Bansal, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh. Nested convex bodies are chaseable.Algorithmica, 82(6):1640–1653, 2020.doi: 10.1007/s00453-019-00661-x. [BCI+19] Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic algorithms for alge...

    work page doi:10.1145/3450349 2020

  3. [3]

    [BKK+22] Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, and Zahra Parsaeian

    doi:10.1109/FOCS.2015.15. [BKK+22] Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, and Zahra Parsaeian. Towards sub-quadratic diameter computation in geometric intersection graphs. In38th International Symposium on Computational Geometry (SoCG 2022), volume 224 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 21:1–2...

    work page doi:10.1109/focs.2015.15 2015

  4. [4]

    Dynamic time warping under translation: Approximation guided by space-filling curves.Journal of Computational Geometry, 14(2):83–107, 2023.doi:10.20382/jocg

    [BKK+23] Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic time warping under translation: Approximation guided by space-filling curves.Journal of Computational Geometry, 14(2):83–107, 2023.doi:10.20382/jocg. v14i2a6. [BLLS23] Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing con...

    work page doi:10.20382/jocg 2023

  5. [5]

    [BN22] Karl Bringmann and André Nusser

    doi:10.1137/20M1312332. [BN22] Karl Bringmann and André Nusser. Translating Hausdorff is hard: Fine-grained lower bounds for Hausdorff distance under translation.Journal of Computational Geometry, 13(2):30–50, 2022.doi:10.20382/jocg.v13i2a3. [Bri14] Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms un...

    work page doi:10.1137/20m1312332 2022

  6. [6]

    [Bri19] Karl Bringmann

    doi:10.1109/FOCS.2014.76. [Bri19] Karl Bringmann. Fine-grained complexity theory (tutorial). In Rolf Niedermeier and Christophe Paul, editors,36th International Symposium on Theoretical Aspects of Com- puter Science (STACS 2019), volume 126 ofLIPIcs, pages 4:1–4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.doi:10.4230/LIPICS.STACS.2019.4. [B...

    work page doi:10.1109/focs.2014.76 2014

  7. [7]

    25 [CHY23] Timothy M

    arXiv:2510.16346. 25 [CHY23] Timothy M. Chan, Qizheng He, and Yuancheng Yu. On the fine-grained complexity of small-size geometric set cover and discrete𝑘-center for small𝑘. In50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 ofLeib- niz International Proceedings in Informatics (LIPIcs), pages 34:1–34:19. Schlo...

    work page doi:10.4230/lipics.icalp.2023.34 2023

  8. [8]

    van Kreveld, and Mark H

    [dBCvKO08] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.Com- putational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008.doi: 10.1007/978-3-540-77974-2. [dBvK94] Mark de Berg and Marc van Kreveld. Rectilinear decompositions with low stabbing number.Information processing letters, 52(4):215–221,

    work page doi:10.1007/978-3-540-77974-2 2008

  9. [9]

    [DELM03] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell. Touring a sequence of polygons. InProceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003), STOC ’03, page 473–482, 2003.doi:10.1145/780542.780612. [DKP+15] José Miguel Díaz-Báñez, Matias Korman, Pablo Pérez-Lantero, Alexander Pilz, Carlos Seara, and Rod...

    work page doi:10.1145/780542.780612 2003

  10. [10]

    [FL93] Joel Friedman and Nathan Linial

    URL:https://www.sciencedirect.com/science/article/pii/ 0022000089900342,doi:10.1016/0022-0000(89)90034-2. [FL93] Joel Friedman and Nathan Linial. On convex body chasing.Discrete & Computational Geometry, 9(3):293–321, 1993.doi:10.1007/BF02189324. [FVP11] Jan Faigl, Vojtěch Vonásek, and Libor Přeučil. A multi-goal path planning for goal re- gions in the po...

    work page doi:10.1016/0022-0000(89)90034-2 1993

  11. [11]

    [FVP13] Jan Faigl, Vojtěch Vonásek, and Libor Přeučil

    URL:https://comrob.fel.cvut.cz/ papers/ecmr11mtp.pdf. [FVP13] Jan Faigl, Vojtěch Vonásek, and Libor Přeučil. Visiting convex regions in a polygo- nal map.Robotics and Autonomous Systems, 61(10):1070–1083, 2013.doi:10.1016/ j.robot.2012.08.013. [GO95] Anka Gajentaan and Mark H. Overmars. On a class of𝑂(𝑛 2)problems in computational geometry.Computational G...

    work page doi:10.1016/0925-7721(95)00022-2 2013

  12. [12]

    [Kle89] Rolf Klein.Concrete and abstract Voronoi diagrams

    doi:10.1109/ECMR.2019.8870971. [Kle89] Rolf Klein.Concrete and abstract Voronoi diagrams. Springer,

    work page doi:10.1109/ecmr.2019.8870971 2019

  13. [13]

    On the Travelling Salesman Problem with Neighborhoods in a Polygonal World

    [KVM23] Miroslav Kulich, Jan Vidašič, and Jan Mikula. On the Travelling Salesman Problem with Neighborhoods in a Polygonal World. In José M. Cascalho, Mohammad Osman Tokhi, Manuel F. Silva, Armando Mendes, Khaled Goher, and Matthias Funk, editors,Robotics in Natural Settings, volume 530 ofLecture Notes in Networks and Systems, pages 334–345. Springer, Cha...

    work page doi:10.1007/978-3-031-15226-9_32 2023

  14. [14]

    [MS04] Joseph S

    SIAM, 2013.doi:10.1137/1.9781611973105.60. [MS04] Joseph S. B. Mitchell and Micha Sharir. New results on shortest paths in three dimensions. InProceedings of the Twentieth Annual ACM Symposium on Computational Geometry, SCG ’04, pages 124–133, New York, NY, USA,

    work page doi:10.1137/1.9781611973105.60 2013

  15. [15]

    doi:10.1145/997817.997839

    Association for Computing Machinery. doi:10.1145/997817.997839. [NP24] Bengt J. Nilsson and Eli Packer. Approximation algorithms for the two-watchman route in a simple polygon.Algorithmica, 86(9):2845–2884, 2024.doi:10.1007/ s00453-024-01245-0. [PV24] Justo Puerto and Carlos Valverde. The hampered travelling salesman problem with neighbourhoods.Computers ...

    work page doi:10.1145/997817.997839 2024

  16. [16]

    27 A Rectangle partition with low stabbing number Proof of Lemma 13.Let𝑉be the set of vertices of𝑃 1,

    Associ- ation for Computing Machinery.doi:10.1145/1998196.1998243. 27 A Rectangle partition with low stabbing number Proof of Lemma 13.Let𝑉be the set of vertices of𝑃 1, . . . , 𝑃𝑘. We build a quadtree on𝑉as follows. Let 𝐵be the bounding box of𝑉. We split𝐵into two rectangles𝐵 0, 𝐵1 by a vertical line at the median 𝑥-coordinate in𝑉. Then we split each𝐵 𝑖 in...

    work page doi:10.1145/1998196.1998243