Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.

Conference version, full version is given in hal-03721463

In our companion paper "Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.

In this paper, we focus on one particular instance of the shape reconstruction problem, in which the shape we wish to reconstruct is an orientable smooth submanifold of the Euclidean space. Assuming we have as input a simplicial complex K that approximates the submanifold (such as the Čech complex or the Rips complex), we recast the reconstruction problem as a 𝓁₁-norm minimization problem in which the optimization variable is a chain of K. Providing that K satisfies certain reasonable conditions, we prove that the considered minimization problem has a unique solution which triangulates the submanifold and coincides with the flat Delaunay complex introduced and studied in a companion paper [D. Attali and A. Lieutier, 2022]. Since the objective is a weighted 𝓁₁-norm and the contraints are linear, the triangulation process can thus be implemented by linear programming.

This paper illustrates how convexity hypotheses help collapsing simplicial complexes. We first consider a collection of compact convex sets and show that the nerve of the collection is collapsible whenever the union of sets in the collection is convex. We apply this result to prove that the Delaunay complex of a finite point set is collapsible. We then consider a convex domain defined as the convex hull of a finite point set. We show that if the point set samples sufficiently densely the domain, then both the Cech complex and the Rips complex of the point set are collapsible for a well-chosen scale parameter. A key ingredient in our proofs consists in building a filtration by sweeping space with a growing sphere whose center has been fixed and studying events occurring through the filtration. Since the filtration mimics the sublevel sets of a Morse function with a single critical point, we anticipate this work to lay the foundations for a non-smooth, discrete Morse Theory.

Abstract Restricted Voronoi diagrams are a fundamental geometric structure used in many applications such as surface reconstruction from point sets or optimal transport. Given a set of sitesV= {vk}nk=1⊂ ℝdand a meshXwith vertices inℝdconnected by triangles, the restricted Voronoi diagram partitionsXby computing for each site the portion ofXfor which the site is the nearest. The restricted Voronoi diagram is the intersection between the regular Voronoi diagram and the mesh. Depending on the site distribution or the ambient space dimension computing the regular Voronoi diagram may not be feasible using classical algorithms. In this paper, we extend Lévy and Bonneel's approach [ LB12 ] based on nearest neighbor queries. We show that their method is limited when the sites are not located onX. We propose a new algorithm for computing restricted Voronoi which reduces the number of sites considered for each triangle of the mesh and scales smoothly when the sites are far from the surface.

International audience

We associate with each compact set X of Rn two real-valued functions cX and hX defined on R+ which provide two measures of how much the set X fails to be convex at a given scale. First, we show that, when P is a finite point set, an upper bound on cP(t) entails that the Rips complex of P at scale r collapses to the Cech complex of P at scale r for some suitable values of the parameters t and r. Second, we prove that, when P samples a compact set X, an upper bound on hX over some interval guarantees a topologically correct reconstruction of the shape X either with a Cech complex of P or with a Rips complex of P. Regarding the reconstruction with Cech complexes, our work compares well with previous approaches when X is a smooth set and surprisingly enough, even improves constants when X has a positive μ-reach. Most importantly, our work shows that Rips complexes can also be used to provide topologically correct reconstruction of shapes. This may be of some computational interest in high dimensions.

We study the simplification of simplicial complexes by repeated edge contractions. First, we extend to arbitrary simplicial complexes the statement that edges satisfying the link condition can be contracted while preserving the homotopy type. Our primary interest is to simplify flag complexes such as Rips complexes for which it was proved recently that they can provide topologically correct reconstructions of shapes. Flag complexes (sometimes called clique complexes) enjoy the nice property of being completely determined by the graph of their edges. But, as we simplify a flag complex by repeated edge contractions, the property that it is a flag complex is likely to be lost. Our second contribution is to propose a new representation for simplicial complexes particularly well adapted for complexes close to flag complexes. The idea is to encode a simplicial complex K by the graph G of its edges together with the inclusion-minimal simplices in the set difference G - K. We call these minimal simplices blockers. We prove that the link condition translates nicely in terms of blockers and give formulae for updating our data structure after an edge contraction. Finally, we observe in some simple cases that few blockers appear during the simplification of Rips complexes, demonstrating the efficiency of our representation in this context.

Sampling conditions for recovering the homology of a set using topological persistence are much weaker than sampling conditions required by any known polynomial time algorithm for producing a topologically correct reconstruction. Under the former sampling conditions which we call weak sampling conditions, we give an algorithm that outputs a topologically correct reconstruction. Unfortunately, even though the algorithm terminates, its time complexity is unbounded. Motivated by the question of knowing if a polynomial time algorithm for reconstruction exists under the weak sampling conditions, we identify at the heart of our algorithm a test which requires answering the following question: given two 2-dimensional simplicial complexes L ⊂ K, does there exist a simplicial complex containing L and contained in K which realizes the persistent homology of L into K? We call this problem the homological simplification of the pair (K, L) and prove that this problem is NP-complete, using a reduction from 3SAT.

A simple way to reconstruct a shape A from a sample P is to output an r-offset P + r B, where B = {x ∈ RN x ≤ 1} designates the unit Euclidean ball centered at the origin. Recently, it has been proved that the output P + r B is homotopy equivalent to the shape A, for a dense enough sample P of A and for a suitable value of the parameter r. In this paper, we extend this result and find convex sets C ⊂ RN, besides the unit Euclidean ball B, for which P + rC reconstructs the topology of A. This class of convex sets includes in particular N-dimensional cubes in RN. We proceed in two steps. First, we establish the result when P is an ε-offset of A. Building on this first result, we then consider the case when P is a finite noisy sample of A.

