Abstract
Given a set P of n points in the plane, a unit-disk graph \(G_{r}(P)\) with respect to a radius r is an undirected graph whose vertex set is P such that an edge connects two points \(p, q \in P\) if the Euclidean distance between p and q is at most r. The length of any path in \(G_r(P)\) is the number of edges of the path. Given a value \(\lambda >0\) and two points s and t of P, we consider the following reverse shortest path problem: finding the smallest r such that the shortest path length between s and t in \(G_r(P)\) is at most \(\lambda \). It was known previously that the problem can be solved in \(O(n^{4/3} \log ^3 n)\) time. In this paper, we present an algorithm of \(O(\lfloor \lambda \rfloor \cdot n \log n)\) time and another algorithm of \(O(n^{{5}/{4}} \log ^2 n)\) time.
This research was supported in part by NSF under Grant CCF-2005323. A full version of this paper is available at https://arxiv.org/abs/2104.14476.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29, 912–953 (1999)
Ajtai, M., Komlós, J., Szemerédi, E.: An \(O(n\log n)\) sorting network. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 1–9 (1983)
de Berg, M., Bodlaender, H., Kisfaludi-Bak, S., Marx, D., van der Zanden, T.: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pp. 574–586 (2018)
Burton, D., Toint, P.: On an instance of the inverse shortest paths problem. Math. Program. 53, 45–61 (1992)
Cabello, S., Jejčič, M.: Shortest paths in intersection graphs of unit disks. Comput. Geom.: Theory Appl. 48, 360–367 (2015)
Chan, T., Skrepetos, D.: All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In: Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), pp. 24:1–24:13 (2016)
Chan, T., Skrepetos, D.: Approximate shortest paths and distance oracles in weighted unit-disk graphs. In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG), pp. 24:1–24:13 (2018)
Clark, B., Colbourn, C., Johnson, D.: Unit disk graphs. Discret. Math. 86, 165–177 (1990)
Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34, 200–208 (1987)
Erickson, J.: On the relative complexities of some geometric problems. In: Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG), pp. 85–90 (1995)
Erickson, J.: New lower bounds for Hopcroft’s problem. Discret. Comput. Geom. 16, 389–418 (1996)
Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153–174 (1987)
Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput. 35, 151–169 (2005)
Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2495–2504 (2017)
Katz, M., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26, 1384–1408 (1997)
Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194–200. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46515-7_16
Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30, 852–865 (1983)
Roditty, L., Segal, M.: On bounded leg shortest paths problems. Algorithmica 59, 583–600 (2011)
Shamos, M., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), pp. 151–162 (1975)
Wang, H., Xue, J.: Near-optimal algorithms for shortest paths in weighted unit-disk graphs. Discret. Comput. Geom. 64, 1141–1166 (2020)
Zhang, J., Lin, Y.: Computation of the reverse shortest-path problem. J. Glob. Optim. 25, 243–261 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, H., Zhao, Y. (2021). Reverse Shortest Path Problem for Unit-Disk Graphs. In: Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science(), vol 12808. Springer, Cham. https://doi.org/10.1007/978-3-030-83508-8_47
Download citation
DOI: https://doi.org/10.1007/978-3-030-83508-8_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83507-1
Online ISBN: 978-3-030-83508-8
eBook Packages: Computer ScienceComputer Science (R0)