{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:59:35Z","timestamp":1778720375949,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T00:00:00Z","timestamp":1596499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T00:00:00Z","timestamp":1596499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/17-1"],"award-info":[{"award-number":["NI 369\/17-1"]}],"id":[{"id":"10.13039\/501100001659","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,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted considerable attention in the context of time series analysis (there called time series visibility graphs) with various practical applications in areas such as physics, geography, and medical sciences. Computing shortest paths in visibility graphs is a common task, for example, in line-of-sight communication. For time series analysis, graph characteristics involving shortest paths lengths (such as centrality measures) have proven useful. In this paper, we devise a fast output-sensitive shortest path algorithm on a superclass of terrain visibility graphs called terrain-like graphs (including all induced subgraphs of terrain visibility graphs). Our algorithm runs in\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(d^*\\log \\varDelta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>\u2217<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$d^*$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2217<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the length (that is, the number of edges) of the shortest path and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the maximum vertex degree. Alternatively, with an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time preprocessing our algorithm runs in\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(d^*)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>\u2217<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time.<\/jats:p>","DOI":"10.1007\/s00454-020-00226-8","type":"journal-article","created":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T19:02:42Z","timestamp":1596567762000},"page":"737-750","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Fast Shortest Path Algorithm on Terrain-like Graphs"],"prefix":"10.1007","volume":"66","author":[{"given":"Vincent","family":"Froese","sequence":"first","affiliation":[]},{"given":"Malte","family":"Renken","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,4]]},"reference":[{"issue":"1","key":"226_CR1","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1142\/S0218195993000038","volume":"3","author":"J Abello","year":"1993","unstructured":"Abello, J., E\u011fecio\u011flu, \u00d6.: Visibility graphs of staircase polygons with uniform step length. Int. J. Comput. Geom. Appl. 3(1), 27\u201337 (1993)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"226_CR2","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF02570710","volume":"14","author":"J Abello","year":"1995","unstructured":"Abello, J., E\u011fecio\u011flu, \u00d6., Kumar, K.: Visibility graphs of staircase polygons and the weak Bruhat order, I: from visibility graphs to maximal chains. Discrete Comput. Geom. 14(3), 331\u2013358 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"9","key":"226_CR3","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1007\/s00702-010-0450-3","volume":"117","author":"M Ahmadlou","year":"2010","unstructured":"Ahmadlou, M., Adeli, H., Adeli, A.: New diagnostic EEG markers of the Alzheimer\u2019s disease using visibility graph. J. Neural Transm. 117(9), 1099\u20131109 (2010)","journal-title":"J. Neural Transm."},{"key":"226_CR4","unstructured":"Ameer, S., Gibson-Lopez, M., Krohn, E., Soderman, S., Wang, Q.: Terrain visibility graphs: persistence is not enough (2020). arXiv:2004.00750"},{"key":"226_CR5","doi-asserted-by":"crossref","unstructured":"Ashur, S., Filtser, O., Katz, M.J., Saban, R.: Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. In: 17th International Workshop on Approximation and Online Algorithms (Munich 2019). Lecture Notes in Computer Science, vol. 11926. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-39479-0_1"},{"key":"226_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)"},{"key":"226_CR7","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"1","key":"226_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF01300372","volume":"14","author":"S-H Choi","year":"1995","unstructured":"Choi, S.-H., Shin, S.Y., Chwa, K.-Y.: Characterizing and recognizing the visibility graph of a funnel-shaped polygon. Algorithmica 14(1), 27\u201351 (1995)","journal-title":"Algorithmica"},{"key":"226_CR9","unstructured":"Colley, P.: Recognizing visibility graphs of unimonotone polygons. In: 4th Canadian Conference on Computational Geometry (St. John\u2019s 1992), pp. 29\u201334. Memorial University of Newfoundland, St. John\u2019s (1992)"},{"issue":"3","key":"226_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0925-7721(95)00033-X","volume":"7","author":"P Colley","year":"1997","unstructured":"Colley, P., Lubiw, A., Spinrad, J.: Visibility graphs of towers. Comput. Geom. 7(3), 161\u2013172 (1997)","journal-title":"Comput. Geom."},{"issue":"3","key":"226_CR11","doi-asserted-by":"publisher","first-page":"589","DOI":"10.2478\/s11600-012-0032-x","volume":"60","author":"RV Donner","year":"2012","unstructured":"Donner, R.V., Donges, J.F.: Visibility graph analysis of geophysical time series: potentials and possible pitfalls. Acta Geophys. 60(3), 589\u2013623 (2012)","journal-title":"Acta Geophys."},{"key":"226_CR12","doi-asserted-by":"crossref","unstructured":"Elsner, J.B., Jagger, T.H., Fogarty, E.A.: Visibility network of United States hurricanes. Geophys. Res. Lett. 36(16), #\u00a0L16702 (2009)","DOI":"10.1029\/2009GL039129"},{"issue":"1","key":"226_CR13","first-page":"108","volume":"6","author":"W Evans","year":"2015","unstructured":"Evans, W., Saeedi, N.: On characterizing terrain visibility graphs. J. Comput. Geom. 6(1), 108\u2013141 (2015)","journal-title":"J. Comput. Geom."},{"key":"226_CR14","unstructured":"Froese, V., Renken, M.: Advancing through terrains (2019). arXiv:1904.08746"},{"key":"226_CR15","doi-asserted-by":"crossref","unstructured":"Gao, Z.-K., Cai, Q., Yang, Y.-X., Dang, W.-D., Zhang, S.-S.: Multiscale limited penetrable horizontal visibility graph for analyzing nonlinear time series. Sci. Rep. 6, #\u00a035622 (2016)","DOI":"10.1038\/srep35622"},{"issue":"1","key":"226_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"SK Ghosh","year":"1991","unstructured":"Ghosh, S.K.: Computing the visibility polygon from a convex set and related problems. J. Algorithms 12(1), 75\u201395 (1991)","journal-title":"J. Algorithms"},{"key":"226_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility Algorithms in the Plane","author":"SK Ghosh","year":"2007","unstructured":"Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, New York (2007)"},{"key":"226_CR18","doi-asserted-by":"crossref","unstructured":"Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv. 46(2), #\u00a021 (2013)","DOI":"10.1145\/2543581.2543589"},{"key":"226_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L Guibas","year":"1987","unstructured":"Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209\u2013233 (1987)","journal-title":"Algorithmica"},{"issue":"12","key":"226_CR20","doi-asserted-by":"publisher","first-page":"2421","DOI":"10.1016\/j.physa.2011.02.031","volume":"390","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Mansour, T., Severini, S.: A characterization of horizontal visibility graphs and combinatorics on words. Physica A 390(12), 2421\u20132428 (2011)","journal-title":"Physica A"},{"key":"226_CR21","doi-asserted-by":"crossref","unstructured":"Hershberger, J.: Finding the visibility graph of a simple polygon in time proportional to its size. In: 3rd Annual Symposium on Computational Geometry, pp. 11\u201320. ACM, New York (1987)","DOI":"10.1145\/41958.41960"},{"issue":"2","key":"226_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. 4(2), 63\u201397 (1994)","journal-title":"Comput. Geom."},{"issue":"13","key":"226_CR23","doi-asserted-by":"publisher","first-page":"4972","DOI":"10.1073\/pnas.0709247105","volume":"105","author":"L Lacasa","year":"2008","unstructured":"Lacasa, L., Luque, B., Ballesteros, F., Luque, J., Nuno, J.C.: From time series to complex networks: the visibility graph. Proc. Nat. Acad. Sci. USA 105(13), 4972\u20134975 (2008)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"issue":"13","key":"226_CR24","doi-asserted-by":"publisher","first-page":"2675","DOI":"10.1016\/j.physa.2010.02.043","volume":"389","author":"C Liu","year":"2010","unstructured":"Liu, C., Zhou, W.-X., Yuan, W.-K.: Statistical properties of visibility graph of energy dissipation rates in three-dimensional fully developed turbulence. Physica A 389(13), 2675\u20132681 (2010)","journal-title":"Physica A"},{"issue":"3","key":"226_CR25","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1140\/epjst\/e2016-60164-1","volume":"226","author":"B Luque","year":"2017","unstructured":"Luque, B., Lacasa, L.: Canonical horizontal visibility graphs are uniquely determined by their degree sequence. Eur. Phys. J. Special Top. 226(3), 383\u2013389 (2017)","journal-title":"Eur. Phys. J. Special Top."},{"key":"226_CR26","doi-asserted-by":"crossref","unstructured":"Luque, B., Lacasa, L., Ballesteros, F., Luque, J.: Horizontal visibility graphs: exact results for random time series. Phys. Rev. E 80(4), #\u00a0046103 (2009)","DOI":"10.1103\/PhysRevE.80.046103"},{"issue":"1","key":"226_CR27","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/TPAMI.1979.4766871","volume":"1","author":"LG Shapiro","year":"1979","unstructured":"Shapiro, L.G., Haralick, R.M.: Decomposition of two-dimensional shapes by graph-theoretic clustering. IEEE Trans. Pattern Anal. Mach. Intell. 1(1), 10\u201320 (1979)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"226_CR28","doi-asserted-by":"crossref","unstructured":"Stephen, M., Gu, C., Yang, H.: Visibility graph based time series analysis. PLoS ONE 10(11), #\u00a0e0143015 (2015)","DOI":"10.1371\/journal.pone.0143015"},{"issue":"1","key":"226_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S Suri","year":"1986","unstructured":"Suri, S.: A linear time algorithm for minimum link paths inside a simple polygon. Comput. Vis. Graph. Image Process. 35(1), 99\u2013110 (1986)","journal-title":"Comput. Vis. Graph. Image Process."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00226-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00226-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00226-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,3]],"date-time":"2021-08-03T23:36:40Z","timestamp":1628033800000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00226-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,4]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["226"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00226-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,4]]},"assertion":[{"value":"5 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}