On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
We study the computational complexity of some well-known problems of 2D digital topology. We prove that all considered problems (including reachability in 2D binary images, connectivity, lower homotopy and symmetric homotopy) are in LogSpace. We prove that reachability in 2D binary images and some other problems are NC1-hard. Finally, we prove that most of the considered problems are not in AC(0). (C) 2002 Elsevier Science B.V. All rights reserved.
computational complexity reachability digital topology homotopy