On the complexity of finding paths in a two-dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: (A) domains with polynomial-time computable boundaries, and (B) polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type (A) and type (B); and it has a polynomial-space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (C) 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.