Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
Timothy M. Chan, Zhengcheng Huang
In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geome…
cs.CG2025
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang +2
We present new results on - and -hop spanners for geometric intersection graphs. These include improved upper and lower bounds for - and -hop spanners for many geometri…