457Accesses
Years and Authors of Summarized Original Work
2002; Gudmundsson, Levcopoulos, Narasimhan, Smid
2005; Gudmundsson, Narasimhan, Smid
2008; Gudmundsson, Levcopoulos, Narasimhan, Smid
Problem Definition
Given a geometric graph ind-dimensional space, it is useful to preprocess it so that distance queries, exact or approximate, can be answered efficiently. Algorithms that can report distance queries in constant time are also referred to as “distance oracles.” With unlimited preprocessing time and space, it is clear that exact distance oracles can be easily designed. This entry sheds light on the design of approximate distance oracles with limited preprocessing time and space for the family of geometric graphs with constant dilation.
Notation and Definitions
Ifp andq are points in\(\mathcal{R}^{d}\), then the notation | pq | is used to denote the Euclidean distance betweenp andq; the notationδG(p, q) is used to denote the Euclidean length of a shortest path betweenp andqin a...
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 285999
- Price includes VAT (Japan)
- Hardcover Book
- JPY 285999
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Agarwal PK, Har-Peled S, Karia M (2000) Computing approximate shortest paths on convex polytopes. In: Proceedings of the 16th ACM symposium on computational geometry, Hong Kong, pp 270–279
Arikati S, Chen DZ, Chew LP, Das G, Smid M, Zaroliagis CD (1996) Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings of the 4th annual european symposium on algorithms, Barcelona. Lecture notes in computer science, vol 1136. Springer, Berlin, pp 514–528
Baswana S, Sen S (2004) Approximate distance oracles for unweighted graphs in\(\tilde{O}(n^{2})\) time. In: Proceedings of the 15th ACM-SIAM symposium on discrete algorithms, Philadelphia, pp 271–280
Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: Proceedings of the 4th Latin American symposium on theoretical informatics, Punta del Este. Lecture notes in computer science, vol 1776. Springer, Berlin, pp 88–94
Chen DZ, Daescu O, Klenk KS (2001) On geometric path query problems. Int J Comput Geom Appl 11:617–645
Das G, Narasimhan G (1997) A fast algorithm for constructing sparse Euclidean spanners. Int J Comput Geom Appl 7:297–315
Gao J, Zhang L (2005) Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J Comput 35(1):151–169
Gao J, Guibas LJ, Hershberger J, Zhang L, Zhu A (2003) Discrete mobile centers. Discret Comput Geom 30:45–63
Gudmundsson J, Levcopoulos C, Narasimhan G (2002) Fast greedy algorithms for constructing sparse geometric spanners. SIAM J Comput 31:1479–1500
Gudmundsson J, Levcopoulos C, Narasimhan G, Smid M (2002) Approximate distance oracles for geometric graphs. In: Proceedings of the 13th ACM-SIAM symposium on discrete algorithms, San Francisco, pp 828–837
Gudmundsson J, Levcopoulos C, Narasimhan G, Smid M (2002) Approximate distance oracles revisited. In: Proceedings of the 13th international symposium on algorithms and computation, Osaka. Lecture notes in computer science, vol 2518. Springer, Berlin, pp 357–368
Gudmundsson J, Narasimhan G, Smid M (2005) Fast pruning of geometric spanners. In: Proceedings of the 22nd symposium on theoretical aspects of computer science, Stuttgart. Lecture notes in computer science, vol 3404. Springer, Berlin, pp 508–520
Gudmundsson J, Levcopoulos C, Narasimhan G, Smid M (2008) Approximate distance oracles for geometric spanners. ACM Trans Algorithms 4(1):article 10
Narasimhan G, Smid M (2007) Geometric spanner networks. Cambridge University, Cambridge
Sankaranarayanan J, Samet H (2010) Query processing using distance oracles for spatial networks. IEEE Trans Knowl Data Eng 22(8):1158–1175
Thorup M (2004) Compact oracles for reachability and approximate distances in planar digraphs. J ACM 51:993–1024
Thorup M, Zwick U (2001) Approximate distance oracles. In: Proceedings of the 33rd annual ACM symposium on the theory of computing, Crete, pp 183–192
Author information
Authors and Affiliations
DMiST, National ICT Australia Ltd, Alexandria, Australia
Joachim Gudmundsson
School of Information Technologies, University of Sydney, Sydney, NSW, Australia
Joachim Gudmundsson
Department of Computer Science, Florida International University, Miami, FL, USA
Giri Narasimhan
School of Computing and Information Sciences, Florida International University, Miami, FL, USA
Giri Narasimhan
School of Computer Science, Carleton University, Ottawa, ON, Canada
Michiel Smid
- Joachim Gudmundsson
You can also search for this author inPubMed Google Scholar
- Giri Narasimhan
You can also search for this author inPubMed Google Scholar
- Michiel Smid
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJoachim Gudmundsson.
Editor information
Editors and Affiliations
Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA
Ming-Yang Kao
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Gudmundsson, J., Narasimhan, G., Smid, M. (2016). Applications of Geometric Spanner Networks. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_15
Download citation
Published:
Publisher Name:Springer, New York, NY
Print ISBN:978-1-4939-2863-7
Online ISBN:978-1-4939-2864-4
eBook Packages:Computer ScienceReference Module Computer Science and Engineering
Share this entry
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative