{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:11:14Z","timestamp":1743091874198,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":17,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_15","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"86-90","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Applications of Geometric Spanner Networks"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giri","family":"Narasimhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"1_CR1315","doi-asserted-by":"crossref","unstructured":"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\u00a0270\u2013279","DOI":"10.1145\/336154.336213"},{"key":"1_CR1316","doi-asserted-by":"crossref","unstructured":"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:\u00a0Proceedings of the 4th annual european symposium on algorithms, Barcelona. Lecture notes in computer science, vol 1136. Springer, Berlin, pp\u00a0514\u2013528","DOI":"10.1007\/3-540-61680-2_79"},{"key":"1_CR1317","unstructured":"Baswana S, Sen S (2004) Approximate distance oracles for unweighted graphs in \n                  \n                    \n                      \u00d5\n                      (\n                      \n                        \n                          n\n                        \n                        \n                          2\n                        \n                      \n                      )\n                    \n                  \n                  $$\\tilde{O}(n^{2})$$\n                 time. In: Proceedings of the 15th ACM-SIAM symposium on discrete algorithms, Philadelphia, pp\u00a0271\u2013280"},{"key":"1_CR1318","doi-asserted-by":"crossref","unstructured":"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\u00a088\u201394","DOI":"10.1007\/10719839_9"},{"key":"1_CR1319","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1142\/S0218195901000675","volume":"11","author":"DZ Chen","year":"2001","unstructured":"Chen DZ, Daescu O, Klenk KS (2001) On geometric path query problems. Int J Comput Geom Appl 11:617\u2013645","journal-title":"Int J Comput Geom Appl"},{"key":"1_CR1320","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G Das","year":"1997","unstructured":"Das G, Narasimhan G (1997) A fast algorithm for constructing sparse Euclidean spanners. Int J Comput Geom Appl 7:297\u2013315","journal-title":"Int J Comput Geom Appl"},{"issue":"1","key":"1_CR1321","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/S0097539703436357","volume":"35","author":"J Gao","year":"2005","unstructured":"Gao J, Zhang L (2005) Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J Comput 35(1):151\u2013169","journal-title":"SIAM J Comput"},{"key":"1_CR1322","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00454-003-2925-6","volume":"30","author":"J Gao","year":"2003","unstructured":"Gao J, Guibas LJ, Hershberger J, Zhang L, Zhu A (2003) Discrete mobile centers. Discret Comput Geom 30:45\u201363","journal-title":"Discret Comput Geom"},{"key":"1_CR1323","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J Gudmundsson","year":"2002","unstructured":"Gudmundsson J, Levcopoulos C, Narasimhan G (2002) Fast greedy algorithms for constructing sparse geometric spanners. SIAM J Comput 31:1479\u20131500","journal-title":"SIAM J Comput"},{"key":"1_CR1324","unstructured":"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\u00a0828\u2013837"},{"key":"1_CR1325","doi-asserted-by":"crossref","unstructured":"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\u00a02518. Springer, Berlin, pp\u00a0357\u2013368","DOI":"10.1007\/3-540-36136-7_32"},{"key":"1_CR1326","doi-asserted-by":"crossref","unstructured":"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\u00a03404. Springer, Berlin, pp\u00a0508\u2013520","DOI":"10.1007\/978-3-540-31856-9_42"},{"key":"1_CR1327","doi-asserted-by":"crossref","unstructured":"Gudmundsson J, Levcopoulos C, Narasimhan G, Smid M (2008) Approximate distance oracles for geometric spanners. ACM Trans Algorithms 4(1):article 10","DOI":"10.1145\/1328911.1328921"},{"key":"1_CR1328","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric spanner networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan G, Smid M (2007) Geometric spanner networks. Cambridge University, Cambridge"},{"issue":"8","key":"1_CR1329","doi-asserted-by":"publisher","first-page":"1158","DOI":"10.1109\/TKDE.2010.75","volume":"22","author":"J Sankaranarayanan","year":"2010","unstructured":"Sankaranarayanan J, Samet H (2010) Query processing using distance oracles for spatial networks. IEEE Trans Knowl Data Eng 22(8):1158\u20131175","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1_CR1330","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup M (2004) Compact oracles for reachability and approximate distances in planar digraphs. J ACM 51:993\u20131024","journal-title":"J ACM"},{"key":"1_CR1331","doi-asserted-by":"crossref","unstructured":"Thorup M, Zwick U (2001) Approximate distance oracles. In: Proceedings of the 33rd annual ACM symposium on the theory of computing, Crete, pp\u00a0183\u2013192","DOI":"10.1145\/380752.380798"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:12:56Z","timestamp":1553098376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_15","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}