The main result of this paper is an extension of de Silva's Weak Delaunay Theorem to smoothly embedded curves and surfaces in Euclidean space. Assuming a sufficiently fine sampling, we prove that i + 1 points in the sample span an i-simplex in the restricted Delaunay triangulation iff every subset of the i + 1 points has a weak witness.

Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract simplicial complexes that correspond to minimal inclusion-exclusion formulas. They include the dual complex, as defined in [2], and are characterized by the independence of their simplices and by geometric realizations with the same underlying space as the dual complex.

It is well known that the complexity of the Delaunay triangulation of N points in R 3, i.e. the number of its faces, can be O (N2). The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface.In this paper, we bound the complexity of the Delaunay triangulation of points distributed on generic smooth surfaces of R 3. Under a mild uniform sampling condition, we show that the complexity of the 3D Delaunay triangulation of the points is O(N log N).

Constrictions on a surface are defined as simple closed curves whose length is locally minimal. In particular, constrictions are periodic geodesics. We use constrictions in order to segment objects. In [4], we proposed an approach based on progressive surface simplification and local geodesic computation. The drawback of this approach is that constrictions are approximated by closed piecewise geodesics which are not necessarily periodic geodesics. In this paper, we compute constrictions starting from the closed piecewise geodesics previously computed and moving them on the surface. We compare the location of the initial closed piecewise geodesics to the location of the constrictions. Finally, we define and compute different types of constrictions on a surface.

In this paper, we propose a new approach based on three-dimensional (3-D) medial axis transformation for describing geometrical shapes in three-dimensional images. For 3-D-images, the medial axis, which is composed of both curves and medial surfaces, provides a simplified and reversible representation of structures. The purpose of this new method is to classify each voxel of the three-dimensional images in four classes: boundary, branching, regular and arc points. The classification is first performed on the voxels of the medial axis. It relies on the topological properties of a local region of interest around each voxel. The size of this region of interest is chosen as a function of the local thickness of the structure. Then, the reversibility of the medial axis is used to deduce a labeling of the whole object. The proposed method is evaluated on simulated images. Finally, we present an application of the method to the identification of bone structures from 3-D very high-resolution tomographic images.

3D-shape description requires the partition of objects in different parts. We propose a new approach based on the analysis of a 3D skeleton. The skeleton is a representation of objects by their axis of symmetry. In 3D, it is composed of surfaces associated with plate-like parts of the object and curves associated with cylindrical parts. Our method is two parts. First, four types of skeleton points are identified: boundary, branching, regular and arc points. A skeleton point is labeled according to the intersection of its maximal ball with the object. In order to add tolerance to the process, the radius of maximal balls is slightly increased. Second, the reversibility of the skeleton is used to deduce a labeling of the whole object. Finally, we present an application of the method to the identification of bone structures from 3D high-resolution tomographic images.

In thw paper, the problem of reconstructing a surface, given a set of scattered data points is addressed.First, a precise formulation of the reconstruction problem is proposed.The solution is mathematically defined as a particular mesh of the surface called the normalized mesh.This solution has the property to be included inside the Delaunay graph.A criterion to select boundary faces inside the Delaunay graph is proposed.This criterion is proven to provide the exact solution in 2D for points sampling a r-regular shapes with a sampling path c < 0.38r.In 3D, this results cannot be extended and the criterion cannot retrieve every faces.Some heuristics are then proposed in order to complete the surface.the object [4, 5, 6].More complex graphs have also been introduced like crhulls and a-shapes [7, 8].a-shapes are a generalization of the convex hull of a point set.An a-shape is a polytope surrounding the set of points.The parameter a controls the maximum "curvature" of any cavity of the polytope.Several a-shapes with different values of a are presented in figure 1.The choice of the parameter a might be tricky. O . .

We present a new method to reconstruct an implicit representation of a branching object from a set of data points scattered on its surface. The method is based on the computation of a geometric skeleton inside the data set. This skeleton is simplified in order to filter noise and converted into skeletal elements – a graph of interconnected curves – that generate an implicit surface. We use Bézier triangles as extra skeletal elements to perform bulge free blends between branches while controlling the blend extent. The result is a smooth reconstruction of the object, that can be computed whatever its topology. The skeleton offers compact storage, and provides an underlying structure for the reconstructed object, making it easier to edit in a modeling or animation environment.

The skeleton of an object is the locus of the centers of maximal discs included in the shape. The skeleton provides a compact representation of objects, useful for shape description and recognition. A well-known drawback of the skeleton transformation is its lack of continuity. This paper is concerned with the modeling of noise that may affect objects and the consequence of this noise on the skeleton. A graph (called the parameter graph) is introduced, on which branches due to noise are characterized. We deduce from this preliminary study a method to simplify skeletons. It depends on thresholds that can be chosen directly on the parameter graph associated to each skeleton.

This paper presents an approach to approximate the skeleton of continuous shapes either in 2D or 3D space. The data required is a sampling of the boundary of the shape. The authors call polyball any finite union of balls. A preliminary work on polyballs shows that their skeletons consist of simple components (line segments in 2D and polygons in 3D). To construct these components, only the computation of a Voronoi graph is required. Previous papers have proposed to approximate the skeleton of continuous shapes using the Voronoi graph of boundary points. An original reformulation of these methods is presented here, using polyballs. It allows one to build a hierarchy of simplified skeletons. An application in the frame of a European project in the field of medicine and biology is also presented. The skeleton by influence zones is computed in real time, which validates the authors' approach.