Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen · 2025
Read Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings by Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26110.txt.
Introduction
Sandor Kisfaludi-Bak, Tze-Yang Poon, and Geert van Wordragen study shortest paths in regular hyperbolic tilings, the infinite planar graphs formed by regular polygons that only fit in hyperbolic geometry. Each vertex has the same degree and each face the same number of edges, with a numeric condition that forces negative curvature. They ask how the routes between a set of terminal points are organized.
The authors compute an isometric closure, closely tied to the geodesic convex hull of the terminals, in near linear time by reusing a classic convex hull algorithm. The hull size is linear in total path length, and its treewidth, a measure of how tree like a graph is, stays small. That bound yields fast algorithms for subset traveling salesman and Steiner tree problems.
Catalog record
| CREATOR | Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26110
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen Abstract Hyperbolic tilings are natural infinite planar graphs where each vertex has degree q q and each face has p p edges for some 1 p + 1 q < 1 2 \frac{1}{p}+\frac{1}{q}<\frac{1}{2} . We study the structure of shortest paths in such graphs. We show that given a set of n 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 𝒪 ( N ) \mathcal{O}(N) where N 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 n terminals has treewidth only max ( 12 , 𝒪 ( log n p + q ) ) \max(12,\mathcal{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 𝒪 ( N log N ) + poly ( n p + q ) ⋅ N \mathcal{O}(N\log N)+\mathrm{poly}(\frac{n}{p+q})\cdot N . Department of Computer Science, Aalto University, [email protected]://orcid.org/0000-0002-6856-2902Supported by the Research Council of Finland, Grant 363444. Department of Computer Science, University of Oxford, United [email protected]://orcid.org/0009-0006-2260-9580 Department of Computer Science, Aalto University, [email protected]://orcid.org/0000-0002-2650-638X ccs Theory of computation Computational geometry ccs Theory of computation Parameterized complexity and exact algorithms ccs Theory of computation Shortest paths ccs Mathematics of computing Graph algorithms keywords Hyperbolic tiling, Geodesic convexity in graphs, Steiner Tree, Subset TSP † † runningauthor: Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen † † copyright: Anonymous author(s) † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The uniform tilings of the three geometries (Euclidean, elliptical/spherical, and hyperbolic) are fundamental discrete structures that have received a lot of well-deserved attention in algorithms and discrete mathematics. In the geometric algorithms literature, these objects are studied in their own right, and they are also the basis of countless algorithmic techniques: e.g., a square grid is very often the basis of geometric approximation algorithms, but the triangular and hexagonal grids are also often sought out for their properties. In the spherical setting, the tilings correspond to the platonic solids; these are finite structures that have been used and studied for millennia. Figure 1: The regular tiling in spherical, Euclidean and hyperbolic geometry where p=3 and q=5,6 , and 7 , respectively. In the hyperbolic plane, unlike the other geometries, there is a much richer set of uniform tilings: for any pair of integers p,q where \frac{1}{p}+\frac{1}{q}<\frac{1}{2} there exists a decomposition of the hyperbolic plane (henceforth denoted by \mathbb{H}^{2} ) into congruent copies of interior-disjoint regular p -gons (tiles) where each vertex is shared by q tiles. This decomposition is called the uniform hyperbolic tiling of Schläfli symbol \{p,q\} . An emerging body of work studies uniform hyperbolic tilings from the algorithmic perspective [ 20 , 26 , 25 , 22 ] , but many fundamental questions, such as computing shortest paths, remain mostly unexplored. In Euclidean square grids it is easy to characterize shortest paths: given a pair of points, these are the set of x - and y -monotone paths connecting the pair. These shortest paths are covered by the minimum bounding box of the point pair. The problem is much less clear when one wants to find a shortest path between two given vertices of a hyperbolic tiling. Due to the fact that \mathbb{H}^{2} is not a vector space (a typical pair of “translations” do not commute), it is significantly harder to find shortest paths in hyperbolic tilings. It is not even clear how one should define a vertex of a tiling in the input of an algorithm. One way to represent a vertex is geometrically, by its coordinates in some model of the hyperbolic plane. Another is graph/group theoretically, as a path from a fixed vertex in the tiling graph or similarly as a word in the corresponding group (i.e. the group generated by the translations that take a vertex to its neighbors). Since these groups are non-abelian, conversion between these two representations is not as straightforward as for regular Euclidean tilings. However, the groups are still automatic , which lets us convert a word of length \ell to a normal form in \mathcal{O}(\ell^{2}) time [ 15 , 8 ] and thereby solve the word problem (“do these words represent the same group element”), which is undecidable in general. In fact, they are strongly geodesically automatic : words in the normal form correspond to shortest paths [ 10 ] . In this paper we will represent the input vertices of the tiling via paths (or even walks) from a fixed origin vertex; in the hyperbolic setting, this has a similar complexity as the number of bits in representations with coordinates, see \Cref sec:preliminaries for a discussion. Shortest paths and intervals in graphs and tilings In the graph setting, geodesic convexity has been studied intensively, see the monograph [ 29 ] for a detailed overview of the topic. In graphs, there can be several shortest paths between a pair of endpoints, so in order to generalize the notion of convexity, we need some further terminology, introduced here only for unweighted graphs. The interval of a vertex pair u,v\in V(G) is the subgraph I_{G}(u,v)\subset E(G) given by the union of all shortest paths between u and v . An important property of shortest paths in hyperbolic tilings is that they stay together in the following sense: for any pair of points u,v in the tiling, and any pair of shortest (u,v) -paths P and P^{\prime} we have that each vertex of P^{\prime} is within distance \mathcal{O}_{p,q}(1) from some vertex of P . This property holds much more generally, even for certain approximate shortest paths in the more general setting of Gromov-hyperbolic metric spaces. See [ 8 ] for a detailed exposition. As a result, we can already derive that an interval I(u,v) in a hyperbolic tiling has constant-size vertex separators, unlike the Euclidean grid where the interval of a pair of points can be a square-shaped patch of the grid of arbitrary side length. In this article, we will get a more accurate description of intervals in hyperbolic tilings. Convexity in graphs In the Euclidean setting, it is natural to talk about the bounding box of a set P of grid points, and observe that all pairwise shortest paths in P are contained in the bounding box. This notion is similar to the geometric notion of convex hulls . Let G be a graph. We say that a subgraph H\subseteq E(G) is convex if for any u,v\in V(H) we have I_{G}(u,v)\subseteq H . On the other hand, there is