Orders and digital topology

Involved people : Gilles Bertrand, Michel Couprie, Christophe Lohou.

In the traditional approach introduced by A. Rosenfeld and named "digital topology", the elements of Zⁿ are linked by adjacency relations (for example the 4- or 8-adjacency in Z²). These relations induces a graph structure and allows the definition of topological notions such as conexity, border, simple curve. However, there is no way to build a topology, in the usual meaning of the term, from these notions.

Another approach has been introduced by E. Khalimsky and called "connected ordered topological spaces (COTS)". In this approach, we consider a set Hⁿ associated to Zⁿ, in which the smallest neighbohood of a point in Hⁿ differs from one point to another (Fig 1). Then a topology can be defined on Zⁿ. The approach based on cellular complexes which are elements of different dimensions called cells, allows as well to define a topology. In these two cases, the topology is an Alexandroff topology, that is a toplogy such that an intersection (finite or not) of open sets is an open set. It can be shown that an Alexandroff topology is equivalent to an order structure, that is a reflexive, transitive and antisymetrical relation. In the framework of orders, we propose a model of the notions based on the field of digital topology. To any object (subset) of Zⁿ, we associate an object in the order Hⁿ (see fig. 1). Then it becomes possible to "interpret" an object from Zⁿ in a space which has much more interesting propoerties. We validate our model by considering the fundamental notions of simple points and surfaces [ Ber99 , BC99 ].


(A)	(b)

Figure 1: (A): A subset X of Z² (black squares). (b): A subset of H² associated to X.
The vicinity of a square consists of itself and the eight smaller elements which surround it ; the vicinity of a rectangle consists of itself and the two discs which surround it ; the vicinity of a disc is composed only of this disc.