2025/04/08 by Sujoy Bhore, Timothy M. Chan, Bhore, Sujoy +7 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2504.05861
openalex publication_date 2025/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝd. For example, we show that the intersection graph of n balls in ℝd admits a 2-hop spanner of size O^*(n(3)/(2)-(1)/(2(2\lfloor d/2\rfloor +1))) and the intersection graph of n fat axis-parallel boxes in ℝd admits a 2-hop spanner of size O(n logd+1n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝd admits a 3-hop spanner of size O^*(n(3)/(2)-(1)/(2(2D-1))), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ3), we provide a lower bound of Ω(n(4)/(3)). For 3-hop and axis-parallel boxes in ℝd, we provide the upper bound O(n log d-1n) and lower bound Ω(n ((log n)/(log log n))d-2).