2025-11-10T02:41:11.708295

Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs

Ãgoston, Dumitrescu, Sagdeev et al.

For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Nearest Neighbor Graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of $n$ points in $\mathbb{R}^d$, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least $\log{n}/(4d)$. Apart from the $1/(4d)$ factor, this bound is the best possible. As for the abstract setting, we show that for every $n$-element metric space, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree $Î©(\sqrt{\log{n}/\log\log{n}})$.

academic

Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs

基本信息

论文ID: 2406.08913
标题: Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs
作者: Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh, Ji Zeng
分类: math.CO (组合数学), cs.CG (计算几何), math.MG (度量几何)
发表时间/会议: CALDAM 2025 (早期版本)，arXiv版本更新至2025年10月13日
论文链接: https://arxiv.org/abs/2406.08913

摘要

对于欧几里得空间或更一般的抽象度量空间中的有序点集，有序最近邻图通过将每个点与其最近的前驱点用有向边连接而得到。本文证明了对于 $\mathbb{R}^d$ 中的任意 $n$ 个点，存在一种排序使得相应的有序最近邻图的最大度数至少为 $\log n/(4d)$ 。除了 $1/(4d)$ 因子外，此界是最优的。对于抽象设置，证明了对于任意 $n$ 元度量空间，存在一种排序使得相应的有序最近邻图的最大度数为 $\Omega(\sqrt{\log n/\log\log n})$ 。

研究背景与动机

问题定义

本文研究有序最近邻图(Ordered Nearest Neighbor Graph)中的最大入度问题。给定点集 $P$ 和其上的排序，有序最近邻图通过将每个点连接到其在排序中所有前驱点中距离最近的点而构造。

研究动机

理论意义: 传统最近邻图的最大入度受接触数(kissing number)限制，但有序版本的性质尚未充分研究
实际应用: 有序最近邻图在动态算法、几何最短路径计算、稀疏图构造等领域有重要应用
算法优化: 理解最大度数的界限对于设计高效的几何算法具有指导意义
对偶问题: 相比于最小化最大度数(容易构造路径图)，最大化问题更具挑战性

现有研究局限

Eppstein等人的经典工作主要关注传统最近邻图的性质
有序版本的度数界限缺乏系统性研究
高维空间和抽象度量空间的结果更加稀少

核心贡献

一维最优结果: 证明了线上 $n$ 个点的有序最近邻图最大入度可达 $\lceil\log n\rceil$ ，且此界是紧的
高维空间界限: 对于 $\mathbb{R}^d$ 中的 $n$ 个点，构造了达到 $\log n/(4d)$ 最大入度的排序
抽象度量空间: 在一般度量空间中获得了 $\Omega(\sqrt{\log n/\log\log n})$ 的下界
构造性证明: 所有结果都提供了显式的构造算法，而非存在性证明

Algorithm Order(P) for points on line:
Step 1: 设a,b为P的最左和最右端点
Step 2: 以ab中点为界将P分割为A∪B，其中|A| ≥ |B|
Step 3: 按以下顺序列出P：
        Center(A), b, Delete(Order(A),Center(A)), AnyOrder(B\{b})
Step 4: Center(P) ← Center(A)

关键洞察: 通过递归分割和精心安排顺序，确保每次递归调用都能为中心点增加一个入度。

2. 高维空间的扩展算法

Algorithm Order(P) for points in R^d:
Step 1: 计算直径对ab，假设|ab| = 1
Step 2: 按到a,b距离分割：A = {p: |pa| ≤ |pb|}, B = {p: |pb| ≤ |pa|}
Step 3: 利用Corollary 1将A分割为至多16^d/2个直径<1/2的子集
Step 4: 选择包含至少n/16^d个点的子集C
Step 5: 按序列出：Center(C), b, Delete(Order(C),Center(C)), AnyOrder(P\(C∪{b}))

技术关键: 使用凸集覆盖定理(Theorem 4)进行空间分割，保证递归子问题的独立性。