{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:20Z","timestamp":1740109580473,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER 1453472","CCF 1815145"],"award-info":[{"award-number":["CAREER 1453472","CCF 1815145"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1423230"],"award-info":[{"award-number":["CCF 1423230"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s00454-021-00282-8","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T19:02:56Z","timestamp":1622228576000},"page":"32-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fractal Dimension and Lower Bounds for Geometric Problems"],"prefix":"10.1007","volume":"66","author":[{"given":"Anastasios","family":"Sidiropoulos","sequence":"first","affiliation":[]},{"given":"Kritika","family":"Singhal","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9170-7914","authenticated-orcid":false,"given":"Vijay","family":"Sridhar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,28]]},"reference":[{"key":"282_CR1","doi-asserted-by":"crossref","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. Foundations of Information Technology in the Era of Network and Mobile Computing (Montreal 2002). IFIP Advances in Information and Communication Technology, vol. 96, pp. 26\u201337. Springer, New York (2002)","DOI":"10.1007\/978-0-387-35608-2_3"},{"key":"282_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: 44th Annual ACM Symposium on Theory of Computing (New York 2012), pp. 663\u2013672. ACM, New York (2012)","DOI":"10.1145\/2213977.2214038"},{"issue":"1","key":"282_CR3","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s00454-008-9115-5","volume":"41","author":"T-HH Chan","year":"2009","unstructured":"Chan, T.-H.H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. Discrete Comput. Geom. 41(1), 28\u201344 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"282_CR4","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1137\/090749396","volume":"41","author":"T-HH Chan","year":"2012","unstructured":"Chan, T.-H.H., Gupta, A.: Approximating TSP on metrics with bounded global growth. SIAM J. Comput. 41(3), 587\u2013617 (2012)","journal-title":"SIAM J. Comput."},{"key":"282_CR5","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms (Vancouver 2005), pp. 762\u2013771. ACM, New York (2005)"},{"key":"282_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, Ch., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM 63(5), # 40 (2016)","DOI":"10.1145\/2820609"},{"key":"282_CR7","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: 38th Annual ACM Symposium on Theory of Computing (Seattle 2006), pp. 574\u2013583. ACM, New York (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"282_CR8","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2017)"},{"key":"282_CR9","doi-asserted-by":"crossref","unstructured":"Gottlieb, L.-A., Roditty, L.: An optimal dynamic spanner for doubling metric spaces. In: 16th Annual European Symposium on Algorithms (Karlsruhe 2008). Lecture Notes in Computer Science, vol. 5193, pp. 478\u2013489. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"282_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lewi, K.: The online metric matching problem for doubling metrics. In: 39th International Colloquium on Automata, Languages, and Programming (Warwick 2012), vol.\u00a01. Lecture Notes in Comput. Sci., vol. 7391, pp. 424\u2013435. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-31594-7_36"},{"issue":"5","key":"282_CR11","doi-asserted-by":"publisher","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":"282_CR12","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: 34th Annual ACM Symposium on Theory of Computing (Montreal 2002), pp. 741\u2013750. ACM, New York (2002)","DOI":"10.1145\/509907.510013"},{"key":"282_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Yorktown Heights 1972), pp. 85\u2013103. Plenum, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"21","key":"282_CR14","doi-asserted-by":"publisher","first-page":"2867","DOI":"10.1016\/j.disc.2010.06.039","volume":"310","author":"K Kozawa","year":"2010","unstructured":"Kozawa, K., Otachi, Y., Yamazaki, K.: The carving-width of generalized hypercubes. Discrete Math. 310(21), 2867\u20132876 (2010)","journal-title":"Discrete Math."},{"issue":"2\u20133","key":"282_CR15","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/j.tcs.2005.09.017","volume":"348","author":"R Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R.: The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2\u20133), 262\u2013276 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"282_CR16","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: 47th Annual IEEE Symposium on Foundations of Computer Science (Pittsburgh 2006), pp. 119\u2013132. IEEE, Los Alamitos (2006)","DOI":"10.1109\/FOCS.2006.9"},{"issue":"4","key":"282_CR17","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839\u2013858 (2005)","journal-title":"Geom. Funct. Anal."},{"key":"282_CR18","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: 13th Annual European Symposium on Algorithms (Palma de Mallorca 2005). Lecture Notes in Comput. Sci., vol. 3669, pp. 448\u2013459. Springer, Berlin (2005)","DOI":"10.1007\/11561071_41"},{"key":"282_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6, 85\u2013112 (2010)","journal-title":"Theory Comput."},{"key":"282_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when $$1-1\/d$$ is the best possible exponent for $$d$$-dimensional geometric problems [extended abstract]. In: 30th Annual Symposium on Computational Geometry (Kyoto 2014), pp. 67\u201376. ACM, New York (2014)","DOI":"10.1145\/2582112.2582124"},{"key":"282_CR21","doi-asserted-by":"crossref","unstructured":"Papadimitriou, Ch.H.: The Euclidean traveling salesman problem is $$NP$$-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","DOI":"10.1016\/0304-3975(77)90012-3"},{"issue":"1","key":"282_CR22","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"282_CR23","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory Ser. B 62(2), 323\u2013348 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"key":"282_CR24","doi-asserted-by":"crossref","unstructured":"Salowe, J.S.: Construction of multidimensional spanner graphs, with applications to minimum spanning trees. In: 7th Annual Symposium on Computational Geometry (North Conway 1991), pp. 256\u2013261. ACM, New York (1991)","DOI":"10.1145\/109648.109677"},{"key":"282_CR25","unstructured":"Sidiropoulos, A., Sridhar, V.: Algorithmic interpretations of fractal dimension. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol.\u00a077, # 58. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"282_CR26","unstructured":"Smith, W.D., Wormald, N.C.: Geometric separator theorems & applications. In: 39th Annual Symposium on Foundations of Computer Science (Palo Alto 1998), pp. 232\u2013243. IEEE, Los Alamitos (2006)"},{"key":"282_CR27","volume-title":"Fractals in the Physical Sciences. Theory and Applications. Nonlinear Science","author":"H Takayasu","year":"1990","unstructured":"Takayasu, H.: Fractals in the Physical Sciences. Theory and Applications. Nonlinear Science. Manchester University Press, Manchester (1990)"},{"key":"282_CR28","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: 36th Annual ACM Symposium on Theory of Computing (Chicago 2004), pp. 281\u2013290. ACM, New York (2004)","DOI":"10.1145\/1007352.1007399"},{"issue":"3","key":"282_CR29","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"PM Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in $$k$$ dimensions. Discrete Comput. Geom. 6(3), 369\u2013381 (1991)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00282-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00282-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00282-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T15:10:21Z","timestamp":1623251421000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00282-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,28]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["282"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00282-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2021,5,28]]},"assertion":[{"value":"27 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}