Computational geometry.
Équipe GEOMETRICA
INRIA Saclay Île-de-France
1 rue Honoré d'Estienne d'Orves
Bâtiment Alan Turing
Campus de l'École Polytechnique
91120 Palaiseau
FRANCE
Nozha Boujemaa
Nozha DOT Boujemaa AT inria DOT fr
We often need to consider objects (physical or not) that we do not know exactly, but only through a point cloud that we assume approximates the object (or its boundary). Reconstructing the object consists in building an explicit discrete object (like a polyhedron) which resembles the original object, both by being geometrically close, but also by having the same topology (connected components, tunnels, cavities).
One natural thing to do with a point cloud is to replace each point with a small ball. In nice cases, the union of these balls is a reconstruction of the object (if an inconvenient one). And the nerve theorem tells us that starting from the point set, adding edges between two points whenever their balls intersect and triangles whenever the three balls have a common intersection, we obtain an object that has the same topology as the union of balls, and we are done. Sadly, nice cases are rare and essentially only happen for smooth surfaces.
However, we can compute the topology even in cases where we don't know how to reconstruct, using persistent homology. Briefly, instead of picking one magical radius for the balls, we take two and compare the results. The topological features common to the two unions of balls correspond precisely to those of the object, under very weak hypotheses. We even know that we can reconstruct the object taking the union of the small balls, and adding selected pieces of the larger balls.
We are thus tempted to do the same with the discrete objects given by the nerve theorem. We have two sets of points, segments, triangles and tetrahedra, one included in the other, and we want to find, for example starting from the smaller one and adding some objects from the larger one, something whose topological features are exactly those common to both and nothing more. In full generality, unless we are working the the plane, determining whether such a reconstruction exists is NP-complete. In some special cases (in particular if the smaller object is connected), it can be done in polynomial time.
The goal of the internship is to study this polynomial case in depth: