{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:04:16Z","timestamp":1758265456025},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9465-2","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T15:23:37Z","timestamp":1288797817000},"page":"207-225","source":"Crossref","is-referenced-by-count":11,"title":["Geometric Spanners for Weighted Point Sets"],"prefix":"10.1007","volume":"61","author":[{"given":"Mohammad Ali","family":"Abam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Berg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Farshi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","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":[[2010,11,4]]},"reference":[{"key":"9465_CR1","first-page":"192","volume-title":"SCG\u201910: Proceedings of the 26th Annual ACM Symposium on Computational Geometry","author":"M.A. Abam","year":"2010","unstructured":"Abam, M.A., Har-Peled, S.: New constructions of SSPDs and their applications. In: SCG\u201910: Proceedings of the 26th Annual ACM Symposium on Computational Geometry, pp. 192\u2013200 (2010)"},{"key":"9465_CR2","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/s00454-009-9137-7","volume":"41","author":"M.A. Abam","year":"2009","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete Comput. Geom. 41, 556\u2013582 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9465_CR3","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1145\/263867.263869","volume":"44","author":"P.K. Agarwal","year":"1997","unstructured":"Agarwal, P.K., Har-Peled, S., Sharir, M., Varadarajan, K.R.: Approximate shortest paths on\u00a0a\u00a0convex polytope in three dimensions. J. ACM 44, 567\u2013584 (1997)","journal-title":"J. ACM"},{"key":"9465_CR4","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM 45, 891\u2013923 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"9465_CR5","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans R n . Bull. Soc. Math. Fr. 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. Fr."},{"issue":"4","key":"9465_CR6","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1016\/j.ejc.2006.04.003","volume":"28","author":"B. Bollob\u00e1s","year":"2007","unstructured":"Bollob\u00e1s, B., Scott, A.: On separating systems. Eur. J. Comb. 28(4), 1068\u20131071 (2007)","journal-title":"Eur. J. Comb."},{"key":"9465_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/978-3-540-69903-3_33","volume-title":"SWAT\u201908: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory","author":"P. Bose","year":"2008","unstructured":"Bose, P., Carmi, P., Courture, M.: Spanners of additively weighted point sets. In: SWAT\u201908: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 5124, pp. 367\u2013377. Springer, Berlin (2008)"},{"key":"9465_CR8","first-page":"291","volume-title":"SODA\u201993: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P.B. Callahan","year":"1993","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA\u201993: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013300. Society for Industrial and Applied Mathematics, Philadelphia (1993)."},{"key":"9465_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"9465_CR10","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/1132516.1132599","volume-title":"STOC\u201906","author":"R. Cole","year":"2006","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: STOC\u201906, pp. 574\u2013583. (2006)"},{"key":"9465_CR11","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/jagm.2000.1135","volume":"38","author":"C.A. Duncan","year":"2001","unstructured":"Duncan, C.A., Goodrich, M.T., Kobourov, S.: Balanced aspect ratio trees: combining the advances of k-d trees and octrees. J. Algorithms 38, 303\u2013333 (2001)","journal-title":"J. Algorithms"},{"key":"9465_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1007\/978-3-540-87744-8_40","volume-title":"Proceedings of the 16th Annual European Symposium on Algorithms","author":"L.-A. Gottlieb","year":"2008","unstructured":"Gottlieb, L.-A., Roditty, L.: An optimal dynamic spanner for doubling metric spaces. In: Proceedings of the 16th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol.\u00a05193, pp.\u00a0478\u2013489. Springer, Berlin (2008)"},{"key":"9465_CR13","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings"},{"key":"9465_CR14","first-page":"6037","volume":"258","author":"G. Hansel","year":"1964","unstructured":"Hansel, G.: Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C.\u00a0R. Acad. Sci. Paris 258, 6037\u20136040 (1964). Russian transl., Kibern. Sb. (Nov. Ser.) 5, 47\u201352 (1968)","journal-title":"C.\u00a0R. Acad. Sci. Paris"},{"issue":"5","key":"9465_CR15","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"9465_CR16","series-title":"Universitext","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on Analysis on Metric Spaces","author":"J. Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on Analysis on Metric Spaces. Universitext. Springer, New York (2001)"},{"key":"9465_CR17","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, Cambridge (2007)"},{"key":"9465_CR18","first-page":"373","volume-title":"SCG\u201907: Proceedings of the 23rd Annual ACM Symposium on Computational Geometry","author":"L. Roditty","year":"2007","unstructured":"Roditty, L.: Fully dynamic geometric spanners. In: SCG\u201907: Proceedings of the 23rd Annual ACM Symposium on Computational Geometry, pp. 373\u2013380 (2007)"},{"key":"9465_CR19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/1007352.1007399","volume-title":"STOC\u201904: Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"K. Talwar","year":"2004","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: STOC\u201904: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 281\u2013290. ACM, New York (2004)"},{"key":"9465_CR20","first-page":"320","volume-title":"FOCS\u201998: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science","author":"K.R. Varadarajan","year":"1998","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: FOCS\u201998: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0320\u2013331 (1998)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-010-9465-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T03:21:10Z","timestamp":1685848870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9465-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,4]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9465"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9465-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,4]]}}}