Publications with Hadi Khodabandeh
On the edge crossings of the greedy spanner.
D. Eppstein and H. Khodabandeh.
arXiv:2002.05854.
Proc. 37th International Symposium on Computational Geometry (SoCG 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 189, 2021, pp. 33:1–33:17.Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.
Distributed construction of lightweight spanners for unit ball graphs.
D. Eppstein and H. Khodabandeh.
arXiv:2106.15234.
Brief announcement, 34th ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 57–59.
Proc. 36th International Symposium on Distributed Computing (DISC 2022).
Leibniz International Proceedings in Informatics (LIPIcs) 246, 2022, pp. 21:1–21:23.Metric spaces of bounded doubling dimension have spanners with bounded degree, weight a bounded multiple of the minimum spanning tree weight, and dilation arbitrarily close to one, that can be found efficiently by a distributed algorithm.
Maintaining light spanners via minimal updates.
D. Eppstein and H. Khodabandeh.
arXiv:2403.03290.
Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 1–15.We find a way to maintain a spanner of a dynamic point set, a graph approximating its distances to within a \(1+\varepsilon\) factor while maintaining weight proportionate to the minimum spanning tree. Each change to the point set leads to a logarithmic number of changes to the spanner, although update times remain slow.