2025-11-20T14:13:14.486864

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings

Kisfaludi-Bak, Poon, van Wordragen

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$.

academic

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings

基本信息

论文ID: 2510.26110
标题: Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
作者: Sándor Kisfaludi-Bak (Aalto University), Tze-Yang Poon (University of Oxford), Geert van Wordragen (Aalto University)
分类: cs.CG (Computational Geometry)
发表时间: 2025年10月30日（arXiv预印本）
论文链接: https://arxiv.org/abs/2510.26110

摘要

双曲平铺（Hyperbolic tilings）是自然的无限平面图，其中每个顶点的度数为 $q$ ，每个面有 $p$ 条边，满足 $\frac{1}{p}+\frac{1}{q}<\frac{1}{2}$ 。本文研究此类图中最短路径的结构。主要成果包括：(1) 给定 $n$ 个终端点，可以在近线性时间内计算等距闭包（与测地凸包密切相关），使用经典几何凸包算法作为黑盒；(2) 凸包大小为 $O(N)$ ，其中 $N$ 是从固定原点到所有终端点的路径总长度；(3) 证明 $n$ 个终端点的测地凸包的树宽仅为 $\max(12, O(\log\frac{n}{p+q}))$ ，该界与点的距离无关；(4) 获得了子集TSP和Steiner树问题的算法，运行时间为 $O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$ 。

研究背景与动机

问题背景

核心问题：在双曲平铺图中计算最短路径、凸包结构，并解决组合优化问题（如Steiner树和子集TSP）。双曲平铺是基础的离散结构，但其最短路径计算等基本问题尚未得到充分探索。
问题重要性：
- 双曲几何中的均匀平铺是算法和离散数学中的基础对象，类似于欧几里得几何中的正方形网格
- 与欧几里得平面不同，双曲平面不是向量空间（平移不可交换），这使得最短路径计算显著更困难
- 双曲平铺图具有对数树宽的特殊结构，为解决NP难问题提供了可能
现有方法局限：
- 在欧几里得网格中，最短路径容易刻画（x-y单调路径），但双曲平铺中不清楚如何定义和计算
- 一般图的凸包计算算法29需要 $O(mn)$ 时间，在无限图中不适用
- 现有双曲平铺的树宽界20为 $O_p,q(\log n)$ ，但依赖于子图的顶点数，不够精细
研究动机：
- 欧几里得网格中的凸包和Hanan网格思想在双曲设置中如何推广？
- 能否利用双曲几何的特殊性质（如线性等周不等式）获得更强的结构结果？
- 能否设计对输入规模近线性、对终端数多项式的高效算法？

核心贡献

最短路径结构刻画：
- 证明了关键引理：对于双曲线 $\ell$ ，任意两个顶点间存在沿 $\ell$ 附近的最短路径（Lemma 3.3, 3.7）
- 建立了区间 $I(u,v)$ 的外平面性质（Corollary 3.4）
高效凸包计算：
- 提出算法在 $O(N\log N)$ 时间内计算等距闭包 $\hat{G}_K$ ，其中 $N$ 是输入路径总长度
- 证明凸包大小为 $O(N)$ （Lemma 5.5）
精细树宽界：
- 证明 $n$ 个终端点的凸包树宽为 $\max\{12, O(\log\frac{n}{p+q})\}$ （Theorem 1.3）
- 该界独立于点的距离，且随 $p,q$ 增大而减小
优化算法：
- 给出Steiner树和子集TSP的 $O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$ 时间算法（Theorem 1.4）
- 当 $\max(p,q)=\Omega(n)$ 时达到 $O(N\log N)$
理论洞察：
- 证明等距闭包是无洞的（Lemma 4.3）
- 建立了边界行走的测地性质（Lemma 4.5, 4.6）

方法详解

任务定义

输入：

双曲平铺图 $G_{p,q}$ （由Schläfli符号 $\{p,q\}$ 指定）
$n$ 个终端点集合 $K$ ，每个终端通过从固定原点出发的路径（长度总和为 $N$ ）表示

输出：

等距闭包 $\hat{G}_K$ 或凸包 $\text{conv}_G(K)$
Steiner树或子集TSP的最优解

关键概念：

区间 $I_G(u,v)$ ：连接 $u,v$ 的所有最短路径的并
凸子图：包含任意顶点对的所有最短路径
等距子图：保持任意顶点对的最短距离
凸包 $\text{conv}_G(K)$ ：包含 $K$ 的最小凸子图
等距闭包：包含 $K$ 的极小等距子图

核心技术框架

1. 最短路径沿双曲线的结构（Section 3）

