Ágoston, Péter and Dumitrescu, Adrian and Sagdeev, Arsenii and Singh, K. and Zeng, Ji (2025) Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs. LECTURE NOTES IN COMPUTER SCIENCE, 15536. pp. 358-367. ISSN 0302-9743
|
Text
2406.08913v3.pdf - Draft Version Download (528kB) | Preview |
Abstract
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 Rd, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least logn/(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 Ω(logn/loglogn). © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
| Item Type: | Article |
|---|---|
| Additional Information: | Export Date: 02 April 2025; Cited By: 0; Correspondence Address: P. Ágoston; HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary; email: agostonp@renyi.hu; A. Sagdeev; HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary; email: sagdeevarsenii@gmail.com; J. Zeng; HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary; email: jzeng@ucsd.edu; A. Dumitrescu; Algoresearch L.L.C., Milwaukee, United States; email: ad.dumitrescu@algoresearch.org; K. Singh; Indraprastha Institute of Information Technology, Delhi, India; email: karamjeets@iiitd.ac.in; Conference name: 11th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2025; Conference date: 13 February 2025 through 15 February 2025; Conference code: 326699 |
| Uncontrolled Keywords: | Directed graphs; Maximum degree; Point set; Euclidean spaces; Metric spaces; Nearest neighbor search; Directed edges; Nearest-neighbour; Neighbor graph; Abstract metrics; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 23 Jan 2026 06:24 |
| Last Modified: | 23 Jan 2026 06:24 |
| URI: | https://real.mtak.hu/id/eprint/232492 |
Actions (login required)
 |
Edit Item |
