Connectivity in Digital Pictures

Natural concepts of connectedness and simple-connectedness are defined for subsets of a digital picture. It is shown that every simply-connected object (with more than one element) in such a picture has elements which can be deleted without destroying its simpleconnectedness. This makes it easy to prove that a well-known "shrinking" algorithm always works--that is, shrinks any simply-connected object down to a single element. It also becomes easy to show that the natural "edge-following" algorithm, in which one "keeps one's hand on the wall," follows completely around the edge of any simply-connected object; this result in turn can be used to show that a well-known "border-following" algorithm (in which one follows the border elements of the object rather than the "cracks" between the object and its complement) always works. Various related questions are also treated, among them, that of whether there can exist a "parallel" shrinking algorithm.