关键引理3.3(i)：对于双曲线 $\ell$ 和任意两个顶点 $u,v$ 在被 $\ell$ 相交的瓦片上，存在完全包含在 $G_\ell$ （被 $\ell$ 相交的子图）中的最短路径。

证明思路：

假设存在最短路径 $P_{u,v}$ 离开 $G_\ell$
构造沿 $P_{u,v}$ 的瓦片序列 $t_1,\ldots,t_m$
利用双曲多边形面积公式：面积 = $\pi(m-2) - \sum\phi_i$
通过角度分析证明封闭区域面积为负，产生矛盾

更强的引理3.7：对于 $\ell$ 相交的边序列 $S_\ell$ ，任意两个端点间存在按顺序经过 $S_\ell$ 所有元素的最短路径。

证明策略（针对 $q=3$ 的复杂情况）：

分三种情况分析（基于 $p$ 的奇偶性和顶点位置）
利用双曲三角学的四部公式和直角三角形公式
通过精确的角度计算证明线 $\ell$ 不能相交特定瓦片 $t_4$
关键不等式： $\cot(\psi) > \cot(\phi')$ ，其中 $\psi,\phi'$ 是精确计算的角度

2. 等距闭包的性质（Section 4）

无洞性（Lemma 4.3）：任何等距子图的有界面都是瓦片。

证明：

假设存在非瓦片的有界面 $F$
考虑内部边 $e=uv$ 及其所在直线 $\ell$
利用Lemma 3.3(i)证明所有最短路径都使用边 $uv$
因此 $e$ 必须在等距闭包中，矛盾

边界测地性（Lemma 4.5）：边界行走 $W_{st}$ 在两个终端间是最短路径。

Lemma 4.6：边界行走的长度不劣于任何外部路径。

Lemma 4.7：任何最优Steiner树和TSP都可以在等距闭包 $G_K$ 中找到。

3. 等距闭包计算算法（Section 5）

Algorithm 1核心思路：

计算双曲凸包 $\text{conv}_H(K)$ 的顶点序列（使用Beltrami-Klein模型中的经典凸包算法）
对每对相邻终端 $v_i, v_{i+1}$ $v_{i}, v_{i + 1}$ ：
- 识别被线段 $v_iv_{i+1}$ 相交的顶点/边序列 $S_{v_iv_{i+1}}$
- 使用动态规划计算依次经过所有 $s_j \in S_{v_iv_{i+1}}$ 的最短路径
- 相邻元素间的最短路径仅使用共享瓦片的边（Lemma 3.1）
合并所有路径形成边界
使用深度优先搜索填充内部

时间复杂度分析：

坐标计算： $O(N)$
凸包计算： $O(n\log n)$
边界路径计算： $O(N)$ （每条边最多遍历两次）
内部填充： $O(N\log N)$ （使用关联数组检测已访问顶点）
总计： $O(N\log N)$

4. 树宽界证明（Section 6）

Theorem 1.3证明策略：

方法1（从原图）：

完全包含在 $\text{conv}_H(K)$ 内的瓦片数为 $O(n/p)$ （Lemma 6.1）
利用Kisfaludi-Bak20的结果： $|S|$ 个瓦片的邻域图是 $O(\log|S|)$ -外平面的
因此树宽为 $O(\log\frac{n}{p})$

方法2（从对偶图）：

对偶平铺 $G_{q,p}$ 中内部顶点数为 $O(n/q)$
诱导子图 $\hat{G}_K[V_{inner}]$ 是 $O(\log\frac{n}{q})$ -外平面的
利用平面图与其对偶树宽差最多1的性质
因此树宽为 $O(\log\frac{n}{q})$

结合两种方法：树宽 $\leq \max\{12, O(\log\frac{n}{p+q})\}$

技术创新点

几何与图论的深度结合：
- 创新性地利用双曲面积论证来约束图路径
- 面积公式 $\pi(m-2)-\sum\phi_i$ 成为核心工具
精细的几何分析：
- 针对 $q=3$ 情况的三种case分析展示了深刻的几何洞察
- 双曲三角学公式的精确应用（四部公式、直角三角形公式）
算法设计的黑盒使用：
- 巧妙利用Beltrami-Klein模型中双曲线是欧几里得直线的性质
- 将经典凸包算法作为黑盒应用
双重树宽界：
- 从原图和对偶图两个角度证明，取最小值
- 揭示了 $p,q$ 对称性和结构复杂度的关系
参数化复杂度的新视角：
- 树宽界独立于距离，仅依赖终端数和平铺参数
- 随 $p,q$ 增大而改善，反映双曲结构的树状特性

实验设置

注：本文是纯理论论文，不包含实验部分。所有结果都是通过严格的数学证明得出的。

理论验证方法

构造性证明：算法给出了显式构造方法
反证法：多处使用假设矛盾来证明结构性质
归纳法：如Lemma 4.6的证明
几何论证：基于双曲几何的面积和角度关系

计算模型

实数RAM模型：支持标准算术、平方根和正弦函数
输入表示：终端通过从原点出发的路径（长度序列）表示
坐标生成：使用Poincaré圆盘模型的双曲三角学公式

实验结果

由于本文是理论论文，"实验结果"部分用理论结果的总结代替。

主要理论结果

问题	结果	复杂度
等距闭包计算	Algorithm 1	$O(N\log N)$
凸包大小	Lemma 5.5	$O(N)$ 个顶点
凸包树宽	Theorem 1.3	$\max\{12, O(\log\frac{n}{p+q})\}$
Steiner树	Theorem 1.4	$O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$
子集TSP	Theorem 1.4	$O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$

关键性质验证

区间外平面性（Corollary 3.4）：任意两顶点的区间是外平面的
等距闭包无洞（Lemma 4.3）：所有有界面都是瓦片
边界测地性（Lemma 4.5）：边界行走在终端间是最短的
最优解包含性（Lemma 4.7）：最优Steiner树和TSP解存在于等距闭包中

与现有结果对比

方面	现有结果	本文结果	改进
树宽界	$O_{p,q}(\log n)$ 20	$O(\log\frac{n}{p+q})$	独立于距离，精细依赖 $p,q$
凸包算法	$O(mn)$ 29（一般图）	$O(N\log N)$	近线性，利用几何结构
Steiner树（平面图）	$n^{O(\sqrt{k})}$ 24	$O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$	多项式时间
子集TSP（平面图）	$k^{O(\sqrt{k})}n^{O(1)}$ 16	$O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$	多项式时间

理论发现

双曲几何的优势：线性等周不等式导致凸包大小线性
结构简化：随 $p,q$ 增大，图变得更"树状"，算法更快
参数化视角：终端数 $n$ 是关键参数，距离不影响树宽
几何-图论对应：双曲凸包与图凸包的紧密联系

结论与讨论

主要结论

结构结果：
- 双曲平铺中的最短路径沿双曲线聚集
- 区间是外平面的，凸包是无洞的
- 凸包大小与输入长度线性相关
算法结果：
- 等距闭包可在 $O(N\log N)$ 时间内计算
- Steiner树和子集TSP可在 $O(N\log N) + \text{poly}(\frac{n}{p+q}) \cdot N$ 时间内求解
复杂度理论：
- 凸包树宽为 $\max\{12, O(\log\frac{n}{p+q})\}$ ，独立于距离
- 树宽随 $p,q$ 增大而减小，反映双曲结构的树状特性

局限性

输入表示限制：
- 假设终端通过路径表示，坐标表示的转换需要额外工作
- 字问题求解（路径到正规形式）需要 $O(\ell^2)$ 时间
常数因子：
- 树宽界中的常数未明确给出
- $\text{poly}(\frac{n}{p+q})$ 的具体次数依赖于树宽算法
平铺识别问题：
- 如何识别一个图是否为平铺子图仍是开放问题
- 限制了方法在一般平面图上的应用
特定几何：
- 证明高度依赖于双曲平铺的规则结构
- 推广到非规则双曲图需要新技术
$q=3$ 的复杂性：
- 证明对 $q=3$ 需要大量case分析
- 表明该情况的本质困难

未来方向

算法改进：
- 能否去除 $\log N$ 因子达到线性时间？
- 能否改进 $\text{poly}(\frac{n}{p+q})$ 的次数？
问题推广：
- 推广到加权双曲平铺
- 处理近似最短路径
- 考虑动态终端集
理论深化：
- 更精确的树宽常数
- 树宽下界
- 其他优化问题（如设施选址）
几何推广：
- 非规则双曲图
- 其他Gromov双曲空间
- 变曲率设置
实现与应用：
- 实际实现和性能评估
- 网络设计中的应用
- 可视化工具

深度评价

优点

理论深度：
- 证明技术精巧，特别是针对 $q=3$ 的几何分析
- 结合双曲几何、图论和算法设计的多学科方法
- 从原图和对偶图双重视角证明树宽界展示了深刻洞察
结果强度：
- 树宽界独立于距离是重要突破，改进了20的结果
- 算法复杂度近线性且对终端数多项式，显著优于平面图的次指数算法
- 凸包大小的线性界利用了双曲几何的独特性质
技术创新：
- 面积论证（area argument）在图论中的创新应用
- 黑盒使用经典凸包算法展示了模型选择的智慧
- Lemma 3.7的证明是技术高峰，处理了多种复杂情况
写作质量：
- 结构清晰，从简单引理逐步推进到主要定理
- 图示丰富（8个图），帮助理解几何论证
- 附录中的详细证明增强了可验证性
实用价值：
- 为双曲平铺上的优化问题提供了实用算法
- 可能应用于网络设计、数据结构等领域
- 算法具有可实现性（给出了明确的计算模型）

不足

证明复杂性：
- $q=3$ 情况的证明冗长（Section 3.7），可读性受影响
- 大量三角学计算可能存在验证困难
- 某些常数（如树宽界中的12）的来源不够清晰
适用范围：
- 仅适用于规则双曲平铺，非规则情况未涉及
- 输入表示的特殊要求可能限制应用
- 平铺识别问题未解决限制了方法的一般性
实验缺失：
- 作为理论论文，缺乏实现和实验验证
- 算法的实际性能（常数因子）未知
- 与启发式方法的比较缺失
下界分析：
- 未提供算法复杂度的下界
- 树宽界的紧性未讨论
- 是否存在更快算法不清楚
技术细节：
- 实数RAM模型的假设较强（需要超越运算）
- 坐标生成的具体公式引用外部文献14
- 关联数组的实现细节未详述

影响力

理论贡献：
- 为双曲图算法理论奠定了重要基础
- 树宽界的参数化视角可能启发其他研究
- 几何论证技术可能推广到其他问题
领域推动：
- 推进了计算几何与图算法的交叉研究
- 为双曲空间中的算法设计提供了新工具
- 可能促进双曲几何在计算机科学中的应用
实用潜力：
- 为网络拓扑设计提供了理论支持
- 可能应用于社交网络、生物网络等具有双曲性质的数据
- 算法的多项式复杂度使实际应用成为可能
可复现性：
- 算法描述清晰，具有可实现性
- 证明详细，可验证性强
- 使用标准几何模型，易于理解和实现
后续研究：
- 已明确指出多个开放问题
- 为改进和推广提供了清晰方向
- 可能激发实验和应用研究

适用场景

理论研究：
- 双曲几何与图论的交叉研究
- 参数化复杂度理论
- 树宽和图结构理论
算法设计：
- 需要在双曲平铺上求解优化问题
- 大规模网络的分层结构分析
- 具有树状层次结构的数据处理
应用领域：
- 网络设计：互联网拓扑、传感器网络
- 数据分析：社交网络、生物网络的双曲嵌入
- 计算机视觉：双曲空间中的特征表示
- 机器学习：双曲神经网络的图结构
教育价值：
- 展示几何与算法的深度结合
- 参数化算法设计的案例研究
- 双曲几何的计算机科学应用

参考文献（精选）

8 Bridson & Haefliger (1999): Metric spaces of non-positive curvature - 双曲几何基础
20 Kisfaludi-Bak (2020): Hyperbolic intersection graphs and (quasi)-polynomial time - 树宽界的前期工作
29 Pelayo (2013): Geodesic Convexity in Graphs - 图凸性理论专著
6 Bodlaender et al. (2015): Deterministic single exponential time algorithms - 树宽算法基础
24 Klein & Marx (2014): Subexponential parameterized algorithm for subset TSP - 平面图基准算法

总体评价：这是一篇高质量的理论论文，在双曲平铺图的算法研究中取得了重要进展。通过深刻的几何洞察和精巧的证明技术，建立了最短路径结构、凸包性质和树宽界等核心结果，并设计了高效的优化算法。论文的主要价值在于揭示了双曲几何结构对算法复杂度的本质影响，为该领域的后续研究奠定了坚实基础。尽管证明较为技术性且缺乏实验验证，但其理论贡献和潜在应用价值使其成为计算几何和图算法领域的重要工作。

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings

基本信息

摘要

研究背景与动机

问题背景

核心贡献

方法详解

任务定义

核心技术框架

1. 最短路径沿双曲线的结构（Section 3）

2. 等距闭包的性质（Section 4）

3. 等距闭包计算算法（Section 5）

4. 树宽界证明（Section 6）

技术创新点

实验设置

理论验证方法

计算模型

实验结果

主要理论结果

关键性质验证

与现有结果对比

理论发现

相关工作

双曲几何中的算法研究

图凸性理论

平面图优化问题

双曲群和自动群

结论与讨论

主要结论

局限性

未来方向

深度评价

优点

不足

影响力

适用场景

参考文献（精选）