Touring a Sequence of Orthogonal Polygons
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916006327222272 |
|---|---|
| author | Casel, Katrin Kisfaludi-Bak, Sándor Kleist, Linda Lamme, Jeroen S. K. Oh, Eunjin Wang, Yanheng |
| author_facet | Casel, Katrin Kisfaludi-Bak, Sándor Kleist, Linda Lamme, Jeroen S. K. Oh, Eunjin Wang, Yanheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07882 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Touring a Sequence of Orthogonal Polygons Casel, Katrin Kisfaludi-Bak, Sándor Kleist, Linda Lamme, Jeroen S. K. Oh, Eunjin Wang, Yanheng Computational Geometry Data Structures and Algorithms 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. |
| title | Touring a Sequence of Orthogonal Polygons |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.07882 |