{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:48:36Z","timestamp":1725853716481},"publisher-location":"New York, NY","reference-count":33,"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":"tdm","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_167","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:15:58Z","timestamp":1553098558000},"page":"846-852","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Geometric Spanners"],"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":[{"issue":"4","key":"159_CR7128","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00454-011-9343-y","volume":"45","author":"MA Abam","year":"2011","unstructured":"Abam MA, de\u00a0Berg M (2011) Kinetic spanners in \u211d d . Discret Comput Geom 45(4):723\u2013736","journal-title":"Discret Comput Geom"},{"key":"159_CR7129","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/s00454-009-9137-7","volume":"41","author":"MA Abam","year":"2009","unstructured":"Abam MA, de\u00a0Berg M, Farshi M, Gudmundsson J (2009) Region-fault tolerant geometric spanners. Discret Comput Geom 41:556\u2013582","journal-title":"Discret Comput Geom"},{"issue":"3","key":"159_CR7130","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.comgeo.2009.01.008","volume":"43","author":"MA Abam","year":"2010","unstructured":"Abam MA, de\u00a0Berg M, Gudmundsson J (2010) A simple and efficient kinetic spanner. Comput Geom 43(3):251\u2013256","journal-title":"Comput Geom"},{"key":"159_CR7131","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-40450-4_4","volume-title":"21st annual European symposium on algorithms","author":"SPA Alewijnse","year":"2013","unstructured":"Alewijnse SPA, Bouts QW, ten Brink AP, Buchin K (2013) Computing the greedy spanner in linear space. In: Bodlaender HL, Italiano GF (eds) 21st annual European symposium on algorithms. Lecture notes in computer science, vol 8125. Springer, Heidelberg, pp\u00a037\u201348"},{"key":"159_CR7132","doi-asserted-by":"crossref","unstructured":"Arikati SR, 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 4th European symposium on algorithms. Lecture notes in computer science, vol\u00a01136. Springer Berlin\/Heidelberg, pp\u00a0514\u2013528","DOI":"10.1007\/3-540-61680-2_79"},{"key":"159_CR7133","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02523237","volume":"17","author":"S Arya","year":"1997","unstructured":"Arya S, Smid M (1997) Efficient construction of a bounded-degree spanner with low weight. Algorithmica 17:33\u201354","journal-title":"Algorithmica"},{"key":"159_CR7134","doi-asserted-by":"crossref","unstructured":"Arya S, Mount DM, Smid M (1994) Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proceedings of 35th IEEE symposium on foundations of computer science, Milwaukee, pp\u00a0703\u2013712","DOI":"10.1109\/SFCS.1994.365722"},{"key":"159_CR7135","doi-asserted-by":"crossref","unstructured":"Arya S, Das G, Mount DM, Salowe JS, Smid M (1995) Euclidean spanners: short, thin, and lanky. In: Proceedings of 27th ACM symposium on theory of computing, Las Vegas, pp\u00a0489\u2013498","DOI":"10.1145\/225058.225191"},{"issue":"2","key":"159_CR7136","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"S Arya","year":"1999","unstructured":"Arya S, Mount DM, Smid M (1999) Dynamic algorithms for geometric spanners of small diameter: randomized solutions. Comput Geom \u2013 Theory Appl 13(2):91\u2013107","journal-title":"Comput Geom \u2013 Theory Appl"},{"issue":"3","key":"159_CR7137","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00453-009-9293-4","volume":"58","author":"P Bose","year":"2010","unstructured":"Bose P, Carmi P, Farshi M, Maheshwari A, Smid MHM (2010) Computing the greedy spanner in near-quadratic time. Algorithmica 58(3):711\u2013729","journal-title":"Algorithmica"},{"key":"159_CR7138","first-page":"11","volume-title":"Symposium on computational geometry","author":"QW Bouts","year":"2014","unstructured":"Bouts QW, ten Brink AP, Buchin K (2014) A framework for computing the greedy spanner. In: Cheng SW, Devillers O (eds) Symposium on computational geometry, Kyoto. ACM, pp\u00a011\u201320"},{"key":"159_CR7139","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB Callahan","year":"1995","unstructured":"Callahan PB, Kosaraju SR (1995) A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J ACM 42:67\u201390","journal-title":"J ACM"},{"issue":"1","key":"159_CR7140","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s00454-008-9115-5","volume":"41","author":"HTH Chan","year":"2009","unstructured":"Chan HTH, Gupta A (2009) Small hop-diameter sparse spanners for doubling metrics. Discret Comput Geom 41(1):28\u201344","journal-title":"Discret Comput Geom"},{"key":"159_CR7141","first-page":"762","volume-title":"Symposium on discrete algorithms","author":"HTH Chan","year":"2005","unstructured":"Chan HTH, Gupta A, Maggs B, Zhou S (2005) On hierarchical routing in doubling metrics. In: Symposium on discrete algorithms, Vancouver. ACM, pp\u00a0762\u2013771"},{"key":"159_CR7142","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/978-3-642-39206-1_27","volume-title":"Automata, languages, and programming","author":"HTH Chan","year":"2013","unstructured":"Chan HTH, Li M, Ning L, Solomon S (2013) New doubling spanners: better and simpler. In: Automata, languages, and programming. Springer, Berlin\/Heidelberg, pp\u00a0315\u2013327"},{"key":"159_CR7143","doi-asserted-by":"crossref","unstructured":"Chandra B, Das G, Narasimhan G, Soares J (1992) New sparseness results on graph spanners. In: Proceedings of 8th annual symposium on computational geometry, Berlin, pp\u00a0192\u2013201","DOI":"10.1145\/142675.142717"},{"key":"159_CR7144","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B Chandra","year":"1995","unstructured":"Chandra B, Das G, Narasimhan G, Soares J (1995) New sparseness results on graph spanners. Int J Comput Geom Appl 5:124\u2013144","journal-title":"Int J Comput Geom Appl"},{"key":"159_CR7145","doi-asserted-by":"crossref","unstructured":"Czumaj A, Lingas A (2000) Fast approximation schemes for Euclidean multi-connectivity problems. In: Proceedings of 27th international colloquium on automata, languages and programming. Lecture notes in computer science, vol\u00a01853. Springer, Berlin\/Heidelberg, pp\u00a0856\u2013868","DOI":"10.1007\/3-540-45022-X_72"},{"issue":"2","key":"159_CR7146","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00454-004-1121-7","volume":"32","author":"A Czumaj","year":"2004","unstructured":"Czumaj A, Zhao H (2004) Fault-tolerant geometric spanners. Discret Comput Geom 32(2): 207\u2013230","journal-title":"Discret Comput Geom"},{"key":"159_CR7147","unstructured":"Das G (1997) The visibility graph contains a bounded-degree spanner. In: Proceedings of 9th Canadian conference on computational geometry, Kingston"},{"key":"159_CR7148","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"},{"key":"159_CR7149","unstructured":"Das G, Narasimhan G, Salowe J (1995) A new way to weigh malnourished Euclidean graphs. In: Proceedings of 6th ACM-SIAM symposium on discrete algorithms, San Francisco, pp\u00a0215\u2013222"},{"issue":"4","key":"159_CR7150","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/s00454-009-9230-y","volume":"43","author":"Y Dinitz","year":"2010","unstructured":"Dinitz Y, Elkin M, Solomon S (2010) Low-light trees, and tight lower bounds for Euclidean spanners. Discret Comput Geom 43(4):736\u2013783","journal-title":"Discret Comput Geom"},{"key":"159_CR7151","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/2488608.2488691","volume-title":"Proceedings of the forty-fifth annual ACM symposium on theory of computing, Palo Alto","author":"M Elkin","year":"2013","unstructured":"Elkin M, Solomon S (2013) Optimal Euclidean spanners: really short, thin and lanky. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing, Palo Alto, pp\u00a0645\u2013654"},{"issue":"1","key":"159_CR7152","first-page":"3","volume":"14","author":"M Farshi","year":"2009","unstructured":"Farshi M, Gudmundsson J (2009) Experimental study of geometric t-spanners. ACM J Exp Algorithmics 14(1):3\u201339","journal-title":"ACM J Exp Algorithmics"},{"key":"159_CR7153","doi-asserted-by":"crossref","unstructured":"Gao J, Guibas LJ, Nguyen A (2004) Deformable spanners and applications. In: Proceedings of 20th ACM symposium on computational geometry, Brooklyn, pp\u00a0190\u2013199","DOI":"10.1145\/997817.997848"},{"issue":"5","key":"159_CR7154","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) Improved greedy algorithms for constructing sparse geometric spanners. SIAM J Comput 31(5):1479\u20131500","journal-title":"SIAM J Comput"},{"issue":"1","key":"159_CR7155","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C Levcopoulos","year":"2002","unstructured":"Levcopoulos C, Narasimhan G, Smid M (2002) Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32(1):144\u2013156","journal-title":"Algorithmica"},{"key":"159_CR7156","first-page":"197","volume-title":"Ad Hoc wireless networking","author":"XY Li","year":"2003","unstructured":"Li XY (2003) Applications of computational geomety in wireless ad hoc networks. In: Cheng XZ, Huang X, Du DZ (eds) Ad Hoc wireless networking. Kluwer, Dordrecht, pp\u00a0197\u2013264"},{"key":"159_CR7157","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 Press, Cambridge\/New York"},{"key":"159_CR7158","first-page":"69","volume-title":"Proceedings of 5th workshop on algorithm engineering and experiments","author":"G Navarro","year":"2003","unstructured":"Navarro G, Paredes R (2003) Practical construction of metric t-spanners. In: Proceedings of 5th workshop on algorithm engineering and experiments, Baltimore, Maryland. SIAM Press, pp\u00a069\u201381"},{"key":"159_CR7159","unstructured":"Rahmati Z, Abam MA, King V, Whitesides S (2014) Kinetic data structures for the semi-Yao graph and all nearest neighbors in \u211d d $$\\mathbb{R}^{d}$$ . In: He M, Zeh N (eds) Canadian conference on computational geometry"},{"key":"159_CR7160","doi-asserted-by":"crossref","unstructured":"Rao S, Smith WD (1998) Approximating geometrical graphs via spanners and banyans. In: Proceedings of 30th ACM symposium on theory of computing, Dallas, pp\u00a0540\u2013550","DOI":"10.1145\/276698.276868"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T22:29:19Z","timestamp":1663108159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_167","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"}}]}}