Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918178719793152 |
|---|---|
| author | Kisfaludi-Bak, Sándor Poon, Tze-Yang van Wordragen, Geert |
| author_facet | Kisfaludi-Bak, Sándor Poon, Tze-Yang van Wordragen, Geert |
| contents | Hyperbolic tilings are natural infinite planar graphs where each vertex has degree $q$ and each face has $p$ edges for some $\frac1p+\frac1q<\frac12$. We study the structure of shortest paths in such graphs. We show that given a set of $n$ terminals, we can compute a so-called isometric closure (closely related to the geodesic convex hull) of the terminals in near-linear time, using a classic geometric convex hull algorithm as a black box. We show that the size of the convex hull is $O(N)$ where $N$ is the total length of the paths to the terminals from a fixed origin.
Furthermore, we prove that the geodesic convex hull of a set of $n$ terminals has treewidth only $\max(12,O(\log\frac{n}{p + q}))$, a bound independent of the distance of the points involved. As a consequence, we obtain algorithms for subset TSP and Steiner tree with running time $O(N \log N) + \mathrm{poly}(\frac{n}{p + q}) \cdot N$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26110 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings Kisfaludi-Bak, Sándor Poon, Tze-Yang van Wordragen, Geert Computational Geometry Hyperbolic tilings are natural infinite planar graphs where each vertex has degree $q$ and each face has $p$ edges for some $\frac1p+\frac1q<\frac12$. We study the structure of shortest paths in such graphs. We show that given a set of $n$ terminals, we can compute a so-called isometric closure (closely related to the geodesic convex hull) of the terminals in near-linear time, using a classic geometric convex hull algorithm as a black box. We show that the size of the convex hull is $O(N)$ where $N$ is the total length of the paths to the terminals from a fixed origin. Furthermore, we prove that the geodesic convex hull of a set of $n$ terminals has treewidth only $\max(12,O(\log\frac{n}{p + q}))$, a bound independent of the distance of the points involved. As a consequence, we obtain algorithms for subset TSP and Steiner tree with running time $O(N \log N) + \mathrm{poly}(\frac{n}{p + q}) \cdot N$. |
| title | Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2510.26110 |