{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:56:32Z","timestamp":1767239792422,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,6]],"date-time":"2016-05-06T00:00:00Z","timestamp":1462492800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.023.208"],"award-info":[{"award-number":["639.023.208"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["612.001.207"],"award-info":[{"award-number":["612.001.207"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00453-016-0160-9","type":"journal-article","created":{"date-parts":[[2016,5,6]],"date-time":"2016-05-06T09:28:28Z","timestamp":1462526908000},"page":"209-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Distribution-Sensitive Construction of the Greedy Spanner"],"prefix":"10.1007","volume":"78","author":[{"given":"Sander P. A.","family":"Alewijnse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quirijn W.","family":"Bouts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex P.","family":"ten Brink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,6]]},"reference":[{"issue":"4","key":"160_CR1","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/s00454-009-9137-7","volume":"41","author":"MA Abam","year":"2009","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete Comput. Geom. 41(4), 556\u2013582 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"160_CR2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s00454-007-9019-9","volume":"39","author":"PK Agarwal","year":"2008","unstructured":"Agarwal, P.K., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir, M., Soss, M.: Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D. Discrete Comput. Geom. 39(1), 17\u201337 (2008)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"160_CR3","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00453-015-0001-2","volume":"73","author":"SPA Alewijnse","year":"2015","unstructured":"Alewijnse, S.P.A., Bouts, Q.W., ten Brink, A.P., Buchin, K.: Computing the greedy spanner in linear space. Algorithmica 73(3), 589\u2013606 (2015)","journal-title":"Algorithmica"},{"key":"160_CR4","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M Atallah","year":"1985","unstructured":"Atallah, M.: Some dynamic computational geometry problems. Comput. Math. Appl. 11, 1171\u20131181 (1985)","journal-title":"Comput. Math. Appl."},{"issue":"3","key":"160_CR5","doi-asserted-by":"crossref","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, M.: Computing the greedy spanner in near-quadratic time. Algorithmica 58(3), 711\u2013729 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"160_CR6","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1137\/S0895480197318088","volume":"20","author":"P Bose","year":"2006","unstructured":"Bose, P., Devroye, L., Evans, W., Kirkpatrick, D.: On the spanning ratio of Gabriel graphs and beta-skeletons. SIAM J. Discrete Math. 20(2), 412\u2013427 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"160_CR7","doi-asserted-by":"crossref","unstructured":"Bouts, Q.W., ten Brink, A.P., Buchin, K.: A framework for computing the greedy spanner. In: Proceedings of 30th Symposium Computional Geometry, pp. 11\u201319. ACM (2014)","DOI":"10.1145\/2582112.2582154"},{"key":"160_CR8","doi-asserted-by":"crossref","unstructured":"Buchin, K.: Constructing Delaunay triangulations along space-filling curves. In: Proceedings of 17th Annual European Symposium Algorithms (ESA), pp. 119\u2013130. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_11"},{"key":"160_CR9","unstructured":"Callahan, P.B.: Dealing with Higher Dimensions: The Well-Separated Pair Decomposition and Its Applications. PhD thesis, Johns Hopkins University, Baltimore (1995)"},{"issue":"2","key":"160_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"160_CR11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0898-1221(88)90071-5","volume":"15","author":"L Devroye","year":"1988","unstructured":"Devroye, L.: On the expected size of some graphs in computational geometry. Comput. Math. Appl. 15, 53\u201364 (1988)","journal-title":"Comput. Math. Appl."},{"issue":"4","key":"160_CR12","doi-asserted-by":"crossref","first-page":"1123","DOI":"10.1017\/S0001867800003773","volume":"41","author":"L Devroye","year":"2009","unstructured":"Devroye, L., Gudmundsson, J., Morin, P.: On the expected maximum degree of Gabriel and Yao graphs. Adv. Appl. Probab. 41(4), 1123\u20131140 (2009)","journal-title":"Adv. Appl. Probab."},{"issue":"1","key":"160_CR13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.comgeo.2006.05.007","volume":"37","author":"D Eppstein","year":"2007","unstructured":"Eppstein, D., Wortman, K.A.: Minimum dilation stars. Comput. Geom. 37(1), 27\u201337 (2007)","journal-title":"Comput. Geom."},{"issue":"1","key":"160_CR14","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1109\/JSAC.2004.837364","volume":"23","author":"J Gao","year":"2005","unstructured":"Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. 23(1), 174\u2013185 (2005)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"160_CR15","first-page":"52-1","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"J Gudmundsson","year":"2006","unstructured":"Gudmundsson, J., Knauer, C.: Dilation and detours in geometric networks. In: Gonzales, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics, pp. 52-1\u201352-16. Chapman & Hall\/CRC, Boca Raton (2006)"},{"key":"160_CR16","first-page":"306","volume-title":"Property Testing, 6390 of LNCS","author":"F Hellweg","year":"2011","unstructured":"Hellweg, F., Schmidt, M., Sohler, C.: Testing Euclidean spanners. In: Goldreich, O. (ed.) Property Testing, 6390 of LNCS, pp. 306\u2013311. Springer, Berlin (2011)"},{"key":"160_CR17","doi-asserted-by":"crossref","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: Proceedings of 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of LNCS, pp. 208\u2013213. Springer (1988)","DOI":"10.1007\/3-540-19487-8_23"},{"key":"160_CR18","doi-asserted-by":"crossref","unstructured":"M\u00fccke, E.P., Saias, I., Zhu, B.: Fast randomized point location without preprocessing in two-and three-dimensional Delaunay triangulations. In: Proceedings of 12th Symposium on Computer Geomics, pp. 274\u2013283. ACM (1996)","DOI":"10.1145\/237218.237396"},{"issue":"3","key":"160_CR19","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1137\/S0097539799361671","volume":"30","author":"G Narasimhan","year":"2000","unstructured":"Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 30(3), 978\u2013989 (2000)","journal-title":"SIAM J. Comput."},{"key":"160_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, New York (2007)"},{"issue":"1","key":"160_CR21","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"160_CR22","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1145\/1089733.1089736","volume":"37","author":"P Santi","year":"2005","unstructured":"Santi, P.: Topology control in wireless ad hoc and sensor networks. ACM Comput. Surv.: CSUR 37(2), 164\u2013194 (2005)","journal-title":"ACM Comput. Surv.: CSUR"},{"key":"160_CR23","volume-title":"Davenport\u2013Schinzel Sequences and their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.: Davenport\u2013Schinzel Sequences and their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"6","key":"160_CR24","doi-asserted-by":"crossref","first-page":"1963","DOI":"10.1109\/TNET.2010.2053381","volume":"18","author":"H Shpungin","year":"2010","unstructured":"Shpungin, H., Segal, M.: Near-optimal multicriteria spanner constructions in wireless ad hoc networks. IEEE\/ACM Trans. Netw. 18(6), 1963\u20131976 (2010)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"160_CR25","unstructured":"Steele, J.M.: Probability Theory and Combinatorial Optimization, volume\u00a069 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM (1997)"},{"issue":"7","key":"160_CR26","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1002\/dac.844","volume":"20","author":"Y Wang","year":"2007","unstructured":"Wang, Y., Li, X.-Y.: Efficient Delaunay-based localized routing for wireless sensor networks. Int. J. Commun. Syst. 20(7), 767\u2013789 (2007)","journal-title":"Int. J. Commun. Syst."},{"issue":"2","key":"160_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1023\/B:WINE.0000013081.09837.c0","volume":"10","author":"F Xue","year":"2004","unstructured":"Xue, F., Kumar, P.R.: The number of neighbors needed for connectivity of wireless networks. Wireless Netw. 10(2), 169\u2013181 (2004)","journal-title":"Wireless Netw."},{"key":"160_CR28","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability theory of classical Euclidean optimization problems. In: Lecture Notes in Mathematics, vol. 1675. Springer Berlin Heidelberg (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0160-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0160-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0160-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0160-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T15:17:05Z","timestamp":1553613425000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0160-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,6]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["160"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0160-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,5,6]]}}}