{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:18:21Z","timestamp":1760440701368},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2007,10,3]],"date-time":"2007-10-03T00:00:00Z","timestamp":1191369600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2008,3]]},"DOI":"10.1007\/s00454-007-9019-9","type":"journal-article","created":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T12:37:19Z","timestamp":1191328639000},"page":"17-37","source":"Crossref","is-referenced-by-count":28,"title":["Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D"],"prefix":"10.1007","volume":"39","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Soss","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,3]]},"reference":[{"key":"9019_CR1","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 1\u201356. American Mathematical Society, Providence (1999)"},{"key":"9019_CR2","unstructured":"Agarwal, P.K., Klein, R., Knauer, C., Sharir, M.: Computing the detour of polygonal curves. Technical Report B 02-03, Freie Universit\u00e4t Berlin, Fachbereich Mathematik und Informatik (2002)"},{"key":"9019_CR3","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1006\/jagm.1994.1038","volume":"17","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. J. Algorithms 17, 292\u2013318 (1994)","journal-title":"J. Algorithms"},{"key":"9019_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(00)00233-X","volume":"109","author":"O. Aichholzer","year":"2001","unstructured":"Aichholzer, O., Aurenhammer, F., Icking, C., Klein, R., Langetepe, E., Rote, G.: Generalized self-approaching curves. Discrete Appl. Math. 109, 3\u201324 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9019_CR5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/B978-044482537-7\/50004-8","volume-title":"Handbook of Computational Geometry","author":"H. Alt","year":"2000","unstructured":"Alt, H., Guibas, L.J.: Discrete geometric shapes: Matching, interpolation, and approximation. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121\u2013153. Elsevier, Amsterdam (2000)"},{"key":"9019_CR6","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s00453-003-1042-5","volume":"38","author":"H. Alt","year":"2004","unstructured":"Alt, H., Knauer, C., Wenk, C.: Comparison of distance measures for planar curves. Algorithmica 38, 45\u201358 (2004)","journal-title":"Algorithmica"},{"key":"9019_CR7","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/B978-044482537-7\/50006-1","volume-title":"Handbook of Computational Geometry","author":"F. Aurenhammer","year":"2000","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 201\u2013290. Elsevier, Amsterdam (2000)"},{"key":"9019_CR8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.tcs.2004.05.019","volume":"324","author":"P. Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Competitive online routing in geometric graphs. Theor. Comput. Sci. 324, 273\u2013288 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9019_CR9","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/PL00009478","volume":"22","author":"T.M. Chan","year":"1999","unstructured":"Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22(4), 547\u2013567 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9019_CR10","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0925-7721(03)00046-4","volume":"27","author":"A. Ebbers-Baumann","year":"2004","unstructured":"Ebbers-Baumann, A., Klein, R., Langetepe, E., Lingas, A.: A fast algorithm for approximating the detour of a polygonal chain. Comput. Geom. Theory Appl. 27, 123\u2013134 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9019_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02187784","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The complexity and construction of many faces in arrangements of lines and of segments. Discrete Comput. Geom. 5, 161\u2013196 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9019_CR12","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF02712875","volume":"16","author":"J. Erickson","year":"1996","unstructured":"Erickson, J.: New lower bounds for Hopcroft\u2019s problem. Discrete Comput. Geom. 16, 389\u2013418 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9019_CR13","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S.J. Fortune","year":"1987","unstructured":"Fortune, S.J.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153\u2013174 (1987)","journal-title":"Algorithmica"},{"key":"9019_CR14","unstructured":"Gr\u00fcne, A.: Umwege in Polygonen. Master\u2019s thesis, Institut f\u00fcr Informatik I, Universit\u00e4t Bonn (2002)"},{"key":"9019_CR15","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/BF02187744","volume":"4","author":"L.J. Guibas","year":"1989","unstructured":"Guibas, L.J., Sharir, M., Sifrony, S.: On the general motion planning problem with two degrees of freedom. Discrete Comput. Geom. 4, 491\u2013521 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9019_CR16","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9019_CR17","doi-asserted-by":"crossref","unstructured":"Icking, C., Klein, R.: Searching for the kernel of a polygon: a\u00a0competitive strategy. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp.\u00a0258\u2013266 (1995)","DOI":"10.1145\/220279.220307"},{"key":"9019_CR18","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1017\/S0305004198003016","volume":"125","author":"C. Icking","year":"1999","unstructured":"Icking, C., Klein, R., Langetepe, E.: Self-approaching curves. Math. Proc. Camb. Philos. Soc. 125, 441\u2013453 (1999)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9019_CR19","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1145\/1017460.1017461","volume":"51","author":"V. Koltun","year":"2004","unstructured":"Koltun, V.: Almost tight upper bounds for vertical decompositions in four dimensions. J. ACM 51, 699\u2013730 (2004)","journal-title":"J. ACM"},{"key":"9019_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/3-540-45841-7_20","volume-title":"Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002)","author":"S. Langerman","year":"2002","unstructured":"Langerman, S., Morin, P., Soss, M.: Computing the maximum detour and spanning ratio of planar chains, trees and cycles. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002). Lecture Notes in Computer Science, vol. 2285, pp. 250\u2013261. Springer, Berlin (2002)"},{"issue":"2","key":"9019_CR21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9019_CR22","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852\u2013865 (1983)","journal-title":"J. ACM"},{"issue":"3","key":"9019_CR23","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":"9019_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0305004100071875","volume":"115","author":"G. Rote","year":"1994","unstructured":"Rote, G.: Curves with increasing chords. Math. Proc. Camb. Philos. Soc. 115, 1\u201312 (1994)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9019_CR25","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-007-9019-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-007-9019-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-007-9019-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:34Z","timestamp":1559072854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-007-9019-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,3]]},"references-count":25,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["9019"],"URL":"https:\/\/doi.org\/10.1007\/s00454-007-9019-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,3]]}}}