Research activity 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
2) Homotopy and Topology Preservation
3) Definition of surfaces as subsets of Z3.
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).
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.
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.
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.