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

정렬된 최근접 이웃 그래프에서 최대 차수 최대화

기본 정보

논문 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)에서의 최대 입차수(maximum in-degree) 문제를 연구한다. 점 집합 $P$ 와 그 위의 정렬이 주어졌을 때, 정렬된 최근접 이웃 그래프는 각 점을 정렬에서 그 모든 선행점 중 거리가 가장 가까운 점과 연결하여 구성된다.

연구 동기

이론적 의의: 전통적 최근접 이웃 그래프의 최대 입차수는 접촉수(kissing number)에 의해 제한되지만, 정렬된 버전의 성질은 아직 충분히 연구되지 않았다
실제 응용: 정렬된 최근접 이웃 그래프는 동적 알고리즘, 기하학적 최단경로 계산, 희소 그래프 구성 등의 분야에서 중요한 응용을 가진다
알고리즘 최적화: 최대 차수의 경계를 이해하는 것은 효율적인 기하학적 알고리즘 설계에 지도적 의미를 가진다
쌍대 문제: 최대 차수를 최소화하는 것(경로 그래프 구성이 용이함)과 비교하여, 최대화 문제는 더욱 도전적이다

기존 연구의 한계

Eppstein 등의 고전적 연구는 주로 전통적 최근접 이웃 그래프의 성질에 초점을 맞춘다
정렬된 버전의 차수 경계에 대한 체계적 연구가 부족하다
고차원 공간과 추상 거리공간에 대한 결과는 더욱 드물다

핵심 기여

1차원 최적 결과: 직선 위의 $n$ 개 점의 정렬된 최근접 이웃 그래프 최대 입차수가 $\lceil\log n\rceil$ 에 도달할 수 있음을 증명하고, 이 경계는 타이트하다
고차원 공간 경계: $\mathbb{R}^d$ 의 $n$ 개 점에 대해 $\log n/(4d)$ 최대 입차수에 도달하는 정렬을 구성한다
추상 거리공간: 일반 거리공간에서 $\Omega(\sqrt{\log n/\log\log n})$ 의 하한을 얻는다
구성적 증명: 모든 결과는 존재성 증명이 아닌 명시적 구성 알고리즘을 제공한다

방법 상세 설명

작업 정의

입력: 거리공간 $(V,\rho)$ 의 유한 점 집합 $P = \{p_1, p_2, \ldots, p_n\}$ 출력: 점 집합의 정렬 $\pi$ 로서, 대응하는 정렬된 최근접 이웃 그래프의 최대 입차수가 가능한 한 크도록 함 제약: 점 집합이 일반 위치에 있음(이등변 삼각형 없음)

핵심 알고리즘 프레임워크

1. 1차원 경우의 재귀적 구성

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)를 사용하여 공간을 분할하고, 재귀 부분 문제의 독립성을 보장한다.