Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915550159962112 |
|---|---|
| author | Ágoston, Péter Dumitrescu, Adrian Sagdeev, Arsenii Singh, Karamjeet Zeng, Ji |
| author_facet | Ágoston, Péter Dumitrescu, Adrian Sagdeev, Arsenii Singh, Karamjeet Zeng, Ji |
| contents | 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}})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08913 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs Ágoston, Péter Dumitrescu, Adrian Sagdeev, Arsenii Singh, Karamjeet Zeng, Ji Combinatorics Computational Geometry Metric Geometry 05C07, 05D10, 52C10 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}})$. |
| title | Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs |
| topic | Combinatorics Computational Geometry Metric Geometry 05C07, 05D10, 52C10 |
| url | https://arxiv.org/abs/2406.08913 |