{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:54Z","timestamp":1759637874388},"reference-count":19,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computational complexity of finding a shortest path in a two\u2010dimensional domain is studied in the Turing machine\u2010based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial\u2010time computable two\u2010dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial\u2010time recognizable domains with polynomial\u2010time computable distance functions. It is proved that the shortest path problem has the polynomial\u2010space upper bound for domains of both type (A) and type (B); and it has a polynomial\u2010space lower bound for the domains of type (B), and has a #<jats:italic>P<\/jats:italic> lower bound for the domains of type (A). (\u00a9 2004 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200310120","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T16:01:01Z","timestamp":1096905661000},"page":"551-572","source":"Crossref","is-referenced-by-count":11,"title":["On the complexity of finding paths in a two\u2010dimensional domain I: Shortest paths"],"prefix":"10.1002","volume":"50","author":[{"given":"Arthur W.","family":"Chou","sequence":"first","affiliation":[]},{"given":"Ker\u2010I","family":"Ko","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00284-9"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979325456X"},{"key":"e_1_2_1_4_2","unstructured":"A. W.Chou andK.Ko A note on the complexity of distance functions of two\u2010dimensional domains. Preprint 2003."},{"key":"e_1_2_1_5_2","unstructured":"T. H.Cormen C. E.Leiserson R. L.Rivest andC.Stein Introduction to Algorithms 2nd ed. (MIT Press Cambridge MA 2001)."},{"key":"e_1_2_1_6_2","unstructured":"D.\u2010Z.Du andK.Ko Theory of Computational Complexity (John Wiley&Sons New York 2000)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"L.Guibas J.Hershberger D.Leven M.Sharir andR.Tarjan Linear time algorithms for visibility and shortest path problems inside simple polygons. In: Proceedings of the 2nd ACM Symposium on Computational Geometry pp. 1\u201313 (ACM New York 1986).","DOI":"10.1007\/BF01840360"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"L.Guibas J.Hershberger Optimal shortest path queries in a simple polygon. In: Proceedings of the 3rd ACM Symposium on Computational Geometry pp. 50\u201363 (ACM New York 1987).","DOI":"10.1145\/41958.41964"},{"key":"e_1_2_1_9_2","unstructured":"P.Henrici Applied and Computational Complex Analysis Vol. 1\u20133 (John Wiley&Sons New York 1974\u20131986)."},{"key":"e_1_2_1_10_2","unstructured":"J. E.Hopcroft J. T.Schwartz andM.Sharir Planning Geometry and Complexity of Robot Motion (Ablex Norwood (NJ) 1987)."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"K.Ko Complexity Theory of Real Functions (Birkh\u00e4user Boston 1991).","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00154-B"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"K.Ko Polynomial\u2010time computability in analysis. In: Handbook of Recursive Mathematics Vol. 2: Recursive Algebra Analysis and Combinatorics (Yu. L. Ershov et al. eds.) Studies in Logic and the Foundations of Mathematics Vol. 139 pp. 1271\u20131317 (Elsevier Amsterdam 1998).","DOI":"10.1016\/S0049-237X(98)80052-9"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(82)80003-0"},{"key":"e_1_2_1_15_2","unstructured":"K.Ko andK.Weihrauch On the measure of two\u2010dimensional regions with polynomial\u2010time computable boundaries. In: Proceedings of 11th IEEE Conference on Computational Complexity pp. 150\u2013159 (IEEE Piscataway (NJ) 1996)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"J.Mitchell andM.Sharir New results on shortest paths in three dimensions. In: Proc. 20th ACM Symposium on Computational Geometry (ACM New York 2004). To appear.","DOI":"10.1145\/997817.997839"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179911"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"M.Pour\u2010El andI.Richards Computability in Analysis and Physics (Springer\u2010Verlag Berlin et al. 1989).","DOI":"10.1007\/978-3-662-21717-7"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"R.Rettinger andK.Weihrauch The computational complexity of some Julia sets. In: Proceedings of the 35th ACM Symposium on Theory of Computing pp. 117\u2013185 (ACM New York 2003).","DOI":"10.1145\/780542.780570"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"K.Weihrauch Computable Analysis (Springer\u2010Verlag Berlin et al. 2000).","DOI":"10.1007\/978-3-642-56999-9"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200310120","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200310120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T21:01:05Z","timestamp":1697662865000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200310120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1002\/malq.200310120"],"URL":"https:\/\/doi.org\/10.1002\/malq.200310120","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10]]}}}