Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments
Algorithmica · 2026-08 · 88 (4)
DOI: 10.1007/s00453-026-01395-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 15.06.2026. Verfasst von Pankaj K. Agarwal und 3 weiteren Autor:innen. Die Arbeit nennt 59 Literaturangaben. Gefördert von: National Science Foundation, United States-Israel Binational Science Foundation, Israel Science Foundation.
Abstract (Originalsprache)
In this paper we study several proximity problems related to a set of pairwise-disjoint segments in R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}^2$$\end{document}. Let S be a set of n pairwise-disjoint segments in R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}^2$$\end{document}, and let r>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r>0$$\end{document} be a parameter. We define the segment r-proximity graph of S to be Gr(S):=(S,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_r(S):= (S,E)$$\end{document}, where E={(e1,e2)∣dist(e1,e2)≤r}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E = \{ (e_1,e_2) \mid \textrm{dist}(e_1,e_2) \le r\}$$\end{document} and dist(e1,e2)=min(p,q)∈e1×e2‖p-q‖\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{dist}(e_1,e_2) = \min _{(p,q)\in e_1\times e_2} \Vert p-q\Vert $$\end{document} is the Euclidean distance between e1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_1$$\end{document} and e2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_2$$\end{document}. We define the weight of an edge (e1,e2)∈E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(e_1,e_2) \in E$$\end{document} to be dist(e1,e2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{dist}(e_1,e_2)$$\end{document}. We first present a simple grid-based O(nlog2n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log ^2 n)$$\end{document}-time algorithm for computing a BFS tree of Gr(S)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_r(S)$$\end{document}. We apply it to obtain an O∗(n8/7)+O(nlog2nlogΔ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(n^{8/7}) + O(n\log ^2n\log \Delta )$$\end{document}-time algorithm for the so-called reverse shortest path problem, in which given two segments s,t∈S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s, t \in S$$\end{document} and an integer k>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k>0$$\end{document}, we wish to compute the smallest value r∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r^*$$\end{document} for which Gr∗(S)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_{r^*}(S)$$\end{document} contains a path from s to t composed of at most k edges. (Here the O∗(·)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(\cdot )$$\end{document} notation hides polylogarithmic factors.) Here Δ=maxe≠e′∈Sdist(e,e′)/mine≠e′∈Sdist(e,e′)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta = \max _{e\ne e' \in S} \textrm{dist}(e,e')/\min _{e\ne e' \in S} \textrm{dist}(e,e')$$\end{document} is what we call the spread of S. Next, we present a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions so that the segment of S closest to a query segment e, chosen from an unknown set Q of pairwise-disjoint segments, can be computed in O(log5n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^5 n)$$\end{document} amortized time. The amortized update time is also O(log5n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log ^5 n)$$\end{document}. We note that if the segments in S∪Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S\cup Q$$\end{document} are allowed to intersect then the known lower bounds on halfplane range searching suggest that a sequence of n updates and queries may take at least close to Ω(n4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n^{4/3})$$\end{document} time in the worst case. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in O(polylog(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\textrm{polylog}(n))$$\end{document} (amortized) time each. Using these results on nearest-neighbor (NN) searching for disjoint segments, we show that a DFS tree (or forest) of Gr(S)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_r(S)$$\end{document} can be computed in O(nlog4n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log ^4n)$$\end{document} time. We also obtain an O(nlog3n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log ^3n)$$\end{document}-time algorithm for constructing a minimum spanning tree of Gr(S)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_r(S)$$\end{document}. Finally, we present an O∗(n4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(n^{4/3})$$\end{document}-time algorithm for computing a single-source shortest-path tree in Gr(S)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_r(S)$$\end{document}. This is the only result where we could not achieve a near-linear performance.
Förderung
- National Science Foundation
- United States-Israel Binational Science Foundation
- Israel Science Foundation
- Blavatnik research Foundation
Zitieren
APA
Agarwal, P. K., Kaplan, H., Katz, M. J., & Sharir, M. (2026). Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments. Algorithmica, 88(4). https://doi.org/10.1007/s00453-026-01395-3
Vancouver
Agarwal PK, Kaplan H, Katz MJ, Sharir M. Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments. Algorithmica. 2026;88(4). doi:10.1007/s00453-026-01395-3
BibTeX
@article{Agarwal2026,
author = {Agarwal, Pankaj K. and Kaplan, Haim and Katz, Matthew J. and Sharir, Micha},
title = {Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {4},
doi = {10.1007/s00453-026-01395-3}
}
EUVIMED