Journal of Applied Mathematics and Stochastic Analysis
Volume 3 (1990), Issue 1, Pages 27-55

Boundaries in digital planes

Efim Khalimsky,1 Ralph Kopperman,2 and Paul R. Meyer3

1College of Staten Island , CUNY, Staten Island 10301, NY, USA
2City College of New York, CUNY, New York 10031, NY, USA
3Lehman College, CUNY, Bronx 10468, NY, USA

Received 1 July 1989; Revised 1 November 1989

Copyright © 1990 Efim Khalimsky et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


The importance of topological connectedness properties in processing digital pictures is well known. A natural way to begin a theory for this is to give a definition of connectedness for subsets of a digital plane which allows one to prove a Jordan curve theorem. The generally accepted approach to this has been a non-topological Jordan curve theorem which requires two different definitions, 4-connectedness, and 8-connectedness, one for the curve and the other for its complement.

In [KKM] we introduced a purely topological context for a digital plane and proved a Jordan curve theorem. The present paper gives a topological proof of the non-topological Jordan curve theorem mentioned above and extends our previous work by considering some questions associated with image processing:

How do more complicated curves separate the digital plane into connected sets? Conversely given a partition of the digital plane into connected sets, what are the boundaries like and how can we recover them? Our construction gives a unified answer to these questions.

The crucial step in making our approach topological is to utilize a natural connected topology on a finite, totally ordered set; the topologies on the digital spaces are then just the associated product topologies. Furthermore, this permits us to define path, arc, and curve as certain continuous functions on such a parameter interval.