R. Malgouyres, A Definition of surfaces of Z3: a new 3D Jordan theorem, Theoretical Computer Science, Vol. 186, pp. 1-41, 1997.

Abstract. We provide a local definition of surfaces in Z³ which generalize the 26-surfaces of D.G. Morgenthaler. The surfaces thus defined which are finite satisfy a 3D Jordan property (i.e. the complement of a finite surface has two connected components) and we provide an algorithmic characterization of interior points. Besides, each point of a finite surface is 6-adjacent to both an interior point and an exterior point.

R. Malgouyres, There is no local characterization of separating objects in Z3, Theoretical Computer Science, vol 163, pp 303-308, 1996.

Abstract. We prove that there is no local characterization of the class of objets S included in Z³, which separate Z³ in two 6-connected components, and such that any point of S is 6-adjacent to both 6-connected components of the complement of S.

G. Bertrand, R. Malgouyres, Some Topological Properties of Discrete surfaces, Journal of Mathematical Imaging and Vision (JMIV), 11, pp 207-221, 1999.

Abstract. A basic property of a simple closed surface is the Jordan property: the complement of the surface has two connected components. We call back-component any such component, and the union of a back-component and the surface is called the closure of this back-component. We introduce the notion of strong surface as a surface which satisfies a strong homotopy property: the closure of a back-component is strongly homotopic to that back-component. This means that we can homotopically remove any subset of a strong surface from the closure of a back-component. On the basis of some results on homotopy, and strong homotopy, we have proved that the simple closed 26-surfaces defined by Morgenthaler and Rosenfeld, and the simple closed 18-surfaces defined by one of the authors are both strong surfaces. Thus, strong surfaces appear as an interesting generalization of these two notions of a surface.

R. Malgouyres, Local characterization of strong surfaces within strongly separating objects, Pattern Recognition Letters, Vol. 19, pp 341-349, 1998.

Abstract. In a prior paper, a characteriztion of discrete surfaces of Z³ is proposed which is called strong surfaces. However, strong surfaces are defined by global properties and the question of their local characterization remains. We propose a local characterization, within the separating and thin objects, of strong surfaces.

R. Malgouyres, G. Bertrand, A New Local Property of Strong n-surfaces, Pattern Recognition Letters 20, pp 417-428, 1999.

Abstract. In prior papers, two characterizations of discrete surfaces of Z³ are proposed which are called strong 18-surfaces and strong 26-surfaces, and a local property of these surfaces is proposed. However, strong surfaces are defined by global properties and the question of their local characterization remains. We propose a new local characterization of those of the separating and thin objects which are strong surfaces.

R. Malgouyres, G. Bertrand, Complete Local Characterization of Strong 26-surfaces: Continuous Analogs for Strong 26-surfaces, International Journal on Pattern Recognition and Artificial Intelligence (IJPRAI), vol 13, no 4, pp 465-484, 1999.

Abstract. In a prior paper, two similar characterizations of discrete surfaces of Z³ are proposed which are called strong 18-surfaces and strong 26-surfaces. The proposed characterization consists in some natural global properties of surfaces. In this paper, we first give local necessary conditions for an object to be a strong 26-surface. An object satisfying these local properties is called a near strong 26-surface. Then we construct continuous analogs for near strong 26-surfaces and, using the continuous Jordan Theorem, we prove that the necessary local conditions previously introduced in fact give a complete local characterization of strong 26-surfaces: the class of near strong 26-surfaces coincides with the class of strong 26-surfaces.

R. Malgouyres, S. Fourey, Strong Surfaces, Surface Skeletons and Image Superimposition, SPIE, Vision Geometry VII, Vol. 3454, San Diego, California, pp. 16-27, July, 1998.

Abstract. After having recalled the definition and local properties of strong surfaces, we present a related new thinning algorithm with surface squeletton, and a specific application of these notions to superimposition (i.e. Matching) of RMN images of brains.

R. Malgouyres, Homotopy in 2-dimensional Digital Images, Theoretical Computer Science, vol. 230(1-2), pages 221-233, 2000.

Abstract. We recall the basic definitions concerning homotopy in 2D Digital Topology, and we set and prove several results concerning homotopy of subsets. Then we introduce an explicit isomorphism between the fundamental group of a 2D connected object and a (non abelian) free group. As a consequence, we provide an algorithm for deciding whether two closed path are homotopic.

R. Malgouyres, A. Lenoir, Topology Preservation Within Digital Surfaces, Graphical Models (GMIP) vol 62, pp 71-84 (2000).

Abstract. Given two connected subsets Y and X of the set of the surfels of a connected digital surface, with Y contained in X, we propose three equivalent way to express that Y is homotopic to X. The first characterization is based on sequential deletion of simple surfels. This characterization enables us to define thinning algorithms within a digital Jordan surface. The second characterization is based on the Euler characteristics of sets of surfels. This characterization enables us, given two connected sets Y and X of surfels, to decide whether Y is homotopic to X. The third characterization is based on of the (digital) fundamental group.

R. Malgouyres, Presentation of the Fundamental Group in Digital Surfaces, Proceedings of DGCI'99, Lecture Notes In Computer Science 1568, pp 136-150, Springer, 1999.

Abstract. As its analogue in the continuous framework, the digital fundamental group represents a major information on the topology of discrete objects. However, the fundamental group is an abstract information and cannot directly be encoded in a computer using its definition. A classical mathematical way to encode a discrete group is to find a presentation of this group. In this paper, we construct a presentation for the fundamental group of any subset of a digital surface. This presentation can be computed by an efficient algorithm.

R. Malgouyres and M. More, On the Computational Complexity of Basic Problems of 2D Digital Topology, To appear in vol 289/1 of the journal Theoretical Computer Science.

Abstract. We study the computational complexity of widely used problems of 2D digital topology. We prove that most of the considered problems (including reachability in 2D binary images, connectivity, lower homotopy and tree-homotopy) are in LogSpace. We prove that reachability in 2D binary images is NC¹-hard under AC⁰ reductions, and that reachability in permutation graphs is also NC¹-hard. Finaly, we prove that most of the considered problems are not in AC⁰.

R. Malgouyres, Computing the Fundamental Group in Digital Spaces, IJPRAI, vol 15, no 7, pp 1075-1088, 2001.

Abstract. As its analogue in the continuous framework, the digital fundamental group represents a major information on the topology of discrete objects. However, the fundamental group is an abstract information and cannot directly be encoded in a computer using its definition. A classical mathematical way to encode a discrete group is to find a presentation of this group. In this paper, we construct a presentation for the fundamental group of any graph, and in particular for any subset of Z³. This presentation can be computed by an efficient algorithm.