Research on Digital Topology

Here are some abstracts on digital topology. One of my topics of interest is Digital Topology. I'm now working more on graphics but I keep up-to-date on topology by reviewing papers and thesis. Digital topology consists in providing algorithmic tools (integer only algorithms) for Pattern Recognition, Image Analysis and Image Processing, using a discrete formalism for geometrical objets. The geometrical and topological discrete notions are not always well defined at first, and my work also consists in providing good definitions for the considered notions. The content of my work up to now consists of three main parts : 1) Complexity and Topology 2) Homotopy and Topology Preservation 3) Definition of surfaces as subsets of Z3. 1) Complexity and Topology If decision problems, such as characterizing the relation linking two geometrical objects which are the same up to some topology preserving transformation, are difficult in 3D, they are polynomial-time decidable in 2D. However, until now, the precise complexity of these decision operations was not known. In a paper written with M. More (LLAIC, University of Clermont 1), we investigate this problem. We prove that deciding of reachability and connectedness are LogSpace decidable, and that reachability is NC1-hard under AC0-reductions. This shows that, though reachability is in LogSpace, it might be difficult to be proved in NC1, and, should it be in NC1, then it would be one of the most difficult problems in NC1. Finally, we prove that none of the most commonly used operations of digital topology (such as deciding of connectedness) can be performed in parallel constant time using a polynomial number of processors (i.e. can be performed by an AC0 family of circuits) In a collaboration with A. Frances (Univ. Zaragoza, Spain), we have investigated the problem of deciding whether a simplicial complex collapses onto one of its subcomplex. This is an example of what a "continuous retraction", or "shrinking" can mean. For 2D-complexes, the problem is polynomial time decidable. For 3D-complexes, the problem of deciding whether a simplicial complex can be collapsed onto a 1D-complex is NP-complete. (not yet published, write an e-mail to get the paper). 2) Homotopy and Topology Preservation This part is itself subdivided into two kinds of problems: characterization of topology preservation for image analysis, and algorithms for computing algebraic invariants of discrete objects, such as the fundamental group, for pattern recognition. The problem of topology preservation comes from the fact that, in image analysis, we apply geometrical transformations to discrete objects. We often want the topology of the transformed object to be "equivalent" to the topology of the initial object. The first thing to do is first to well formalize this notion. I have proposed, with my student A.Lenoir, a robust solution in the digital space formed by a digital surface. What I consider as the begining of a solution in 3D has been proposed by T.Y.Kong, G.Bertrand, and other authors, though many questions are still opened in 3D. After having defined precisely topology preservation, we want to design and implement some topology preserving transformations, such as thinning. I have designed, together with my student S.Fourey some surface thinning algorithms using formal notions of a surface of Z3 such as mentionned in Part 2) Finaly, the most difficult is to (algorithmically) characterize the relation linking two geometrical objects which are the same up to some topology preserving transformation. From this question follows the second kind of questions mentionned in this section: computation of algebraic invariants. Up to now, the precise problem on which I have worked is the problem of representing in the memory of a computer the information constituted by the digital fundamental group. This invariant of disctete objects has been introduced in the framework of digital topology by T.Y.Kong. In mathematics, a classical way to encode some discrete groups is to find an algebraic presentation of these groups. I have provided an algebraic presentation of the fundamental group in 2D, within digital surfaces, and in 3D. The presentations I give can be obtained by an efficient algorithm. Then another question is to exploit the data obtained by these methods, and thus to provide what I expect to be powerfull tools for pattern recognition. 3)Definition of Surfaces as Subsets of Z3 The question is the following: given X a connected subset of Z3, under what conditions can we say that X is a surface? During my PhD, I have provided a definition, which was much more general and adapted to practical purposes than de definition of D.G.Morgenthaler, which was the first existing notion of a surface as a subset of Z3. Since my PhD, I have proposed, together with G.Bertrand, a new notion of a surface, strong surfaces, which generalize in turn the notion defined in my PhD thesis, and have a more "natural" definition. The definition of strong surfaces is global: it is based on the notion of strong homotopy between sets, which is a global property. However, we found local characterizations of strong surfaces, which are more adapted to practical purpose, such as surface thinning.