Maxime Lhuillier
email: maxime.lhuillier@univ-bpclermont.fr

Overview of Shelling for 2-Manifold Surface Reconstruction based on 3D Delaunay Triangulation

Keywords: Reconstruction, Volumetric models, Shellability, 3D Delaunay Triangulation, Star-Shapes

Recently, methods have been proposed to reconstruct a 2-manifold surface from a sparse cloud of points estimated from an image sequence. Once a 3D Delaunay triangulation is computed from the points, the surface is searched by growing a set of tetrahedra whose boundary is maintained 2-manifold. Shelling is a step that adds one tetrahedron at once to the growing set. This paper surveys properties that helps to understand the shelling performances: shelling provides most tetrahedra enclosed by the final surface but it can "get stuck" or block in unexpected cases.

Introduction

In the recent years, a family of 2-manifold surface reconstruction methods have been proposed to deal with a sparse cloud of input points and their visibility information estimated from an image sequence. There are both batch [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] and incremental [START_REF] Yu | Incremental reconstruction of a manifold surface from sparse visual mapping[END_REF][START_REF] Litvinov | Incremental solid modeling from sparse and omnidirectional structure-from-motion data[END_REF][START_REF] Litvinov | Incremental solid modeling from sparse structure-from-motion data with improved visual artifacts removal[END_REF][START_REF] Romanoni | Incremental reconstruction of urban environments by edge-point Delaunay triangulation[END_REF] variations. First a 3D Delaunay triangulation is computed from the sparse point cloud to divide up the space by a set T of tetrahedra. Then the visibility information is used to associate a free-space score to every tetrahedron ∆ ∈ T , e.g. by counting the rays (line segments between points and camera poses used to reconstruct these points) that intersect ∆. Last these scores are used for growing a set O of tetrahedra in T such that the boundary ∂O of O is maintained 2-manifold.

Several operations are designed for the O growing. One of them adds one tetrahedron at once to O and is closely related to the "shelling" process that is studied in Combinatorial Topology: Algorithm 1 in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] generates a shelling in the 3D case if O is initialized by a single tetrahedron. This greedy algorithm tries to add to O the tetrahedron in T \ O that has the largest visibility score (and that has a face triangle in ∂O) if ∂O is still a 2-manifold. The goal of the paper is to survey the shelling properties in our surface reconstruction context, where O is included in a 3D Delaunay triangulation and the O initialization is not restricted to a single tetrahedron. First Sec. 2 introduces prerequisites. Second, Sec. 3 provides our shelling definition and shows that it does not change the topology (number of connected components and genus) of ∂O in almost all cases. Third, Sec. 4 overviews shelling properties known in Combinatorial Topology, i.e. if O is initialized by a single tetrahedron. At first glance, one could guess that a shelling started by a single tetrahedron in T can reach/have every end value O e ⊆ T such that tetrahedron union ∪O e is homeomorphic to one tetrahedron. Surprisingly, this is wrong: some of these O e do not have such a shelling. This implies that no greedy algorithm [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF][START_REF] Romanoni | Incremental reconstruction of urban environments by edge-point Delaunay triangulation[END_REF] (whatever the free-space scoring of the tetrahedra) can reach O e . Furthermore, even if there is a shelling that reaches O e , a greedy algorithm can "get stuck" or block: it can generate another shelling with other tetrahedron choice(s) at the beginning such that the end value is strictly included in O e . Fourth, Sec. 5 studies shelling in the favorable case of star-shapes in a 3D Delaunay triangulation. We remind that ∪O is star-shaped with respect to the center c ∈ R 3 , if for every point x ∈ ∪O, the line segment xc ⊆ ∪O. More precisely, we show that there is a shelling that starts from O s and ends to O e ⊆ T if both ∪O s and ∪O e are star-shaped with respect to the same center. This generalizes a known case where ∪O e is convex (indeed, a convex set is star-shaped with respect to every of its point) and O s has a single tetrahedron. Then Sec. 5 explains why shelling provides most of the tetrahedra enclosed by the final surface in our context (shelling does not have excessive blocking). Last, Sec. [START_REF] Diestel | Graph theory[END_REF] provides examples of shelling blocking: a shelling starts from O s but cannot end to O e although ∪O s and ∪O e have the same topology. This should convince the reader that such cases really exist, although they don't in the 2D case [START_REF] Danaraj | A representation of 2-dimensional pseudomanifolds and its use in the design of a linear-time shelling algorithm[END_REF] (i.e. by replacing tetrahedra by triangles). The examples are chosen to be as simple as possible. Sec. 6 introduces a family of sets O that cannot be reached by a shelling started from a single tetrahedron (as in Sec. 4), which generalizes an example in [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF]. It also introduces examples of visual artifact similar to that in Fig. 1 of [START_REF] Litvinov | Incremental solid modeling from sparse structure-from-motion data with improved visual artifacts removal[END_REF] which cannot be removed by shelling alone (against the intuition).

Main prerequisites

The majority of prerequisites are in [START_REF] Derose | Reconstructing two-dimensional manifolds from scattered data: motivations and background[END_REF][START_REF] Vegter | Computational topology[END_REF][START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF][START_REF] Giblin | Graphs, surfaces and homology[END_REF][START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF].

Simplicial complexes in R n

Let integers k ≥ 0 and n > 0. A simplex σ is the convex hull of k + 1 points v 0 , • • • , v k in general position in R n ; σ is a vertex if k = 0, an edge if k = 1, a triangle if k = 2, a tetrahedron if k = 3. The dimension of σ is k. A simplex σ is a face of σ if σ is the convex hull of some of the v i above (we have σ ⊆ σ). A simplicial complex K in R n is a finite set of simplices in R n such that (1) σ ∈ K if σ is a face of σ ∈ K and (2) σ ∩ σ is empty or a face of σ and σ if both σ and σ are in K.

A 3D Delaunay triangulation is a simplicial complex K in R 3 that meets several conditions. There is a set T of tetrahedra such that the faces of the tetrahedra are the simplices in K. Let V be the vertex set of K. The circumscribing sphere of every tetrahedron in T does not contain a vertex in V in its interior. The convex hull of V is the union of the tetrahedra in T .

Closure, pure simplicial complex, boundary

Let A be included in a simplicial complex. The closure c(A) of A is the set of all faces (including the vertices) of the simplices in A. If both A and B are included in a same simplicial complex, c(A ∪ B) = c(A) ∪ c(B), c(A ∩ B) ⊆ c(A) ∩ c(B). If A ⊆ B, c(A) ⊆ c(B). We use notation c(σ

1 , • • • σ k ) = c({σ 1 , • • • σ k }) for simplices σ i .
Let X be a simplicial complex. We say that X is kD pure if there are simplices(s) σ i ∈ X with a same dimension k such that X = c(σ 1 , • • • σ m ). A 3D Delaunay triangulation K is 3D pure and meets K = c(T ) where T is the set of all tetrahedra in K.

If A is a set of simplices with a same dimension k > 0, the boundary ∂A of A is the set of all simplices of dimension k -1 in c(A) that are faces of exactly one simplex in A. The boundary ∂σ of a simplex σ is ∂{σ}.

Abstract simplicial complexes

Let V be a finite set. An abstract simplicial complex S is a set of subsets of V such that A ∈ S and B ⊂ A imply B ∈ S. It is implicitly defined by every simplicial complex K as follows: V is the vertex set of K and S is the set of the vertex sets of the K simplices. Conversely, K is a realization of S in R n . The elements of S are called (abstract) simplices; their faces are their subsets.

The definitions of edge/triangle/tetrahedron, closure, kD pure and boundary still hold for abstract simplices and abstract simplicial complexes, replacing simplices by abstract simplices and using their same inclusion relations. Same notations are used for a simplicial complex and its abstract version, and also for a simplex and its abstract version. We use bold fonts for vertices, e.g. ab is an edge (abstract or non-abstract).

Let c(T ) be a 3D Delaunay triangulation using a non-empty set T of tetrahedra. Every triangle in c(T ) is included in exactly two tetrahedra in c(T ), except those in ∂T (we have ∂T = ∅). These exceptions are removed as in [START_REF] Boissonnat | Triangulations in CGAL[END_REF][START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF] to make easier proofs. Let v ∞ be an abstract vertex that is different to those in c(T ). For every triangle abc ∈ ∂T , we create a new tetrahedron abcv ∞ by adding v ∞ to the set abc. Let T ∞ = T ∪ {abcv ∞ , abc ∈ ∂T }. Now T ⊂ T ∞ and every triangle in c(T ∞ ) is a face of exactly 2 tetrahedra in T ∞ . Notations T and T ∞ are used in the whole paper.

2-manifolds (with boundary), k-spheres, k-balls

Let A ⊆ R n and B ⊆ R m . If there is a bijective and continuous function between A and B such that the inverse function is also continuous, A and B are homeomorphic. We say that A is a 2-manifold with boundary if every point x ∈ A has a neighborhood in A that is homeomorphic to R 2 or R × R + (R + includes 0); A is a 2-manifold if every point x ∈ A has a neighborhood in A that is homeomorphic to R 2 ; A is a k-ball (k ∈ {1, 2, 3}) if it is homeomorphic to {x ∈ R k , ||x|| ≤ 1}; A is a k-sphere (k ∈ {1, 2}) if it is homeomorphic to {x ∈ R k+1 , ||x|| = 1}. 2-spheres are 2-manifolds, 2-manifolds and 2-balls are 2-manifolds with boundary.

Let Y ⊆ c(T ). We define |Y | = ∪Y = ∪ σ∈Y σ (here σ is a convex hull, it is not an abstract simplex). We say that Y is homeomorphic to

B if |Y | is homeomor- phic to B. Thus Y can be a 2-manifold/2-manifold with boundary/k-sphere/k-ball. Here are examples: a trian- gle in c(T ) is a 2-ball, ∂T is a 2-sphere, ∂∆ is a 2-sphere and ∆ is a 3-ball if tetrahedron ∆ ∈ c(T ). Let vertex series v 1 • • • v m where m ≥ 2. We use no- tation v 1 -v 2 -• • • -v m for the set of edges v 1 v 2 , v 2 v 3 , • • • , v m-1 v m . If the v i are distinct and every v i v i+1 ∈ c(T ), v 1 -v 2 -• • • -v m is a 1-ball. A cycle is an edge set v 1 -• • • -v m -v 1 such that m ≥ 3 and the v i are distinct.
A cycle is a 1-sphere if all its edges are in c(T ).

Here we merge Theorem 4 and Lemma 4 in [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF]:

Theorem 1 Let O ⊂ T ∞ be such that ∂O ⊂ c(T ) and ∂O is a 2-manifold. If ∆ is a tetrahedron in T \ O, ∂(O ∪ {∆}) is a 2-manifold iff c(O) ∩ c(∆) is 2D pure.

2-manifold criterion for simplicial complexes

If v is a vertex and E is a set of edges, v × E is the set of the triangles defined by joining v and every edge in E: v × E = {vab, ab ∈ E}. Let X be a set of triangles in c(T ). If a vertex v ∈ c(X), we define X v by the set of all triangles in X that include v. There is a set

E v of edges such that X v = v × E v . If E v is not a cycle, v is a singular vertex of X.
According to [START_REF] Vegter | Computational topology[END_REF][START_REF] Boissonnat | Geometric structures for threedimensional shape representation[END_REF][START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF], X is a 2-manifold iff for every vertex v ∈ c(X), there is a cycle a * such that

X v = v×a * . Thus there are distinct vertices a i ∈ c(X v ) such that a * = a 1 -• • • -a m -a 1 .
This implies that every edge vw ∈ c(X) is included in exactly two triangles in X (indeed, w is an a i and all a i are distinct).

According to [START_REF] Derose | Reconstructing two-dimensional manifolds from scattered data: motivations and background[END_REF][START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF], X is a 2-manifold with boundary iff for every vertex v ∈ c(X), there is a non-empty set of edge(s) a * such that X v = v × a * with two cases: there are distinct vertices a i such that

a * = a 1 -• • • a m or a * = a 1 -• • • a m -a 1 is a cycle (m ≥ 2 in
the first case and m ≥ 3 in the second case). Thus every a i ∈ c(X v ) and every edge vw ∈ c(X) is included in one or two triangle(s) in X (but not more).

Connectivity and genus

Let X ⊆ c(T ∞ ). We say that X is connected if for all vertices v and v in c(X), there are vertices v

i ∈ c(X) such that 1 ≤ i ≤ m, v = v 1 , v = v m and v 1 -v 2 -• • • -v m ⊆ c(X). A connected component X is a connected subset of X that is maximal in the inclusion sense. If two sets are homeomorphic, they have the same number of connected components. If X ⊆ c(T ), X is connected iff |X| is connected in R 3 .
If X is a set of simplices with a same dimension k, X is strongly connected if for all σ and σ in X, there are

σ i ∈ X such that 1 ≤ i ≤ m, σ 1 = σ, σ m = σ and every σ i ∩ σ i+1 is a k -1 dimensional simplex. For example, T ∞ , T and ∂T are strongly connected. If X is strongly connected, X is connected.
Let X ⊂ c(T ) be a connected 2-manifold. The genus g of X meets 2(1 -g) = v -e + t where v, e and t are the numbers of the vertices, edges and triangles in c(X), respectively. Two connected 2-manifolds in c(T ) are homeomorphic iff they have the same genus. The genus is the number of handle(s) of X, e.g. g = 0 if X is a 2-sphere, g = 1 if X is homeomorphic to a torus. The genus of a non-connected 2-manifold in c(T ) is the sum of genuses of its connected components.

Shelling definition and properties

First Sec. 3.1 provides our definition and explains the shelling algorithm in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF]. Then Sec. 3.2 describes the two cases of shelling steps. Last Sec. 3.3 details the topological changes in these two cases.

Definition

In our context (surface reconstruction), a shelling is a series of tetrahedron sets

O 0 , O 1 , • • • , O n such that 1. O 0 ⊆ T ∞ and ∂O 0 is a non-empty 2-manifold 2. O i+1 = O i ∪ {∆ i } where a tetrahedron ∆ i ∈ T \ O i and c(O i ) ∩ c(∆ i ) is a non-empty 2D-pure simplicial complex if 0 ≤ i < n.
Thus every ∂O i is a 2-manifold thanks to Theorem 1. Fig. 1 shows a shelling in the 2D case to help intuition: replace tetrahedra by triangles, 2-manifold by 1manifold (a disjoint union of cycles), 2D-pure by 1Dpure.

There is another definition in remark 8.3.ii of [START_REF] Ziegler | Lectures on polytope[END_REF] (see also remark 2 in chapter 7 of [START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF], and definition 2.7 of [12]): a shelling of a d-D pure simplicial complex K is a series σ

0 , σ 1 , • • • , σ n of d-D simplices such that K = c(σ 0 , σ 1 , • • • σ n ) and every c(σ 0 , σ 1 , • • • σ j-1 ) ∩ c(σ j ) is a non-empty (d -1)-D-pure simplicial complex. Both definitions are equivalent if d = 3 and O 0 = {σ 0 } ⊆ T and K ⊆ c(T ).
Our definition is different by two ways. First we prefer a cumulative formulation based on tetrahedron sets O i since our application computes surfaces ∂O i . Second a more general initialization O 0 is used since shellings are started at several steps of the surface reconstruction in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF]. Indeed, Theorem 2 Algorithm 1 in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] generates a shelling.

We describe this algorithm before the proof of Theorem 2. Let F ⊆ T be the free-space: a tetrahedron ∆ ∈ F iff there is a point x reconstructed from a view-point c using Computer Vision techniques such that ∆ ∩ cx = ∅. Let n ∆ be the number of line segments cx intersecting ∆. The goal is the computation of O ⊆ F that maximizes ∆∈O n ∆ subject to the constraint that ∂O is a 2-manifold. Let Q ⊆ F \ O be a set of tetrahedra that should be added to the current estimate of O. Furthermore, Q is included in the immediate neighborhood of O: every tetrahedron ∆ ∈ Q has a common triangle with a tetrahedron in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] for several initializations of Q and O.

O (if O = ∅), i.e. ∂∆ ∩ ∂O = ∅. At each step of Algorithm 1, we remove a tetrahedron ∆ from Q with the largest n ∆ , then we add ∆ to O if ∂O remains a 2-manifold. If ∆ is added to O, we also add to Q every tetrahedron ∆ ∈ F \ O such that ∂∆ ∩ ∂∆ = ∅. This algorithm stops when Q = ∅. It is used several times in

Proof This algorithm computes a series

O i (consecutive values of O) such that O i+1 = O i ∪ {∆ i }, ∆ i ∈ T \ O i , ∂∆ i ∩ ∂O i = ∅ and ∂O i is a 2-manifold for all i. According to Theorem 1, c(O i )∩c(∆ i ) is 2D pure. Since ∂∆ i ∩ ∂O i ⊆ c(O i ) ∩ c(∆ i ), c(O i ) ∩ c(∆ i ) is non-empty 2D pure.
Furthermore ∂O 0 is a non-empty 2-manifold (if the algorithm starts with O = ∅, set O 0 as the first tetrahedron added to O).

Basic properties

Several remarks can be done about shelling thanks to the following Lemma (this is Lemma 1 in [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF]).

Lemma 1 Let O ⊆ T ∞ and ∆ be a tetrahedron in T \ O. Then c(O) ∩ c(∆) is a simplicial complex in R 3 . Furthermore, c(O) ∩ c(∆) = c(∂O) ∩ c(∂∆) and the triangles in c(O) ∩ c(∆) are exactly those in ∂O ∩ ∂∆ (Fig. 2).
First the shelling definition is the same if we replace c(O i ) ∩ c(∆ i ) by c(∂O i ) ∩ c(∂∆ i ). Intuitively, this is the simplicial complex "between" O i and ∆ i . Second the number of the triangles in ∂O i ∩ ∂∆ i cannot be 0. Now we provide the two cases of shelling steps. They are in a corollary of the following theorem: Theorem 3 Let ∆ be a tetrahedron in T . Let K ⊆ c(∆) be a simplicial complex. Then K is a non-empty 2D-pure simplicial complex iff it is a 2-ball or a 2sphere. Let f be the number of the triangles in K. In the 2-ball case, f ∈ {1, 2, 3}. In the 2-sphere case, f = 4.

Proof We show that assertions A "K is a non-empty 2D-pure simplicial complex" and B "K is a 2-ball or a 2-sphere" are simultaneously true or false for every simplicial complex K ⊆ c(∆).

If K = ∅ or K = c(∆) or K has only one vertex, both A and B are wrong. Otherwise K has at least two vertices. If one of these vertices is not in an edge of K, K is not connected. Thus both A and B are wrong. Now we consider the case where an edge ab ∈ K and triangles abc / ∈ K and abd / ∈ K using notation abcd = ∆. Here A is wrong. Let points x = 2 3 a + 1 3 b and y = 1 3 a + 2 3 b. Assume (reductio ad absurdum) that B is true. Thus |K| \ {x, y} is homeomorphic to a 2ball or a 2-sphere minus two points, which is connected. This is impossible since |K| \ {x, y} has (at least) two connected components: xy \ {x, y} and another one included in (ax \ {x}) ∪ (by \ {y}) ∪ cda ∪ cdb.

Assume that we are not in the previous cases. Thus A is true. We show that B is true. We have triangles

t i ∈ ∂∆ and K = c(t 1 , t 2 , • • • , t f ) where f ≥ 1. If f = 4, K = c(∂∆) and K is a 2-sphere. If f = 1, |K| = t 1 is a 2-ball. If f = 3, |K| = t 1 ∪ t 2 ∪ t 3 is homeomorphic to t 4 (
use the piecewise linear function that is the identity at the t 4 vertices and maps the t 4 center to vertex t 1 ∩ t 2 ∩ t 3 ). If f = 2, |K| = t 1 ∪ t 2 is homeomorphic to t 3 (thanks to a similar piecewise linear function).

Corollary 1 A simplicial complex c(O i )∩c(∆ i ) is nonempty and 2D-pure (in the shelling definition) iff it is a 2-ball or a 2-sphere. Let f be the number of the triangles in ∂O i ∩ ∂∆ i . In the ball case,

1 ≤ f ≤ 3, otherwise f = 4. Proof The set K = c(O i ) ∩ c(∆ i ) is a simplicial com- plex (Lemma 1) included in c(∆ i ).
According to Theorem 3, K is non-empty and 2D-pure iff it is a 2-ball (f ∈ {1, 2, 3}) or a 2-sphere (f = 4).

Topology of surfaces ∂O i

Theorem 4 describes all topology change(s) by adding one tetrahedron in O i . The two following lemmas are needed in its proof (the former is Lemma 3 in [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF]. Proof We find a homeomorphism ϕ such that ϕ(|∂O|) = |∂(O ∪ {∆})|. First ϕ is defined by its values on vertices and linear interpolation on the ∂O triangles (or their subdivisions) as follows. For every vertex v in c(∂O), we set ϕ(v) = v. We use notation ∆ = abcd.

Lemma 2 Let O ⊂ T ∞ and ∆ be a tetrahedron in T \ O. Then ∂(O ∪ {∆}) = (∂∆ \ ∂O) ∪ (∂O \ ∂∆). Lemma 3 Let O ⊂ T ∞ be such that ∂O ⊂ c(T ) and ∂O is a 2-manifold. Let ∆ be a tetrahedron in T \ O such that c(O) ∩ c(∆) is 2D pure. Let f be the number of the triangles in ∂O ∩ ∂∆. If 1 ≤ f ≤ 3, ∂O and ∂(O ∪ {∆}) are homeomorphic.
If f = 1, ∂O ∩ ∂∆ = {abc}, we split abc into triangles abe, bce, cae where e = (a + b + c)/3, and set ϕ(e) = d. We obtain ϕ(abc) = abd ∪ bcd ∪ cad.

If f = 2, ∂O ∩ ∂∆ = {abc, bcd}, we split bc into edges be and ec where e = (b + c)/2, we split ad into edges ag and gd where g = (a + d)/2, and set ϕ(e) = g. Note that this scheme also splits every triangle including bc or ad into two other triangles. We obtain ϕ(abc ∪ bcd) = adb ∪ adc.

If f = 3, ∂O ∩ ∂∆ = {dab, dbc, dca}, we split abc into triangles abe, bce, cae where e = (a + b + c)/3, and reset ϕ(d) = e. We obtain ϕ(dab ∪ dbc ∪ dca) = abc. The three cases f ∈ {1, 2, 3} are in Fig. 3.

Second we check that every triangle t ∈ ∂O\∂∆ and ϕ |t (ϕ restricted to t) are unchanged by the modifications above. If t ∩ ∆ = ∅, both t and ϕ |t are unchanged. Now we assume t ∩ ∆ = ∅. Since c(T ) is a simplicial complex, t ∩ ∆ is a vertex or an edge of ∆. We consider several cases. If f = 1, t = abc and e is not a vertex of t. Thus both t and ϕ |t are unchanged. Assume (reductio ad absurdum) that f = 2 and bc ⊂ t. Thus bc is a face of three distinct triangles t, abc and bcd in ∂O, although ∂O is a 2-manifold (impossible). Assume (reductio ad absurdum) that f = 2 and ad ⊂ t.

in |∂O \ ∂∆|, ϕ(|∂O|) = ϕ(|∂O ∩ ∂∆| ∪ |∂O \ ∂∆|) (1)
= |∂∆ \ ∂O| ∪ |∂O \ ∂∆| (2) = |∂(O ∪ {∆})|. (3)
Fourth we show that ϕ is a homeomorphism. We only need to check that ϕ maps distinct vertices to distinct vertices [START_REF] Sakai | Simplicial homology, a short course[END_REF]. This is true if f = 2 and f = 3. Assume (reductio ad absurdum) that f = 1 and

d ∈ c(∂O). Thus d ∈ c(O) ∩ c(∆). Since triangles dab, dbc and dca are not in c(O) ∩ c(∆), c(O) ∩ c(∆) is not 2D pure (impossible). If f = 1, d = ϕ(e) is different
to all vertices in c(∂O) and we obtain the result.

Note that Appendix B of [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF] provides a first version of the proof of Lemma 3 without details on steps 2 and 4.

Theorem 4 In a shelling, all ∂O i are 2-manifolds with the same genus. If c(O i ) ∩ c(∆ i ) is a 2-ball, ∂O i+1 and ∂O i have the same number of connected components. If c(O i ) ∩ c(∆ i ) is a 2-sphere, ∂O i has one connected component more than ∂O i+1 (Fig. 4).

Proof Every ∂O i is a 2-manifold thanks to Theorem 1 and since ∂O 0 is a 2-manifold. Let f be the number of the triangles in ∂O i ∩ ∂∆ i . If f ∈ {1, 2, 3}, ∂O i+1 and ∂O i are homeomorphic thanks to Lemma 3. Therefore ∂O i+1 and ∂O i have the same genus and the same number of connected component(s). Now we study case f = 4. We have ∂∆ i ⊆ ∂O i and Lemma 2 implies

∂O i+1 = ∂O i \ ∂∆ i . Therefore ∂O i = ∂O i+1 ∪ ∂∆ i and ∂O i+1 ∩ ∂∆ i = ∅. Assume (reductio ad absurdum) that ∂∆ i is not a connected component of ∂O i . Thus these is an edge vv ∈ c(∂O i ) such that v ∈ c(∂∆ i ) and v / ∈ c(∂∆ i ). This implies that there is a triangle in ∂O i \ ∂∆ i that includes vv . Therefore v ∈ c(∂∆ i ) ∩ c(∂O i+1 ). Since ∂O i+1 is a 2- manifold, there is a cycle a * such that (∂O i+1 ) v = v × a * . Thus (v × a * ) ∪ (∂∆ i ) v ⊆ (∂O i ) v and (∂∆ i ) v \ v × a * = ∅,
which imply that v is a singular vertex of ∂O i (impossible). Since ∂∆ i is a connected component of ∂O i and ∂O i = ∂O i+1 ∪ ∂∆ i , ∂O i has one connected component more than ∂O i+1 . Last ∂O i+1 and ∂O i have the same genus since ∂∆ i has zero genus.

In most cases, c(O i ) ∩ c(∆ i ) is a 2-ball. In the few cases where ∆ i is a cavity of O i (O 0 can be like a piece of Swiss cheese that has cavities as in Fig. 4), c(O i )∩c(∆ i ) is a 2-sphere.

Corollary 2 describes a frequent case where shelling does not change the topology of ∂O i . We need

Lemma 4 If ∅ = O T ∞ , ∂O = ∅.
The proof of Lemma 4 is straightforward (T ∞ is strongly connected) and is in the supplementary material.

Corollary 2 Assume that O i ⊂ T ∞ and ∂O i is a 2- sphere in a shelling. If i ≤ j < n and O j+1 = T ∞ , c(O j ) ∩ c(∆ j ) is a 2-ball and ∂O j+1 is a 2-sphere. Proof We assume (induction) that ∂O j is a 2-sphere (this is OK if j = i) and show that c(O j ) ∩ c(∆ j ) is a 2-ball and ∂O j+1 is a 2-sphere if O j+1 = T ∞ .
Assume (reductio ad absurdum) that c(O j ) ∩ c(∆ j ) is a 2-sphere. Since ∂O j has one connected component, Theorem 4 implies that ∂O j+1 does not have a connected component, i.e. ∂O j+1 = ∅. Since ∅ = O j+1 T ∞ , this contradicts Lemma 4.

Thus c(O j ) ∩ c(∆ j ) is a 2-ball (Corollary 1) and ∂O j+1 is a 2-manifold with the same genus and the same number of connected component than ∂O j (Theorem 4), i.e. ∂O j+1 is a 2-sphere.

Overview of 3-ball shellability

This section summarizes previous works in Combinatorial Topology. Here we would like to know if O ⊆ T is shellable, i.e. if O can be the end value of a shelling started from a single tetrahedron. First Sec. 4.1 describes and compare several kinds of shellability and non-shellability. Second Sec. 4.2 presents invariant numbers and a necessary condition for the O shellability. Last Sec. 4.3 and 4.4 list positive and negative cases of shellability.

Definitions

According to Theorem 5 (supplementary material),

Theorem 5 Let O ⊆ T . Then O is a 3-ball iff ∂O is a 2-sphere.
assertions "O is a 3-ball" and "∂O is a 2-sphere" are equivalent in our context. Although the introduction of 3-balls seems useless, we mention it (and use it) since this formulation is often used in the bibliography.

A tetrahedron set O ⊆ T is shellable if there is a tetrahedron ∆ ∈ T and a shelling O 0 • • • O n such that O 0 = {∆} and O = O n . We also say that O 0 • • • O n is a shelling of O. Thanks to Corollary 2, we note that all ∂O i are 2-spheres and all c(O i ) ∩ c(∆ i ) are 2-balls. Thus O is a 3-ball. A 3-ball O ⊆ T is extendably shellable if for every shellable O ⊂ O, there is a shelling O 0 • • • O k such that O 0 = O and O k = O. In other words, every partial shelling of O can be completed to reach O. Therefore O is shellable if O is extendably shellable.
Extendable shellability is a convenient case of shellability. If O is extendably shellable and if a greedy algorithm constructs a shelling of O by choosing successive tetrahedra in O (e.g. Algorithm 1 in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] using F = O), the algorithm always succeeds, i.e. its final value is always O n = O. If O is shellable but non-extendably shellable, the greedy algorithm can choose tetrahedra at the shelling beginning such that it "gets stuck". This means that there is O i O in the shelling computation such that c(O i ) ∩ c(∆) is never non-empty 2D-pure for every tetrahedron ∆ tried by the algorithm (thus the algorithm stops). Thanks to Theorem 1, this means that

∂(O i ∪ {∆}) is not a 2-manifold (i.e. ∂(O i ∪ {∆}) has a singular vertex) or c(O i ) ∩ c(∆) = ∅.
A 3-ball O ⊆ T is strongly non-shellable if O has at least two tetrahedra and if for every tetrahedron ∆ ∈ O, c(∆)∩c(∂O) is not a 2-ball. Here we note that ∆ ∈ O in contrast to the shelling definition where

∆ i / ∈ O i . Ac- cording to Proposition 2.4.iv in [24], O is non-shellable if O is strongly non-shellable (principle of the proof: if O 0 • • • O n is a shelling of O, we have O = O n-1 ∪ {∆}, and see that c(∂O) ∩ c(∆) is a 2-ball as the complement of 2-ball c(∂O n-1 ) ∩ c(∆) in 2-sphere c(∂∆)).
Strongly non-shellability is an easy case of non-shellability for several reasons. First it is not difficult to check that a given O is strongly non-shellable. In comparison, it is quite more difficult to check that O is non-shellable: we don't know whether a polynomialtime algorithm can do that [START_REF] Edelsbrunner | Geometry and topology for mesh generation[END_REF]. Second, a strongly nonshellable O can be build with a few tetrahedra. Third, non-shellability and strongly non-shellability are related by Proposition 2.4.v in [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF]: if O is non-shellable, there is a strongly non-shellable 3-ball O ⊆ O (principle of the proof: construct a shelling of O in the reverse order if every 3-ball O ⊆ O is not strongly non-shellable). More details about the relations between strongly nonshellability and non-shellability are in the supplementary material.

h-numbers of O

The result described in this section is known for every dimension (Theorem 8.19 in [START_REF] Ziegler | Lectures on polytope[END_REF], see also Proposition 7.7 in [START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF]). Here we present a simpler (specialized) proof in our 3D case.

Let O be a 3-ball in T and f 0 (respectively, f 1 , f 2 and f 3 ) be the number of the vertices (respectively, edges, triangles and tetrahedra) in c(O). According to [START_REF] Ziegler | Lectures on polytope[END_REF][START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF], the definition of h-numbers h 1 , h 2 and h

3 of O is     1 h 1 h 2 h 3     = H     1 f 0 f 1 f 2     where H =     +1 0 0 0 -4 +1 0 0 +6 -3 +1 0 -4 +3 -2 +1     . ( 4
)
If O is shellable, we classify the shelling steps in three cases and all steps in a case update the numbers of the simplices by the same way. Thanks to this, Theorem 6 shows that the number of the steps in the j-th case is a function of the f i s, more precisely it is h j . The number of the steps in the j-th case is invariant to the shelling choice since h j does not depend on it.

Theorem 6 If O is shellable, every shelling of O has h j step(s) O i+1 = O i ∪ {∆ i } such that the number of the triangles in ∂O i ∩ ∂∆ i is equal to j. Proof If X ⊆ c(T ), we define the vector f (X) ∈ N 4 whose k-th coordinate is the number of k-1-dimensional simplices in c(X). Let O 0 • • • O n be a shelling of O and the tetrahedron ∆ i ∈ T \O i such that O i+1 = O i ∪{∆ i }. We will calculate δ i = f (c(O i+1 )) -f (c(O i )). Since c(O i+1 ) = c(O i )∪(c(∆ i )\c(O i )), δ i = f (c(∆ i )\ c(O i )). Let n i be the number of the triangles in ∂O i ∩ ∂∆ i and abcd = ∆ i . Since c(O i ) ∩ c(∆ i ) is a 2-ball,
there are three cases according to Corollary 1.

If

n i = 1, c(O i ) ∩ c(∆ i ) = c(abc). Thus c(∆ i ) \ c(O i ) = {d, da, db, dc, dab, dbc, dca, abcd}. We ob- tain δ i = 1 3 3 1 T .
If

n i = 2, c(O i ) ∩ c(∆ i ) = c(abc, bcd). Thus c(∆ i ) \ c(O i ) = {ad, adb, adc, abcd}. We obtain δ i = 0 1 2 1 T .
If

n i = 3, c(O i ) ∩ c(∆ i ) = c(abc, acd, adb). Thus c(∆ i )\c(O i ) = {bcd, abcd}. We obtain δ i = 0 0 1 1 T .
Let j ∈ {1, 2, 3} and h j be the number of the step(s)

O i+1 = O i ∪ {∆ i } such that n i = j. Let A =     4 1 0 0 6 3 1 0 4 3 2 1 1 1 1 1     and B =     0 1 0 0 0 0 1 0 0 0 0 1 -1 1 -1 1     . (5)
Since O 0 has one tetrahedron, f (c(O 0 )) = 4 6 4 1

T .

Now we have

f (c(O)) = f (c(O 0 )) + n-1 i=0 δ i = A 1 h 1 h 2 h 3 . (6)
Furthermore, Eqs. 6 and 5 imply

f 0 -f 1 + f 2 -f 3 = 1 -1 1 -1 f (c(O)) = 1, (7)
which in turn implies

f (c(O)) = f 0 f 1 f 2 f 3 = B 1 f 0 f 1 f 2 . (8)
Thanks to Eqs. 6 and 8 and since H = A -1 B, we obtain

1 h 1 h 2 h 3 = H 1 f 0 f 1 f 2 . (9)
Therefore h j = h j for j ∈ {1, 2, 3}.

We also see that a necessary condition for shellability is h 1 ≥ 0 and h 2 ≥ 0 and h 3 ≥ 0 (O is non-shellable if there is j such that h j < 0). Furthermore, the h j are consistent even if O is non-shellable:

Property 1 If O ⊆ T is a 3-ball, 1 + h 1 + h 2 + h 3 = f 3 .
Proof According to Eq. 4,

1 + h 1 + h 2 + h 3 = 1 1 1 1 H 1 f 0 f 1 f 2 (10) = -1 + f 0 -f 1 + f 2 . ( 11
)
Last we obtain the result thanks to Euler's relation for 3-balls [START_REF] Gallier | Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and Delaunay triangulation[END_REF], i.e.

f 0 -f 1 + f 2 -f 3 = 1.

Positive cases

First, all 3-balls with less than 9 vertices are extendably shellable and almost all 3-balls with 9 vertices are shellable [START_REF] Lutz | Combinatorial 3-manifold with 10 vertices[END_REF] (there are only 29 non-shellable 3-balls over the 2451305 combinatorial 3-balls with 9 vertices). Second, every 3D Delaunay T is a shellable 3-ball [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF][START_REF] Bruggesser | Shellable decomposition of cells and spheres[END_REF]. Thus every O ⊆ T such that |O| is convex is shellable. Indeed, such an O is the set of all tetrahedra of the 3D Delaunay triangulation defined by using only the vertices in c(O). Third Sec. 5 shows that O ⊆ T is shellable if |O| is star-shaped. This generalizes the convex case above, since a convex set is star-shaped with respect to every point in the convex set.

Negative cases

There is a survey [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF] of non-shellable 3-balls in a more general context than ours: some of them are constructed using a polytopal complex instead of a simplicial complex, i.e. the tetrahedra are replaced by convex hulls with n ≥ 4 vertices likes cubes. Since we focus on 3-balls included in a 3D Delaunay triangulation, they should be converted to analog examples in a 3D Delaunay. There are two kinds of examples: strongly non-shellable 3-balls defined by a small (ideally minimal) set of simplices, and non-shellable 3-balls defined by an important (not explicit) set of simplices and a global property. In the former, there is a 3-ball that has only 10 vertices and 21 tetrahedra (or 12 vertices and 25 tetrahedra). In the latter, there is a 3-ball called "Knotted hole ball" (K); K is non-shellable thanks to a property based on the knot theory: there is a knotted curve (a cycle of edges that cannot be included in a 2-sphere) with all edges on the boundary of K except one edge that is in K.

There are other negative cases. A 3D Delaunay triangulation T can be non-extendably shellable [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF]. Thus a greedy shelling algorithm can fail and miss O if O ⊆ T and |O| is convex. Last Sec. 6 provides a family of strongly non-shellable 3-balls that are not difficult to visualize in 3D. It includes the 3-ball with 12 vertices and 25 tetrahedra in [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF], which is in a 3D Delaunay triangulation. [START_REF] Edelsbrunner | An acyclicity theorem for cell complexes in d dimensions[END_REF] if O = T and O has a single tetrahedron.

O 0 • • • O n such that O 0 = O and O n = O . Such a result is sug- gested in
Here we need a non-degenerate case: c is not in a plane including a triangle of c(T ).

Summary

The proof has three main steps. First Sec. 5.2 provides useful lemmas and a star-shape criterion for a set of tetrahedra included in T (Theorem 7). Second Sec. 5.3 describes a visibility relation between two tetrahedra in T with respect to a view point c: ∆ is behind ∆ . Then Sec. 5.3 shows that there is a "front" tetrahedron in O \O for this relation (Theorem 8), i.e. this tetrahedron is not behind another one in O \ O. Third Sec. 5.4 shows that the front tetrahedron is added to O such that we obtain a shelling step (Theorem 9) thanks to Theorems 7 and 8 and lemmas. Then Sec. 5.4 shows the existence of a shelling between O and O (Corollary 3).

Last Sec. 5.5 presents a qualitative argument based on Corollary 3 to explain why the first shelling in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF] does not have excessive blocking.

Prerequisites

We give definitions before lemmas and theorems. If a and b are distinct points in R 3 , we distinguish the line

ab = {(1 -λ)a + λb, 0 ≤ λ ≤ 1} and ( 12
) (ab) = {(1 -λ)a + λb, λ ∈ R}. ( 13
) A point d is between a and b if d ∈ ab \ {a, b}. A set X ⊂ R 3 is star-shaped with respect to c (or X is c-star-shaped) if x ∈ X implies that xc ⊆ X. We say that O ⊆ T is c-star-shaped if |O| is c-star-shaped.
If t is a triangle in R 3 , the half-spaces of t are the two half-spaces of R 3 separated by the plane including t (each half-space includes the plane itself). Note that our non degenerate case implies that c is in exactly one half-space of every triangle in c(T ). Fig. 5 shows a starshape shelling in the 2D case (replace tetrahedron by triangle etc, as in Fig. 1).

We also use other notations in Sec. 5. Let σ be a simplex in R 3 and σ = σ \ |∂σ|, i.e. σ is the interior of σ. Let B(x, ) be the 3D ball centered at x ∈ R 3 with the radius > 0. If σ is a tetrahedron in R 3 , σ is an open set in R 3 , i.e. every point x ∈ σ is such that there is > 0 and B(x, ) ⊆ σ.

We need the three following lemmas to show Theorem 7 (the star-shape criterion) and others. The first two help to escape from degenerate configurations. The third one is a ray-tracing lemma, which provides a series of adjacent tetrahedra in T covering a line segment between two points in |T |.

Lemma 5 If a tetrahedron ∆ ∈ T and a point x ∈ ∆, ∆ is the only tetrahedron in T that contains x, and x is not in a triangle of c(T ). If a triangle t ∈ c(T ) and x ∈ t, t is the only triangle in c(T ) that contains x.

The proof of Lemma 5 is straightforward (c(T ) is a simplicial complex) and is in the supplementary material.

Lemma 6 Let A ⊆ T and points c ∈ |A|, x ∈ |A| \ c, y ∈ cx such that y / ∈ |A|. Let ∆ x be a tetrahedron in A such that x ∈ ∆ x .
There is a point x ∈ ∆x and a tetrahedron ∆ y ∈ T \ A and a point ỹ ∈ ∆y ∩ cx such that (cx) does not intersect the edges in c(T ) (Fig. 6).

Lemma 7 Let ∆ x be a tetrahedron in T and points x ∈ ∆x , y ∈ T \ {x} such that (xy) does not intersect the edges in c(T ). Let 7).

∆ 1 • • • ∆ 6 in T , every ∆ i ∩∆ i+1 is an edge (a triangle in 3D). Right: x λ maps [λ i , λ i+1 ] in ∆ i .
x λ = (1-λ)x+λy if λ ∈ R. There are integer k ≥ 1, reals λ 1 • • • λ k+1 , tetrahedra ∆ 1 • • • ∆ k in T such that λ i < λ i+1 if 1 ≤ i ≤ k, x λ ∈ ∆ i iff λ ∈ [λ i , λ i+1 ], every ∆ i ∩ ∆ i+1 is a triangle. If ∆ ∈ T and (xy) ∩ ∆ = ∅, ∆ is a ∆ i and (xy) ∩ ∆ = ∅ (Fig.
The proofs ot Lemma 6 and 7 are in Appendices A.1 and A.2). Theorem 7 converts the star-shape definition to a more tractable condition in our proof.

Theorem 7 Let O ⊆ T and a point c ∈ |O|. Then O is c-star-shaped iff every triangle t ∈ ∂O is a face of a tetrahedron ∆ ∈ O such that ∆ and c are in the same t half-space (Fig. 8). This is similar to star-shape tests in [START_REF] Varadhan | Topology preserving surface extraction using adaptive subdivision[END_REF][START_REF] Xia | Parameterization of a star-shaped volumes using green's functions[END_REF], which use outward-pointing normals at points on a volume boundary and a scalar product instead of our condition based on simplices. The proof is summarized in Fig. 8 and detailed in Appendix A.3.

Visibility in a 3D Delaunay triangulation

Let tetrahedra ∆ ∈ T and ∆ ∈ T . Let l be a half-line starting at c. We say that ∆ is behind [START_REF] Edelsbrunner | An acyclicity theorem for cell complexes in d dimensions[END_REF] ∆ if there is l such that l ∩ ∆ = ∅ and l ∩ ∆ = ∅ and ∆ = ∆ and every point in (l \ {c}) ∩ ∆ is between c and every point of (l \ {c}) ∩ ∆. Fig. 9 shows c, l, ∆ and ∆ .

The goal of Sec. 5.3 is Theorem 8: the existence of a "front" tetrahedron in O \ O, i.e. a tetrahedron which is not behind another one in O \ O. The proof is based on the fact that the relation "is behind" is acyclic in the 3D Delaunay triangulation T [START_REF] Edelsbrunner | An acyclicity theorem for cell complexes in d dimensions[END_REF]. It also needs the two following lemmas to generate "behind" relations. ∈ ∂O such that ∆ and c are not in the same t half-space. There is ∆ ∈ O \ O such that ∂∆ ∩ ∂O = ∅ and ∆ is behind ∆ (Fig. 9).

A sketch proof is provided before the proof for intuition. Let y be a point in ∆. Since O is c-star-shaped, y + λ(c-y) successively intersects tetrahedra ∆ 0 , ∆ 1 • • • ∆ k in O when λ increases from 0 to 1, and every ∆ i ∩∆ i+1 is not empty. We choose y such that ∆ i ∩ ∆ i+1 is a triangle for every i (cy does not intersect the edges in

c(T )). Since y ∈ ∆ = ∆ 0 ∈ O \ O and c ∈ ∆ k ∈ O, there is i such that ∆ i ∈ O \ O and ∆ i+1 ∈ O. We obtain ∆ = ∆ i (we have ∆ = ∆ if ∂∆ ∩ ∂O = ∅).
Proof First we set A = O ∪ {∆} and find points x and y that meet the assumptions of Lemma 6. Let x be the barycentre of t and ∆ x ∆ ∈ A. If t ∈ ∂T (reductio ad absurdum), both ∆ and c are in the same t halfspace since T is convex (impossible). Thus there is a tetrahedron ∆ ∈ T \ {∆} such that t = ∆ ∩ ∆ . Since Theorem 8 There is a tetrahedron ∆ ∈ O \ O such that ∂∆∩∂O = ∅ and every triangle t ∈ ∂∆\∂O is such that c and ∆ are in the same t half-space (Fig. 10).

∆ m ∩∆ m+1 is in ∂∆ ∩ ∂O. Note that x λ ∈ ∆ iff λ ∈ [λ j , λ j+1 ], x λ ∈ ∆ iff λ ∈ [λ m , λ m+1 ], λ j+1 ≤ λ m (since j < n ≤ m), c = x µ with µ ∈ [λ l , λ l+1 ] and λ m+1 ≤ λ l (since m < l). Thus ∆ is behind ∆ . Lemma 9 If O is c-star-shaped and O \ O = ∅, there is a tetrahedron ∆ ∈ O \ O such that ∂∆ ∩ ∂O = ∅. Proof Let ∆ be a tetrahedron in O \O. If ∂∆∩∂O = ∅, we obtain ∆ = ∆. Otherwise, ∂∆ ∩ ∂O = ∅. Note that c / ∈ ∆ (c / ∈ ∂∆
Proof Assume (reductio ad absurdum) that

∀∆ ∈ O \ O, ∂∆ ∩ ∂O = ∅ or ∃t ∈ ∂∆ \ ∂O such that
∆ and c are not in the same half-space of t.

Thus ∆ ∈ O \ O and ∂∆ ∩ ∂O = ∅ imply that ∆ meets the assumptions of Lemma 8. The principle of the proof is the following. We find an infinite series of tetrahedra ∆ i ∈ O \ O such that ∂∆ i ∩ ∂O = ∅ and ∆ i is behind ∆ i+1 for all i using Lemma 8. Since O is finite, there are m = n such that ∆ m = ∆ n , i.e. the relation "is behind" has a cycle. This contradicts [START_REF] Edelsbrunner | An acyclicity theorem for cell complexes in d dimensions[END_REF] which shows that this relation is acyclic in Delaunay triangulation T .

Here is the series. First Lemma 9 provides ∆ 0 ∈ O \O such that ∂∆ 0 ∩∂O = ∅. Now ∆ i+1 is defined from ∆ i as follow. If ∆ i ∈ O \O and ∂∆ i ∩∂O = ∅, ∆ i meets the assumptions of Lemma 8 (thanks to the reductio ad absurdum). Thus Lemma 8 provides

∆ i+1 ∈ O \O such that ∂∆ i+1 ∩ ∂O = ∅ and ∆ i is behind ∆ i+1 .

Proof of star-shape shelling

First we show in Theorem 9 that c(O) ∩ c(∆) is a 2-ball using the tetrahedron ∆ provided by Theorem 8. The proof highly relies on the fact that we are not in a degenerate case, i.e. c is not in a plane including a triangle of c(T ). It also requires the three following lemmas. Then a shelling between O and O is obtained in a corollary of Theorem 9. Lemma 11 Let abcd be a tetrahedron and K be a simplicial complex such that K ⊆ c(abcd 11). 11 The point vc ∩ t 1 according to Lemma 12. We have Proof Let triangles t i be such that

). If c(abc) K, d ∈ K. If c(abc, bcd) K, ad ∈ K. Lemma 12 Let ∆ = v 1 v 2 v 3 v 4 and triangles t i ∈ ∂∆ such that v i / ∈ t i . Let H i and H i be the two half-spaces of t i such that ∆ ⊂ H i . We have H 1 ∩H 2 ∩H 3 ∩H 4 = ∅. If c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 , v 1 c ∩ t 1 = ∅. Let v = (v 1 + v 2 )/2. If c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 , vc ∩ (t 1 ∪ t 2 ) = ∅ (Fig.
t 1 = v 2 v 3 v 4 , t 2 = v 3 v 4 v 1 , t 3 = v 4 v 1 v 2 and t 4 = v 1 v 2 v 3 . Left: v = v 1 and c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 .
∂∆ = {t 1 , t 2 , t 3 , t 4 } and ∂∆ ∩ ∂O = {t 1 , • • • , t n }. Thanks to Theorem 8, n ≥ 1. Let K = c(∂∆) ∩ c(∂O). We show that K = c(t 1 , • • • , t n ) where 1 ≤ n ≤ 3 and conclude using The- orem 3. Note that c(t 1 , • • • , t n ) = c(∂∆ ∩ ∂O) ⊆ K.
Let H i and H i be the two half-spaces of Third we show that n = 3 implies

t i such that ∆ ⊂ H i . First we show that i ≤ n implies c ∈ H i and i > n implies c ∈ H i . If i ≤ n, there is a tetrahedron ∆ i ∈ O such that t i = ∆ ∩ ∆ i and ∆ i ⊂ H i . Since O is c-star-shaped, c and ∆ i are in the same t i half-space (Theorem 7), i.e. c ∈ H i . If i > n, t i ∈ ∂∆\∂O. Thanks to Lemma 2, t i ∈ ∂(O ∪ {∆}). Since ∂(O ∪ {∆}) is c- star-
K = c(t 1 , t 2 , t 3 ). We have c(t 1 , t 2 , t 3 ) ⊆ K ⊆ c(∂∆) = c(t 1 , t 2 , t 3 ) ∪ {t 4 }. If c(t 1 , t 2 , t 3 ) K (reductio ad absurdum), K = c(∂∆), i.e. n = 4 (impossible).
Fourth we show that n = 1 implies

K = c(t 1 ). Thus c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 . Let v 1 be the ∆ vertex that is not in t 1 , i.e. v 1 = t 2 ∩ t 3 ∩ t 4 . Thanks to Lemma 12, there is a point w ∈ t 1 ∩ cv 1 . Assume (reductio ad absurdum) that c(t 1 ) K. According to Lemma 11, v 1 ∈ K ⊆ c(O). Since O is c-star-shaped, cv 1 ⊂ |O|. We obtain wv 1 ⊆ ∆ ∩ |O|. Since ∆ / ∈ O, Lemma 5 implies ∆ ∩ |O| = ∅. Therefore wv 1 ⊂ |∂∆|.
There is a triangle t i ∈ ∂∆ that includes at least two distinct points in wv 1 . Since c ∈ (wv 1 ), c is in the t i plane: we are in a degenerate case (contradiction).

Last we show that n = 2 implies

K = c(t 1 , t 2 ). Thus c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 .
Let v be the center of the edge t 3 ∩ t 4 . Thanks to Lemma 12, there is a point w ∈ (t 1 ∪t 2 )∩cv. Assume (reductio ad absurdum) that c(t 1 , t 2 ) K. According to Lemma 11,

t 3 ∩ t 4 ∈ K ⊆ c(O) and v ∈ |O|. Since O is c-star-shaped, cv ⊂ |O|.
Therefore wv ⊆ ∆ ∩ |O|. Last we show that c is in a t i plane as in the previous case n = 1 (contradiction). Now we obtain the result of Sec. 5.

Corollary 3 Let c be a point in |T | that is not in a plane including a triangle of c(T ). Let O ⊆ T such that O is non-empty c-star-shaped. Then ∂O is a 2- manifold. Let O ⊆ T such that O O and O is c- star-shaped. Then there is a shelling O 0 • • • O n such that O 0 = O, O n = O and every O i ⊆ T is c-star-shaped.
Proof First we assume that both Õ and O i are c-starshaped such that ∅ = O i Õ ⊆ T and ∂O i is a 2manifold. We show that there is a tetrahedron ∆ i ∈ Õ \ O i such that ∂∆ i ∩ ∂O i = ∅ and, using notation

O i+1 = O i ∪ {∆ i }, O i+1 is c-star-shaped and ∂O i+1 is a 2-manifold. Theorem 8 provides the tetrahedron ∆ i . Let O i+1 = O i ∪ {∆ i }. Now O i+1 is c-star-shaped (Lemma 10) and c(∂∆ i ) ∩ c(∂O i ) is a 2-ball (Theo- rem 9). Thus c(∆ i ) ∩ c(O i
) is non-empty 2D-pure (Theorem 3) and ∂O i+1 is a 2-manifold (Theorem 1). Second we show that ∂O is a 2-manifold. Let ∆ be a tetrahedron such that c ∈ ∆ ∈ T . Let O 0 = {∆ }. Note that O 0 is c-star-shaped (∆ is convex) and ∂O 0 is a 2-manifold (∂O 0 is a 2-sphere). By successive use(s) of the first step (above) with Õ = O, we find a series

O 0 • • • O n in T such that O n = O and every ∂O i is a 2-manifold.
Third we show that there is a shelling

O 0 • • • O n such that O 0 = O, O n = O
• • • O n in T such that O n = O and every O i is c-star-shaped. This series is a shelling since O i+1 = O i ∪ {∆ i } and c(∆ i ) ∩ c(O i ) is non-empty 2D-
pure for all i < n, and ∂O 0 is a non-empty 2-manifold.

According to Appendix C, there are non-shellable starshapes in degenerate cases.

A qualitative argument for surface reconstruction

Here we provide a qualitative argument (this is not a proof as in the paper remainder) to explain that the first shelling in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF], i.e. Algorithm 1 started from O = ∅, does not have excessive blocking and provides most of the tetrahedra enclosed by the final surface. Sec. 3.1 gives a reminder of this algorithm and useful notations F and n ∆ .

The set F looks like a star-shape: for every point x reconstructed from a camera location c, cx ⊂ ∪F (F is not exactly a star-shape since x is restricted to the vertices in c(T ) and there are several c). Assuming that c follows a curve and the distance between x and c is small compared to the curve length, F can be seen as a tubular neighborhood of the curve.

Furthermore, O also looks like a star-shape during the first shelling in [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF]. Since both ∆ size and cx density increase when we go toward the curve, n ∆ increases when we go toward the curve. Since this shelling tries to add first to O the tetrahedra ∆ having the highest n ∆ , O essentially grows in a front-to-back order relatively to the curve. As a consequence, the points in ∪F with a small distance to the curve enter in ∪O during the shelling before those with a greater distance, i.e. there is a c in the curve such that cx ⊂ ∪O if x ∈ ∪O.

Now O is growing in F by the shelling such that both O and F looks like star-shapes with the same curve as "center". Then Corollary 3 suggests that O fills F , if we replace the point center by the curve center.

Let O/F be the ratio of the number of the tetrahedra in O generated by the first shelling alone and the number of the tetrahedra in F . Let O/O e be the ratio of the number of the tetrahedra in O generated by the first shelling alone and the final number of the tetrahedra generated by all operators (including the first shelling). In Tab. 2 of [START_REF] Lhuillier | Manifold surface reconstruction of an environment from sparse structure-from-motion data[END_REF], O/F = 87% and O/O e = 94%.

Shelling blocking

In this section, we provide a family of 3-balls that are strongly non-shellable with small numbers of simplices (Sec. 6.5). We also provide other cases of blocking (Sec. 6.6) for a shelling started from a general O 0 ⊆ T . All these cases of shelling blocking are generated by disjoint unions of tetrahedron sets in T that are called "pipe" (Sec. 6.1) and "slice" (Sec. 6.3). Both are 3-balls and their "gluing" (union of such a 3-ball with another tetrahedron set in T ∞ ) are described in Secs. 6.2 and 6.4.

Basic component: pipe

If triangles a 0 b 0 c 0 and a 1 b 1 c 1 have distinct vertices, the tetrahedron set

P = p(a 0 b 0 c 0 , a 1 b 1 c 1 ) is {a 0 a 1 b 1 c 0 , a 0 a 1 b 0 c 0 , a 1 b 0 b 1 c 0 , a 0 a 1 b 1 c 1 , a 0 b 1 c 0 c 1 }. ( 14
)
We assume that P ⊆ T , show P in Fig. 12, and see that a 0 a 1 b 1 c 0 is an internal tetrahedron of P . Indeed, every triangle face of a 0 a 1 b 1 c 0 is join to b 0 or c 1 by another tetrahedron in P :

P = {a 0 a 1 b 1 c 0 } ∪ b 0 × {a 0 a 1 c 0 , a 1 b 1 c 0 } ∪ c 1 × {a 0 a 1 b 1 , a 0 b 1 c 0 }. ( 15
)
Fig. 12 The pipe p(a 0 b 0 c 0 , a 1 b 1 c 1 ) (right) and its decomposition (left). See the internal tetrahedron a 0 a 1 b 1 c 0 .

Lemma 13

We have

∂P = {a 0 b 0 c 0 , a 1 b 1 c 1 } ∪ {a 0 a 1 b 0 , a 1 b 0 b 1 }∪ {b 0 b 1 c 0 , b 1 c 0 c 1 } ∪ {a 0 c 0 c 1 , a 0 a 1 c 1 }. ( 16
)
Proof Eq. 15 implies that the triangles in c(P ), that have neither b 0 nor c 1 as vertex, are faces of the internal tetrahedron a 0 a 1 b 1 c 0 . Since ∂P ⊂ c(P ), every triangle in ∂P has vertex b 0 or c 1 , i.e.

∂P ⊆ b 0 × a 0 -a 1 -c 0 -a 0 ∪ b 0 × a 1 -b 1 -c 0 -a 1 ∪ c 1 × a 0 -a 1 -b 1 -a 0 ∪ c 1 × a 0 -b 1 -c 0 -a 0 . (17)
Since a triangle in ∂P is in a single tetrahedron of P ,

∂P = b 0 × c 0 -a 0 -a 1 ∪ b 0 × a 1 -b 1 -c 0 ∪ c 1 × a 0 -a 1 -b 1 ∪ c 1 × b 1 -c 0 -a 0 = b 0 × c 0 -a 0 -a 1 -b 1 -c 0 ∪ c 1 × a 0 -a 1 -b 1 -c 0 -a 0 (18)
and we obtain the result.

We say that P is a pipe. Intuitively, the two cross sections of the pipe are triangles a 0 b 0 c 0 and a 1 b 1 c 1 . The lateral section of the pipe is a strip of 6 triangles (in Eq. 16) having edges a 0 a 1 , b 0 b 1 , c 0 c 1 and three others. A pipe series p(a

0 b 0 c 0 , a 1 b 1 c 1 ), p(a 1 b 1 c 1 , a 2 b 2 c 2 ), p(a 2 b 2 c 2 , a 3 b 3 c 3 ),
• • • will be used to form a longer "pipe" and build strongly non-shellable 3-balls.

Lemma 14 If p(a 0 b 0 c 0 , a 1 b 1 c 1 ) ⊆ T , P is a 3-ball.
The proof ot this lemma is in the supplementary material (use a shelling, or see that ∂P is an octahedron).

Gluing a pipe

The goal of Sec. 6.2 is Theorem 11: we define an union of a pipe P and another tetrahedron set A ⊆ T ∞ such that the criterion of the strongly non-shellability (Sec. 4.1) applied to A∪P is meet for every tetrahedron in P . The proof of this theorem (and others) needs the following gluing lemma and theorem. Proof Let1 t ∈ c(T ∞ ) and C = T ∞ \(A∪B). Let ∆ and ∆ be the two tetrahedra in This theorem means that volumes A and B can be glued properly, i.e. by maintaining the 2-manifold property of their boundaries, if their intersection is well behaved (Fig. 13). The proof is technical and is in Appendix D.

Lemma 15 If A ⊆ T ∞ and B ⊆ T ∞ and A ∩ B = ∅, ∂(A ∪ B) = (∂A \ ∂B) ∪ (∂B \ ∂A).
T ∞ such that t = ∆ ∩ ∆ . We show that t ∈ ∂(A ∪ B) iff t ∈ (∂A \ ∂B) ∪ (∂B \ ∂A) in all cases. If (∆, ∆ ) ∈ A × A, the triangle t is neither in ∂A \ ∂B nor in ∂(A ∪ B). Since A ∩ B = ∅, we also have t / ∈ ∂B \ ∂A. The case (∆, ∆ ) ∈ B × B is similar. If (∆, ∆ ) ∈ C × C, t is neither in ∂(A ∪ B) nor in (∂A\∂B)∪(∂B \∂A). If (∆, ∆ ) ∈ A×B, t / ∈ ∂(A∪B). Since A ∩ B = ∅, t ∈ ∂A ∩ ∂B and thus t / ∈ (∂A \ ∂B) ∪ (∂B \ ∂A). If (∆, ∆ ) ∈ A × C, t ∈ ∂A \ ∂B and t ∈ ∂(A ∪ B). The case (∆, ∆ ) ∈ B × C is similar.
Theorem 11 Let A ⊆ T ∞ such that ∂A is a 2-manifold. Let P = p(a 0 b 0 c 0 , a 1 b 1 c 1 ) such that P ⊆ T \ A and c(A) ∩ c(P ) = c(a 0 b 0 c 0 , a 1 b 1 c 1 , b 0 b 1 c 0 , b 1 c 0 c 1 ). (19) Then ∂(A ∪ P ) is a 2-manifold. If a tetrahedron ∆ ∈ P , c(∂(A ∪ P )) ∩ c(∆)
is not a 2-ball (Fig. 14).

Proof Since the triangles in c(A) ∩ c(P ) form a hexagon a 0 b 0 b 1 a 1 c 1 c 0 , c(A)∩c(P ) is homeomorphic to a 2-ball. Then Lemma 14 and Theorem 10 imply that ∂(A ∪ P ) is a 2-manifold.

We will show that c(∂(A ∪ P )) ∩ c(∆) has zero or one triangle and includes four vertices if ∆ ∈ P . This implies that c(∂(A ∪ P )) ∩ c(∆) is not 2D pure, which in turn implies that c(∂(A ∪ P )) ∩ c(∆) is not a 2-ball thanks to Theorem 3.

Since [START_REF] Litvinov | Incremental solid modeling from sparse structure-from-motion data with improved visual artifacts removal[END_REF]. Therefore

∂A ∩ ∂P = {a 0 b 0 c 0 , a 1 b 1 c 1 , b 0 b 1 c 0 , b 1 c 0 c 1 }, ∂P \ ∂A = {a 0 a 1 b 0 , a 1 b 0 b 1 , a 0 c 0 c 1 , a 0 a 1 c 1 } (Eq.
{a 0 , a 1 , b 0 , b 1 , c 0 , c 1 } ⊂ c(∂P \ ∂A) (20)
and

∆ = a 0 a 1 b 1 c 0 ⇒ ∂∆ ∩ (∂P \ ∂A) = ∅ ∆ = a 0 a 1 b 0 c 0 ⇒ ∂∆ ∩ (∂P \ ∂A) = {a 0 a 1 b 0 } ∆ = a 1 b 0 b 1 c 0 ⇒ ∂∆ ∩ (∂P \ ∂A) = {a 1 b 0 b 1 } ∆ = a 0 a 1 b 1 c 1 ⇒ ∂∆ ∩ (∂P \ ∂A) = {a 0 a 1 c 1 } ∆ = a 0 b 1 c 0 c 1 ⇒ ∂∆ ∩ (∂P \ ∂A) = {a 0 c 0 c 1 }. (21)
Since ∆ ∈ P has its four vertices in {a 0 , a 1 , b 0 , b 1 , c 0 , c 1 } and thanks to Eq. 20, c(∂P \ ∂A) ∩ c(∆) includes four vertices. Furthermore, Eq. 21 implies that (∂P \ ∂A) ∩ (∂∆) has zero or one triangle for every ∆ ∈ P . Assume (reductio ad absurdum) that there is a triangle t ∈ (∂A \ ∂P ) ∩ ∂∆. Thus t ⊆ ∆ ∈ P and t ⊆ ∆ ∈ A. Since A ∩ P = ∅ (Eq. [START_REF] Sakai | Simplicial homology, a short course[END_REF], we have ∆ / ∈ P and obtain t ∈ ∂P , which contradicts t ∈ ∂A \ ∂P .

Thanks to Lemma 15, (∂P \∂A)∪(∂A\∂P ) = ∂(A∪ P ). Therefore c(∂(A ∪ P )) includes the four vertices of ∆ and has zero or one triangle of ∆.

* = b 0 -b 1 -• • • b n-1 -b 0 and c * = c 0 -c 1 -• • • c n-1 -c 0 . Let N = 0≤i<n N i where N i = {b i b i+1 c i , b i+1 c i c i+1 } or N i = {c i+1 b i b i+1 , c i c i+1 b i }. ( 22
)
The set N is a strip of triangles that form an annulus and we have ∂N = b * ∪ c * . We say that S ⊆ T is a slice if S is a 3-ball such that N ⊆ ∂S (see Fig. 15). Slice properties are in the following theorem:

Gluing a slice

Similarly as in Sec. 6.2, the goal of Sec. 6.4 is Corollary 4: we define an union of a slice S and another tetrahedron set A ⊆ T ∞ such that the criterion of the strongly non-shellability applied to A∪S is meet for every tetrahedron in S . Here S is computed by "shrinking" an initial slice S: we progressively remove every tetrahedron ∆ from S that does not meet this criterion. The proof needs Theorem 13, which guarantees that S is a slice (a 3-ball with the same annulus as S). This theorem needs the following lemma.

Lemma 16 Let A ⊆ T ∞ such that ∂A is a 2-manifold. Let S ⊂ T \ A
= {b i c i , b i+1 c i+1 , b i+1 c i , b i b i+1 c i , b i+1 c i c i+1 } or Ñi = {b i c i , b i+1 c i+1 , b i c i+1 , c i+1 b i b i+1 , c i c i+1 b i }. ( 24
) If σ ∈ c(b * ) ∪ c(c * ), σ ∈ c(B) ∪ c(C).
Otherwise σ ∈ Ñ . This implies that there is an edge b i c i or b i+1 c i or c i+1 b i in c(∂(A∪S))∩c(N ). Let e be this edge. There are distinct triangles t 1 and

t 2 in N = ∂S∩∂A such that e = t 1 ∩ t 2 . Since e ∈ c(∂(A ∪ S)) = c((∂A ∪ ∂S) \ N ), there is another triangle t 3 ∈ (∂A ∪ ∂S) \ N such that e ⊂ t 3 . If t 3 ∈ ∂A, e is in 3 distinct triangles in ∂A. This is impossible since ∂A is a 2-manifold. If t 3 ∈ ∂S, e is in 3 distinct triangles in ∂S. This is impossible since ∂S is a 2-manifold. Theorem 13 Let A ⊆ T ∞ such that ∂A is a 2-manifold. Let S ⊂ T \ A be a 3-ball such that c(A) ∩ c(S) = c(N ) and N is an annulus. Let ∆ be a tetrahedron in S such that c(∂(A ∪ S)) ∩ c(∆) is a 2-ball. Then S \ {∆} is a 3-ball and c(A) ∩ c(S \ {∆}) = c(N ).
Proof Let B and C be as in Lemma 16.

Let X = c(∆)∩ c(B) and Y = c(∆) ∩ c(C). First we show that X = ∅ (or similarly, Y = ∅). Since ∆ ∈ S, c(∆) ∩ c(∂(A ∪ S)) = c(∆) ∩ (c(∂(A ∪ S)) ∩ c(S)) = X ∪ Y. ( 25
)
Assume (reductio ad absurdum) that X = ∅ and Y = ∅. Since c(B)∩c(C) = ∅, X ∩Y = ∅ and c(∆)∩c(∂(A∪S)) is not connected. This contradicts that c(∆ Proof Let S = S. We consider the following loopalgorithm: while there is a tetrahedron

) ∩ c(∂(A ∪ S)) is a 2-ball. Second we show that c(∆) ∩ c(N ) ⊆ c(∆) ∩ c(c * ). Since c(∆)∩c(b * ) ⊆ X = ∅, ∆ does not have a vertex in c(b * ). Since every vertex in c(∆) ∩ c(N ) is a b i or a c i , every vertex in c(∆) ∩ c(N ) is a c i . Thus c(∆) ∩ c(N ) ⊆ c(c * ). We obtain c(∆) ∩ c(N ) ⊆ c(∆) ∩ c(c * ). Third we show that S \ {∆} is a 3-ball. Since ∂S = B ∪ C ∪ N and c(∆) ∩ c(N ) ⊆ c(∆) ∩ c(c * ) ⊆ c(∆) ∩ c(C) = Y , c(∆) ∩ c(∂S) = X ∪ Y ∪ (c(∆) ∩ c(N )) = Y = c(∆) ∩ c(∂(A ∪ S)). (26
∆ ∈ S such that c(∆) ∩ c(∂(A ∪ S )) is a 2-ball, remove ∆ from S .
Thanks to Theorem 13, S is always a 3-ball and we always have c(A) ∩ c(S ) = c(N ). The algorithm stops since S is finite, and it stops if c(∆) ∩ c(∂(A ∪ S )) is not a 2-ball for every tetrahedron ∆ ∈ S .

Family of strongly non-shellable 3-balls

First we need a specialization of Theorem 10 (proof in Appendix F):

Theorem 14 Let A ⊆ T ∞ and B ⊆ T \A such that ∂A is a connected 2-manifold, ∂B is a 2-sphere, c(A)∩c(B) is a 2-ball. Then ∂(A ∪ B) is homeomorphic to ∂A.
Then Theorem 15 presents a family of strongly nonshellable 3-balls.

Theorem 15

Let P i = p(a i b i c i , a i+1 b i+1 c i+1 ) or P i = p(a i+1 b i+1 c i+1 , a i b i c i ) such that P i ⊆ T if 0 ≤ i < n.
Let S ⊆ T \ ∪ i P i be a 3-ball such that c(∪ i P i ) ∩ c(S) = c(N ) and N is an annulus using notations in Eq. 22 (top of Fig. 16). Then there is a 3-ball S ⊆ S such that c(∪ i P i ) ∩ c(S ) = c(N ) and ∪ i P i ∪ S is a strongly non-shellable 3-ball (bottom of Fig. 16).

Intuitively (Fig. 16), ∂(∪ i P i ) is a torus whose intersection with ∂S (and also ∂S ) is the annulus N . Furthermore, ∂(∪ i P i ∪ S ) is a 2-sphere, with both "sides" separated by the cycle a * (B is in one side and C is in the other). If a tetrahedron ∆ having a triangle in one side is removed from ∪ i P i ∪ S , a singular vertex appears in both sides. We use Theorem 11 if ∆ ∈ P i and Corollary 4 if ∆ ∈ S to show that c(∆)∩c(∂(∪ i P i ∪S )) is not a 2-ball, i.e. to show that ∪ i P i ∪ S is a strongly non-shellable 3-ball.

Proof First we find S . Every ∂P i is a 2-manifold and every c(∂

(∪ i-1 k=0 P k ))∩c(∂P i ) is a 2-manifold with bound- ary ({a i b i c i } if i < n -1, {a n-1 b n-1 c n-1 , a 0 b 0 c 0 } if i = n -1)
. Thus successive uses of Theorem 10 imply that ∂(∪ n-1 i=0 P i ) is a 2-manifold. Now we use Corollary 4 using A = ∪ i P i and obtain a 3-ball S ⊆ S such that c(A) ∩ c(S ) = c(N ) and c(∆) ∩ c(∂(A ∪ S )) is not a 2-ball for every tetrahedron ∆ ∈ S . Second we show that A i = ∪ j =i P j ∪ S and O = ∪ j P j ∪ S are 3-balls. By successive uses of Theorem 14 (as in the previous case above), ∂(∪ j =i P j ) is a 2-manifold that is homeomorphic to a 2-sphere. Then Theorem 14 implies that ∂A i is a 2-sphere (use A = ∪ j =i P j and B = S ). Now Theorem 14 implies that ∂O is a 2-sphere (use A = A i and B = P i ). Since A i ⊆ T and O ⊆ T , Theorem 5 implies that A i and O are 3-balls.

Last we show that O is strongly non-shellable. We already know that c(∆) ∩ c(∂O) is not a 2-ball for every tetrahedron ∆ ∈ S . We use Theorem 11 using A = A i and P = P i and see that c(∆) ∩ c(∂O) is not a 2-ball for every tetrahedron ∆ ∈ P i .

Appendix G shows that there is a strongly non-shellable 3-ball as described in Theorem 15: the strongly nonshellable 3-ball Z with 12 vertices and 25 tetrahedra in Sec. 4 of [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF] (Z is the symmetric version of the 3-ball with 10 vertices and 21 tetrahedra).

∆ ∈ T \ O 0 and c(O 0 ) ∩ c(∆) = c(∂O) ∩ c(∂∆) = c(∂∆) is non-empty 2D-pure. Thus (O 0 , O 1 ) is a shelling. Since O 1 = T ∞ \ (O \ {∆}) and O has at least two tetrahe- dra, O 1 = T ∞ . Since ∂O 0 is a 2-sphere and O 1 = T ∞ , Corollary 2 implies that c(O 0 ) ∩ c(∆) = c(∂∆) is a 2- ball (impossible). Theorem 16 Let M ⊆ T ∞ such that ∂M is a 2-manifold. Let S ⊆ T \ M be a 3-ball such that c(M ) ∩ c(S) = c(N \ {b 0 b 1 c 0 , b 1 c 0 c 1 })
ing notation O = T ∞ \ (M ∪ P ∪ S ), ∂O is a 2- manifold, c(O) ∩ c(∆) is not 2D-pure for every tetrahe- dron ∆ ∈ P ∪ S such that ∂∆ ∩ ∂O = ∅.
Two examples of M , S and P are shown in Fig. 17. The first one (on the top) is inspired by the real example in Fig. 1 of [START_REF] Litvinov | Incremental solid modeling from sparse structure-from-motion data with improved visual artifacts removal[END_REF] such that M is "the matter" (set of the tetrahedra non-intersected by rays and including the ground and walls of a city), P , S and P ∪ S are 3-balls that cannot be carved by a shelling although they are in the free-space (set of the tetrahedra intersected by rays). The second one (on the bottom) is similar and is inspired by the real example in Fig. 3.4 of [START_REF] Gezahegne | Surface reconstruction with constrained sculpting[END_REF].

Proof First we find S . Let A = M ∪ P . Since c(M ) ∩ c(P ) is two disjoint 2-balls and both ∂M and ∂P are 2-manifolds and P ⊂ T \ M , Theorem 10 implies that ∂A is a 2-manifold. Furthermore, c(A)∩c(S) = (c(M )∩ c(S)) ∪ (c(P ) ∩ c(S)) = c(N ). Thus Corollary 4 implies that there is a 3-ball S ⊆ S such that c(A) ∩ c(S ) = c(N ) and c(∆) ∩ c(∂(A ∪ S )) is not a 2-ball for every tetrahedron ∆ ∈ S .

Second we show that ∂O is a 2-manifold. Since both ∂A and ∂S are 2-manifold and c(A) ∩ c(S ) is a 2manifold with boundary (the annulus N ), Theorem 10 implies that ∂(A ∪ S ) is a 2-manifold. Therefore ∂O = ∂(M ∪ P ∪ S ) is a 2-manifold.

Third we show that ∆ ∈ P ∪ S implies that c(∆) ∩ c(∂O) is not a 2-sphere. If ∆ ∈ S and since S is a 3-ball with more that one tetrahedron, there is another tetrahedron ∆ ∈ S such that ∆ ∩ ∆ is a triangle (Lemma 17). We have a similar case if ∆ ∈ P . In all cases, ∆ has a triangle face t between two tetrahedra in M ∪ P ∪ S . Since t / ∈ ∂O, c(∆) ∩ c(∂O) = c(∂∆). According to Theorem 3 and since ∆ / ∈ O, c(∆)∩c(∂O) is not 2D-pure or is a 2-ball, but it is not a 2-sphere.

Last we conclude. We use Theorem 11 using A = M ∪ S and see that c(∆) ∩ c(∂O) is not a 2-ball for every tetrahedron ∆ ∈ P . Now c(∆) ∩ c(∂O) is not a 2-ball for every tetrahedron

∆ ∈ P ∪ S . Since c(∆) ∩ c(∂O) is neither 2-ball nor 2-sphere, c(∆)∩c(∂O) is not non-empty 2D-pure (Theorem 3). Since ∂∆ ∩ ∂O = ∅, c(∆) ∩ c(∂O) is not 2D pure.

Conclusion

This article overviews shelling properties for the surface reconstruction application. In this context, a shelling is a series of tetrahedron sets O 0 • • • O n in a 3D Delaunay triangulation T , generated by a greedy algorithm that adds one tetrahedron to every O i , such that all boundaries ∂O i have the same topology in almost all cases.

If O 0 includes only one tetrahedron, all O i are 3balls and Combinatorial Topology works study the shellability of a 3-ball O: is there a shelling such that O n = O ? Several cases are possible for greedy shelling algorithms that try to generate O: always success (O is extendably shellable), sometimes success (O is shellable but non-extendably shellable), and always failure (O is non-shellable). Furthermore, there are 3 invariant numbers (the h-numbers) for all shellings of O.

We also show that there is a shelling started from O 0 and ended to O, if O 0 ⊂ O ⊆ T and both O 0 and O are star-shaped with respect to a same point. This generalizes a known result of shellability (if O = T and O 0 has a single tetrahedron) and we use this property to qualitatively explain why the greedy algorithm does not have excessive failures and provides most of the tetrahedra enclosed by the final surface.

Last we provide a family of non-shellable 3-balls and examples of visual artifacts that a shelling alone cannot remove. Such visual artifacts occur in previous surface reconstruction results and are due to an incomplete growing of O in the free-space. Actually non-shelling algorithms remove some of them, but future work is needed to remove all of them.

A Proofs for prerequisites of star-shape shelling

A.1 Proof of Lemma 6

First we show that there are points x ∈ ∆x and y

∈ cx \ |A|. Since |A| is a closed set in R 3 , there is > 0 such that B(y, ) ∩ |A| = ∅. Let τ ∈ R be such that x -c = τ (y -c).
We have τ > 1 since y is between x and c. If Last we find x and ỹ. Since ∆x and ∆y are open, we define B x = B(x , τ ) and B y = B(y , ) such that B x ⊂ ∆x and B y ⊂ ∆y . Let V be the union for every edge e ∈ c(T ) of the plane(s) that include(s) both e and c. Since we are in a non degenerate case, e and c are not collinear. Thus V is a finite union of planes and we cannot have B x ⊆ V . There is x ∈ B x \ V ⊆ ∆x . This implies that cx does not intersect the edges in c(T ) and ỹ = c + (x -c)/τ ∈ B y ⊆ ∆y .

A.2 Proof of Lemma 7

First we show that the set of the triangles t i ∈ c(T ) intersected by (xy) are such that x λ i = (xy) ∩ t i and the λ i are distinct. If x λ is in a triangle t λ ∈ c(T ), t λ ∩ (cx) is a line segment x λ 0 x λ 1 (indeed the intersection of two closed convexes is a closed convex). Furthermore, λ 0 = λ 1 (otherwise, (xy) is in the plane of t λ and intersects an edge of t λ ) and we obtain x λ = (xy) ∩ t λ . Let λ i ∈ R such that x λ i ∈ t i . Now we show that λ i = λ j implies i = j. Since (xy) does not intersect the edges of t i , x λ i ∈ ti . Thus t i = t j (Lemma 5), i.e. i = j.

Second we note that there are at least two triangles t i , i.e. k ≥ 1. Indeed, x ∈ ∆x and ∆ x ∈ T imply that (xy) intersects at least two triangles in ∂∆ x ⊂ c(T ).

Third the λ i are ordered such that λ i < λ i+1 and we show that there is a tetrahedron

∆ i ∈ T such that t i ∈ ∂∆ i , t i+1 ∈ ∂∆ i and x λ ∈ ∆ i iff λ ∈ [λ i , λ i+1 ]. Let m i = x (λ i +λ i+1 )/2 . Since |T | is convex, there is a tetrahedron ∆ i ∈ T such that m i ∈ ∆ i . Since m i is not in a triangle of c(T ), m i ∈ ∆i . Therefore ∆ i ∩ (xy) is a line segment x λ 0 x λ 1 such that λ 0 = λ 1 . This implies that x λ ∈ ∆ i iff λ ∈ [λ 0 , λ 1 ]. Furthermore x λ ∈ |∂∆ i | (indeed x λ /
∈ ∆i which is open). Thus there are distinct triangles t j and t l in ∂∆ i such that x λ 0 ∈ t j and x λ 1 ∈ t l and λ 0 = λ j and λ 1 = λ l . Since λ j < λ < λ l implies x λ ∈ ∆i , which in turn implies x λ / ∈ t m (Lemma 5), we have j + 1 = l. Since m i ∈ x λ j x λ j+1 , we have j = i. Thus t i ∈ ∂∆ i , t i+1 ∈ ∂∆ i , λ 0 = λ i and λ 1 = λ i+1 .

Last we assume that a tetrahedron ∆ ∈ T meets (xy) ∩ ∆ = ∅ and show that ∆ is a ∆ i . The proof is similar as in the third step above. We have (xy) ∩ ∆ = x λ0 x λ1 such that λ0 ≤ λ1 and x λ is in a triangle t ∈ ∂∆. Since (xy) does not intersect the ∆ edges, (xy) intersects t , which in turn implies that λ0 = λ1 . Now there are distinct triangles t j and t l such that t0 = t j , t1 = t l , λ0 = λ j and λ1 = λ l . Since λ0 < λ < λ1 implies x λ ∈ ∆, which in turn implies x λ / ∈ t m (Lemma 5), we have l = j + 1.

A.3 Proof of Theorem 7

Let O ⊆ T be c-star-shaped, a triangle t ∈ ∂O, a tetrahedron ∆ ∈ O such that t ∈ ∂∆, and show that ∆ and c are in the same t half-space. If t ∈ ∂T , both ∆ and c are in the convex set T (indeed T is Delaunay) and thus there are in the same half-space of t. If t / ∈ ∂T , there is a tetrahedron

∆ ∈ T \ O such that t = ∆ ∩ ∆ . Let b be the barycentre of t. Since c is not in the t plane, ∆ ∩ bc = ∅ or ∆ ∩ bc = ∅. Assume (reductio ad absurdum) that ∆ ∩ bc = ∅. Since O is c-star-shaped, bc ⊆ |O|. Therefore there is ∆ ∈ O such that ∆ ∩ ∆ = ∅. Lemma 5 implies that ∆ = ∆ ∈ O, which contradicts ∆ ∈ T \ O.
Assume that O ⊆ T is not c-star-shaped and show that there is a tetrahedron ∆ ∈ O and a triangle t ∈ ∂O ∩ ∂∆ such that ∆ and c are not in the same t half-space. Since O is not c-star-shaped, there is a point x ∈ |O| \ {c} such that cx is not included in |O|. Thus there is a point y ∈ cx \ |O|. Now we use Lemma 6 with A = O. Let ∆ x ∈ O be a tetrahedron such that x ∈ ∆ x . Thus there are tetrahedron ∆ y ∈ T \ O and points x ∈ ∆x and y ∈ ∆y ∩ cx such that (cx) does not intersect the edges in c(T ). Then we obtain a tetrahedron series ∆ i covering xy as described by Lemma 7. There are j and m such that ∆ j = ∆ x ∈ O and ∆ m = ∆ y ∈ T \ O. Since x 0 = x ∈ ∆ j and x 1 = y ∈ ∆ m , j ≤ m and λ m ≤ 1. Therefore there is l such that j ≤ l < m, ∆ l ∈ O, ∆ l+1 ∈ T \ O and λ l+1 ≤ λ m . Let ∆ = ∆ l and the triangle t = ∆ l ∩ ∆ l+1 . Note that x λ ∈ ∆ iff λ ∈ [λ l , λ l+1 ], x λ ∈ t iff λ = λ l+1 , λ l+1 ≤ 1, c = x µ with µ > 1 (x 1 is between x 0 and c). Thus ∆ and c are in different half-spaces of t.

B Proofs for star-shape shelling

B.1 Proof of Lemma 12

We change the coordinate basis such that v that v 1 ∈ H1 and v 2 ∈ H2 . Note that ∆ 2 is like ∆ except that the vertex v 1 is replaced by ṽ1 and the half-space H 2 is replaced by H2 : ∆ 2 = H 1 ∩ H2 ∩ H 3 ∩ H 4 (t 1 does not change, the half-spaces H 3 and H 4 does not change since their boundary planes include ṽ1 , v 1 and v 2 that are collinear). Assume c ∈ H2 (the other case c ∈ H1 is similar). We have c ∈ H 1 ∩ H2 ∩ H 3 ∩ H 4 (indeed, c ∈ H 1 ∩ H 3 ∩ H 4 and c ∈ H2 ). According to the second assertion of the lemma applied to ∆ 2 , cṽ 1 ∩ t 1 = ∅. Thus cv ∩ (t 1 ∪ t 2 ) = ∅.

T 1 = 0 0 0 , v T 2 = 1 0 0 , v T 3 = 0 1 0 , v T 4 = 0 0 1 . Thus H 1 = {(x 2 , x 3 , x 4 ) T ∈ R 3 , x 2 + x 3 + x 4 ≥ 1} H 2 = {(x 2 , x 3 , x 4 ) T ∈ R 3 , x 2 ≤ 0} H 3 = {(x 2 , x 3 , x 4 ) T ∈ R 3 , x 3 ≤ 0} H 4 = {(x 2 , x 3 , x 4 ) T ∈ R 3 , x 4 ≤ 0}. ( 29
) Now we see that (x 2 , x 3 , x 4 ) ∈ H 1 ∩H 2 ∩H 3 ∩H 4 is impossible. Assume that c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 . We have v 1 ∈ H 2 ∩ H 3 ∩H 4 (indeed ∆ = H 1 ∩H 2 ∩H 3 ∩H 4 ). Since H 2 ∩H 3 ∩H 4 is convex and includes both c and v 1 , cv 1 ⊂ H 2 ∩ H 3 ∩ H 4 . Let plane π 1 = H 1 ∩H 1 . Thus cv 1 ∩π 1 ⊆ H 1 ∩H 2 ∩H 3 ∩H 4 ∩H 1 = ∆ ∩ π 1 = t 1 . We obtain cv 1 ∩ π 1 ⊆ cv 1 ∩ t 1 . Since c and v 1 are in different t 1 half-spaces, cv 1 ∩ π 1 = ∅ and we obtain cv 1 ∩ t 1 = ∅. Assume that c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 . The tetrahedron ∆ = v 1 v 2 v 3 v 4 is split in two tetrahedra ∆ 1 = v 1 ṽ2 v 3 v 4 and ∆ 2 = ṽ1 v 2 v 3 v 4 using ṽ2 = ṽ1 = v = (v 1 + v 2 )/

C Non-shellable star-shapes in degenerate cases

Here we show that there are star-shapes O that are non shellable in degenerate cases. More precisely, we find h-starshapes O such that ∂O has a singular vertex and h is in a plane of a triangle in ∂O. Since ∂O is a 2-manifold if O is shellable (Theorem 4), we see that such an O is non-shellable.

For example, O = {habc, hdef } is a h-star-shape such that ∂O has a singular vertex h. Proof This is Lemma 1 in [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF] by replacing the set B by a single tetrahedron. The proof is very similar as the proof in Appendix A.1 of [START_REF] Lhuillier | 2-manifold tests for 3D Delaunay triangulation-based surface reconstruction[END_REF].

We show that every vertex

v ∈ c(∂(A ∪ B)) meets (∂(A ∪ B)) v = v × x * where x * is a cycle. Thanks to Lemma 15, ∂(A ∪ B) = (∂A \ ∂B) ∪ (∂B \ ∂A). Thus v ∈ c(∂A) or v ∈ c(∂B). We also have (∂(A ∪ B)) v = ((∂A) v \ (∂B) v ) ∪ ((∂B) v \ (∂A) v ). ( 32
)
There are three cases.

If v ∈ c(∂A) \ c(∂B), (∂B) v = ∅. Thanks to Eq. 32, (∂(A ∪ B)) v = (∂A) v . Since ∂A is a 2- manifold, there is a cycle x * such that (∂(A∪B)) v = (∂A) v = v × x * . The proof is the same if v ∈ c(∂B) \ c(∂A). Now we consider the last case v ∈ c(∂A) ∩ c(∂B). Since ∂A is a 2-manifold, ∃a i ∈ c(∂A), (∂A) v = v × a * , a * = a 1 -• • • a m -a 1 , (33)
and a * is a cycle. Since ∂B is a 2-manifold,

∃b i ∈ c(∂B), (∂B) v = v × b * , b * = b 1 -• • • b n -b 1 , (34)
c i ∈ c(∂A) ∩ c(∂B) such that (∂A ∩ ∂B) v = v × c * , c * = c 1 -• • • c k , (35)
i = c i if 1 ≤ i ≤ k. Similarly k ≤ n and b i = c i if 1 ≤ i ≤ k. Thanks to Eq. 32, (∂(A ∪ B)) v = v × x * where x * = a k -• • • a m -a 1 ∪ b k -• • • b n -b 1 . (36)
Since

a 1 = b 1 = c 1 and a k = b k = c k , x * = c k -a k+1 -a k+2 -• • • a m -c 1 -b n -b n-1 -• • • b k+1 -c k . (37)
Then we show that c(x * ) has at least 3 distinct vertices. It has c k and c 1 . Furthermore, c 1 = c k since k ≥ 2. Assume (reduction ad absurdum) that it has no other vertex. Thus m = k = n. This implies (∂A) v = (∂B) v , which is impossible (see above).

Last we show that the vertices in the vertex sequence x * are distinct. We have c 1 = c k since k ≥ 2. We also have

c 1 = a i if i > k, since c 1 = a 1 and the a i are distinct (indeed, a * is a cycle). Similarly, c 1 = b i if i > k, c k = a i and c k = b i if i > k. Assume (reductio ad absurdum) that a i = b j if i > k and j > k. Thus va i ∈ c(∂A) ∩ c(∂B). Since c(∂A) ∩ c(∂B) is 2D pure 2 (indeed, c(∂A) ∩ c(∂B)
is a 2-manifold with boundary), there is a triangle t ∈ (∂A∩∂B) v such that a i ∈ t. This implies that a i = a j with i > k and j ≤ k (impossible). Proof Since the 3-ball L ⊆ T , ∂L is a 2-sphere (Theorem 5). Let m ∈ |∂L| that is neither a vertex nor in an edge of c(∂L). Let ϕ be a homeomorphism such that ϕ(|∂L| \ {m}) = R 2 .

Let G = (V, E) be the graph of the vertices and edges in c(∂L). Let G * = (V * , E * ) be the adjacency graph of the triangles in ∂L, i.e. V * = {v(t), t ∈ ∂L} and E * = {e(t 1 , t 2 ), t i ∈ ∂L, t 1 ∩ t 2 is an edge }. Both G and G * have drawings (mappings) in R 2 by ϕ. The drawing of G is (ϕ(V ), ϕ(E)). The drawing of v(t) ∈ V * is the drawing of the barycentre of t ∈ ∂L. The drawing of e(t 1 , t 2 ) ∈ E * is the drawing of a polygonal curve linking the barycentres of adjacent triangles t 1 and t 2 (the polygonal curve is included in t 1 ∪ t 2 and intersects the edge t 1 ∩ t 2 ). Let F = b * and F * be the dual edges of F , i.e. F * = {e(t 1 , t 2 ) ∈ E * , t 1 ∩ t 2 ∈ F }. Thanks to Proposition 4.6.1 in [START_REF] Diestel | Graph theory[END_REF] (the plane duality theorem) and since G is connected and the drawings of G and G * are dual and F is a cycle, F * is a minimal cut of G * .

Word "cut" means that the graph (V * , E * \F * ) is disconnected. Word "minimal" means that (V * , E * \ F * ) becomes connected if we remove any edge from F * . If we don't remove an edge from F * , (V * , E * \ F * ) has exactly two connected components {v(t), t ∈ B 1 } and {v(t), t ∈ B 2 }: B 1 ∪ B 2 = ∂L, B 1 ∩ B 2 = ∅, and every B i is non-empty strongly connected using the edges in E * \ F * .

Let edge e ∈ ∂B i and show e ∈ b * . Since ∂L is a 2manifold and the B i partition ∂L, there are triangles t i ∈ B i such that e = t 1 ∩ t 2 . If e(t 1 , t 2 ) ∈ E * \ F * , v(t 1 ) and v(t 2 ) are in the same connected component of (V * , E * \ F * ) (impossible). Thus e(t 1 , t 2 ) ∈ F * and e ∈ F = b * .

Let edge e ∈ b * and show e ∈ ∂B i . We have distinct triangles t i ∈ ∂L such that e = t 1 ∩ t 2 . Since F = b * , e(t 1 , t 2 ) ∈ F * . If t 1 ∈ B 1 and t 2 ∈ B 1 (reductio ad absurdum), we remove the edge e(t 1 , t 2 ) from F * and add it to E * \ F * without connecting B 1 and B 2 , i.e. F is not a minimal cut (impossible). Thus t 1 ∈ B 1 and t 2 ∈ B 2 ; we obtain e ∈ ∂B i .

Since

∂B i = b * , c(b * ) ⊆ c(B 1 ) ∩ c(B 2 ). Now we show c(B 1 ) ∩ c(B 2 ) ⊆ c(b * ). Since B 1 ∩ B 2 = ∅, there are not triangles in c(B 1 ) ∩ c(B 2 ). Let edge e ∈ c(B 1 ) ∩ c(B 2
); e is included in a triangle in B 1 and another in B 2 and thus e ∈ b * . Let vertex v ∈ c(B 1 )∩c(B 2 ). Since ∂L is a 2-manifold, there is a triangle series t i ∈ (∂L) v such that every t i ∩ t i+1 is an edge. There is a t j ∈ B 1 and t k ∈ B 2 . Therefore there is i such that t i ∈ B 1 and t i+1 ∈ B 2 . We see that the edge e = t i ∩ t i+1 meets e ∈ c(B 1 ) ∩ c(B 2 ). Since e ∈ b * (see above), v ∈ c(b * ). Now we do the proof of Theorem 12.

First we introduce notations by applying Theorem 17 to cycles b * and c * . There are

B i such that B 1 ∪ B 2 = ∂L, ∂B 1 = ∂B 2 = b * , c(B 1 ) ∩ c(B 2 ) = c(b * ) and every B i is strongly connected. There are C i such that C 1 ∪ C 2 = ∂L, ∂C 1 = ∂C 2 = c * , c(C 1 ) ∩ c(C 2 ) = c(c * ) and every C i is strongly connected.
Second we show that N ⊆ B 2 (similarly, N ⊆ C 2 ). Assume (reductio ad absurdum) that there are triangles t 1 ∈ N ∩ B 1 and t 2 ∈ N ∩ B 2 . Since N is strongly connected and N ⊆ B 1 ∪ B 2 , we can choose t 1 and t 2 such that t 1 ∩ t 2 is an edge. Therefore t 1 ∩ t 2 ∈ ∂B i = b * . However, an edge between two distinct triangles in N is b i c i or b i+1 c i or c i+1 b i (contradiction). We obtain N ⊆ B 2 .

Third we show that c(N

) ∩ c(B 1 ) = c(b * ) (similarly, c(N ) ∩ c(C 1 ) = c(c * )). Since c(b * ) ⊆ c(B 1 ) and c(b * ) ⊆ c(N ) ⊆ c(B 2 ) and c(B 1 ) ∩ c(B 2 ) = c(b * ), we have c(b * ) ⊆ c(N ) ∩ c(B 1 ) ⊆ c(B 1 ) ∩ c(B 2 ) ⊆ c(b * ). ( 38
) Thus c(N ) ∩ c(B 1 ) = c(b * ). Fourth we show that B 1 ∩ C 1 = ∅. Since ∂B 1 = b * , there is a triangle t = db 0 b 1 ∈ B 1 . Assume (reductio ad absurdum) that t ∈ C 1 . Thus b 0 ∈ c(C 1 ). Since b 0 ∈ c(N ), we have b 0 ∈ c(C 1 ) ∩ c(N ) = c(c * ), i.
e. b 0 is equal to a c j (impossible). We see that every triangle t = db 0 b 1 ∈ B 1 \C 1 . Assume (reductio ad absurdum) that there is a triangle t ∈ C 1 ∩ B 1 . Since B 1 is strongly connected and t ∈ B 1 \ C 1 and t ∈ B 1 ∩ C 1 , we can find triangles t ∈ B 1 \ C 1 and t ∈ B 1 ∩ C 1 such that t ∩ t is an edge. Therefore t ∩ t ∈ ∂C 1 = c * ⊆ ∂N . This implies that t ∈ N or t ∈ N , which is impossible since

B 1 ∩ N ⊆ B 1 ∩ B 2 = ∅.
Fifth we show that

N ∪ C 1 = B 2 . Since B 1 ∩ C 1 = ∅ and C 1 ⊆ B 1 ∪ B 2 , C 1 ⊆ B 2 .
Thus N ∪ C 1 ⊆ B 2 and we only need to show that t ∈ B 2 implies t ∈ N ∪ C 1 . Since B 2 is strongly connected and ∅ = N ∪ C 1 ⊆ B 2 , there is a triangle series t i ∈ B 2 such that t 0 ∈ N ∪ C 1 and t n = t and every t i ∩ t i+1 is an edge that is not in ∂B

F Proof of Theorem 14

We show that ∂(A∪B) is a connected 2-manifold that has the same genus as ∂A (therefore they are homeomorphic). The principle of the proof is the following. Theorem 10 implies that ∂(A ∪ B) is a 2-manifold. The set D = ∂A ∩ ∂B is a 2ball 3 . Then we show that ∂(A ∪ B) is connected by studying the connectivity of ∂A\D and ∂B \D and since their closures include the 1-sphere ∂D. Last we use properties of Euler's characteristic χ(X) of X ⊆ c(T ) to show that both ∂(A ∪ B) and ∂A have the same genus. We remind that χ(X) is the number of the vertices plus number of the triangles minus the number of the edges in X, thus it is closely related to the genus of X (Sec. 2.6).

We start by the two following lemmas, which are useful to show that ∂A \ D and ∂B \ D are connected. Assume that σ is an edge (case 1). Thus σ = t 1 ∩ t 2 . Since D ⊆ M and M is a 2-manifold, the only triangles in M that includes σ are t 1 and t 2 . Therefore there is only one triangle in D that includes σ and we obtain σ ∈ c(∂D). Assume that σ is a vertex (case 2). Since M is a 2-manifold, M v is a triangle series t i ∈ M such that every t i ∩t i+1 is an edge including v5 . There is j and k such that t j = t 1 ∈ D and t k = t 2 ∈ M \ D. Thus we can find i such that t i ∈ D and t i+1 ∈ M \ D (or vice versa). Now vertex σ is a face of the edge e = t i ∩ t i+1 such that e ∈ c(M \ D) ∩ c(D) and we just showed (case 1) that e ∈ c(∂D). Therefore σ ∈ c(∂D). Table 1 3D coordinates of the 12 vertices in V . Fig. 19 Top views of the three subsets of Z. Left: the top subset is the union of the tetrahedra cycles Z 2.10 and Z 4.12 . Middle: the center subset has five internal tetrahedra. Right: the bottom subset is the union of the tetrahedra cycles Z 1.9 and Z 3.11 . Note that vertices are sometimes duplicated.

Using Eq. 51 and a 0 ∈ {5, 7} and a 1 ∈ {6, 8}, σ is included is 11 Thus Z = P ∪S with n = 4 and P = ∪ i P i 13 as in Theorem 15.

Since Z is strongly non-shellable [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF], Z = P ∪S and S = S .

H Addendum

-Title "2-Manifold criterion for sets of triangles" is better than "2-Manifold criterion for simplicial complexes" for Sec. 2.5, since X in Sec. 2.5 is a set of triangles (X is not a simplicial complex). -We need a basic Lemma two times in the paper: Lemma 24 If a simplicial complex X ⊂ c(T ) is a 2manifold with boundary, X is 2D pure.

Intuitively, if X is not 2D pure, there is a point in |X| that has no 2D neighborhood in |X|. A proof is in Sec. H.1.

-Lemma 24 is used at the very end of Appendix D using X = c(∂A) ∩ c(∂B). -Lemma 24 is used at the very beginning of Appendix F using X = c(A) ∩ c(B). Since this X is a 2-ball, X meets the Lemma's assumptions and |X| is the union of the triangles in X. Since the set of these triangles is D = ∂A ∩ ∂B, we see that D is a 2-ball.

H.1 Proof of Lemma 24

Assume (reductio ad absurdum) that X is not 2D pure. Thus there is a vertex that is not in an edge (both in X), or there is an edge that is not in a triangle (both in X). Since X is a 2-manifold with boundary, the vertex point is homeomorphic to R 2 or R × R + in the first case (impossible). In the second case, we consider the middle point m of the edge and one of its small neighborhood N in |X| that is included in the edge such that N is homeomorphic to R 2 or R × R + . Now we see that N \ {m} is homeomorphic to R 2 minus a point or homeomorphic to R × R + minus a point. This is impossible since the former is disconnected and the latters are connected.

Fig. 1 A

 1 Fig.1A shelling example in the 2D case: O is a growing set of triangles such that ∂O is a cycle (drawn with bold edges).

Fig. 2

 2 Fig. 2 Lemma 1 in the 2D case. Left: c(∆) and c(∂∆). Middle: c(O) and c(∂O). Right: c(∆) ∩ c(O). Both ∆ and O are in gray, T is the set of all triangles, ∆ ∈ T \ O, the edges of c(∂∆) and c(∂O) are thickened, the vertices of c(∆) and c(O) are black squares. We see that c(∆) ∩ c(O) has 1 edge and 3 vertices, c(∆) ∩ c(O) = c(∂∆) ∩ c(∂O), ∂O ∩ ∂∆ has 1 edge.

Fig. 3

 3 Fig. 3 Triangle splitting for Lemma 3 in cases f = 1 (left), f = 2 (middle) and f = 3 (right). There are ∂O ∩ ∂∆ on the top and ∂∆ \ ∂O on the bottom (ϕ maps the former to the latter).

  Thus ad ∈ c(O) ∩ c(∆) although triangles adb and adc are not in c(O)∩c(∆), i.e. c(O)∩c(∆) is not 2D pure (impossible). Therefore both t and ϕ |t are unchanged if f = 2. Assume (reductio ad absurdum) that f = 3 and d ∈ t. Thus {t} ∪ d × a-b-c-a ⊆ (∂O) d and t / ∈ d × a-b-c-a, i.e. d is a singular vertex of ∂O (impossible). Therefore both t and ϕ |t are unchanged if f = 3. Third we show that ϕ is surjective. Thanks to Lemma 2 and since ϕ(|∂O∩∂∆|) = |∂∆\∂O| and ϕ is the identity

Fig. 4

 4 Fig. 4 Theorem 4 in the 2D case (O is gray). Left: O encloses a cavity defined by two white triangles. Middle: add a triangle to O such that c(O) ∩ c(∆) is a ball. Right: add a triangle to O such that c(O) ∩ c(∆) is a sphere. The number of the connected component(s) of ∂O is two (left and middle) or one (right).

5

  Star-shape shelling In Sec. 5, there are tetrahedron sets O, O and a point c ∈ |O| such that O O ⊆ T and both O and O are cstar-shaped. We show that there is a shelling

Fig. 5

 5 Fig.5A star-shape shelling example in the 2D case: O is a growing set of triangles such that ∂O is a cycle (bold edges) and O is always star-shaped with respect to the black dot.

Fig. 6

 6 Fig. 6 Lemma 6 in the 2D case. Left: A is enclosed by the bold edges, c ∈ |A|, x ∈ ∆ x ∈ A, ∆ x is grey, (cx) intersects a vertex of c(T ) (an edge in 3D), y ∈ cx \ |A|. Right: replace x by x ∈ ∆x such that (cx) does not intersect the c(T ) vertices, replace y by ỹ ∈ ∆y ∩ cx such that ∆ y ∈ T \ A, ∆ y is grey.

Fig. 7

 7 Fig. 7 Lemma 7 in the 2D case. Left: (xy) successively intersects ∆ 1 • • • ∆ 6 in T , every ∆ i ∩∆ i+1 is an edge (a triangle in 3D). Right: x λ maps [λ i , λ i+1 ] in ∆ i .

Fig. 8

 8 Fig. 8 Theorem 7 in the 2D case (tetrahedra are drawn as triangles). The streaked triangle is ∆ and the bold edge is t. If O is c-star-shaped (left), ∆ and c are in the same t halfspace. If O is not c-star-shaped (right), there is x ∈ |O| such that we have not xc ⊂ |O|. Thus there are ∆ and t such that ∆ and c are not in the same t half-space.

Lemma 8

 8 Assume that O is c-star-shaped and ∆ ∈ O \ O has a triangle face t /

  t / ∈ ∂O and ∆ / ∈ O, ∆ ∈ T \ O and thus ∆ ∈ T \ A. Since c and ∆ are in different half-spaces of t, there is a point y ∈ cx ∩ ∆ . Since y cannot be in a tetrahedron of A (Lemma 5), y / ∈ |A|. Second we find a tetrahedron series covering xc (x ∈ ∆) using Lemma 7. According to Lemma 6, there are a tetrahedron ∆ y ∈ T \ A and points x ∈ ∆x and y ∈ ∆y ∩ cx such that (cx) does not intersect the edges in c(T ). Now we have a tetrahedron series ∆ i ∈ T that covers |T |∩(xy) as defined by Lemma 7. Since xc ⊆ |T | (indeed |T | is convex and include both x and c) and (xc) = (xy), the tetrahedron series also covers xc. Third we find distinct ∆ i that include x, y and c. There are j, n and l such that ∆ j = ∆ x , ∆ n = ∆ y and c ∈ ∆ l ∈ O (since c ∈ |O|). Since y ∈ xc and x = x 0 and y = x 1 , we have j ≤ n ≤ l. Since ∆ j ∈ A and ∆ n / ∈ A and ∆ l ∈ A, we have j < n < l. Fourth we show that j ≤ m ≤ l implies ∆ m ∈ O . Since O is c-star-shaped and both x and c are in |O |,

Fig. 9 Fig. 10

 910 Fig. 9 Notations for Lemma 8 in the 2D case (tetrahedra are drawn as triangles). The two streaked triangles are ∆ and ∆ , the triangle with dotted edges is in O. Here ∆ is behind ∆ .

Lemma 10

 10 If O is c-star-shaped and ∆ is defined by Theorem 8, O ∪ {∆} is also c-star-shaped.Proof According to Theorem 7 applied to O, every triangle t ∈ ∂O\∂∆ is a face of a tetrahedron ∆ ∈ O such that ∆ and c are in the same t half-space. Theorem 8 implies that every triangle t ∈ ∂∆ \ ∂O is such that ∆ and c are the same t half-space. Thanks to Lemma 2, every triangle t ∈ ∂(O ∪ {∆}) is a face of a tetrahedron ∆ ∈ O ∪ {∆} such that ∆ and c are in the same t half-space. Last we apply Theorem 7 to O ∪ {∆} and see that O ∪ {∆} is c-star-shaped.The proofs of the two following technical lemmas are in the supplementary material and Appendix B.

Theorem 9

 9 If O is c-star-shaped and ∆ is defined by Theorem 8, c(∂∆) ∩ c(∂O) is a 2-ball.

Fig.

  Fig.11The point vc ∩ t 1 according to Lemma 12. We havet 1 = v 2 v 3 v 4 , t 2 = v 3 v 4 v 1 , t 3 = v 4 v 1 v 2 and t 4 = v 1 v 2 v 3 . Left: v = v 1 and c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 .The half-spaces H 1 , H 2 , H 3 and H 4 are below t 1 , t 2 , t 3 and t 4 respectively. Right: v = (v 1 + v 2 )/2 and c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 . The half-spaces H 1 , H 2 , H 3 and H 4 are below t 1 , t 2 , t 3 and t 4 respectively.

  shaped (Lemma 10), c and ∆ are in the same t i half-space (Theorem 7), i.e. c ∈ H i .Second we show that n = 4. If n = 4 (reductio ad absurdum), c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 , which is impossible thanks to Lemma 12.

  and every O i is c-star-shaped. We set O 0 = O. Note that O 0 is c-star-shaped and ∂O 0 is a 2-manifold. By successive use(s) of the first step (above) with Õ = O , we find a series O 0

Fig. 13

 13 Fig. 13 Gluing A ⊂ T (left) and B ⊂ T (middle) using Theorem 10. Both ∂A and ∂B are 2-manifolds, A∩B = ∅ and ∂A ∩ ∂B is the union of two 2-balls. Right: the result A ∪ B. If c(A) ∩ c(B) is a 2-manifold with boundary, ∂(A ∪ B) is a 2-manifold (top). If c(A) ∩ c(B) is 2D pure and non-manifold, ∂(A ∪ B) can have a singular vertex (bottom).

Theorem 10

 10 Let A ⊆ T ∞ and B ⊆ T \ A such that both ∂A and ∂B are 2-manifolds, and c(A)∩c(B) is a 2manifold with boundary. Then ∂(A∪B) is a 2-manifold.

Fig. 14

 14 Fig. 14 Assumptions of Theorem 11: P (left), A (middle) and A ∪ P (right).

6. 3

 3 Basic component: slice Let integer n ≥ 3 and vertices b 0 , • • • b n and c 0 , • • • c n in c(T ) that are distinct, with exceptions b n = b 0 and c n = c 0 . We have cycles b

Fig. 15

 15 Fig. 15 Annulus (left) and slice (right) using n = 6.

be a 3 -

 3 ball such that c(A) ∩ c(S) = c(N ) and N is an annulus. Then there are B and C as in Theorem 12 such that c(∂(A ∪ S)) ∩ c(S) = c(B) ∪ c(C). Proof Since c(A) ∩ c(S) = c(N ) and A ∩ S = ∅, every triangle in N is in a tetrahedron in A and another in S. Thus S is a slice with the annulus N ⊂ ∂S. Let B and C as in Theorem 12. Now N = ∂A ∩ ∂S and Lemma 15 imply ∂(A∪S) = (∂A\N )∪(∂S \N ). We use shortened notation S = c(S). Since ∂(A∪S) = (∂A\N )∪(∂S \N ) and ∂S \ N = B ∪ C and B ⊂ S and C ⊂ S, c(∂(A ∪ S)) ∩ S = (c(∂A \ N ) ∩ S) ∪ (c(∂S \ N ) ∩ S) = (c(∂A \ N ) ∩ S) ∪ c(B) ∪ c(C). (23) Let σ be a simplex in c(∂A \ N ) ∩ S and show that σ ∈ c(B)∪c(C). Since c(∂A\N )∩ S ⊆ c(A)∩ S = c(N ), we have σ ∈ c(N ). We have c(N ) = c(b * ) ∪ c(c * ) ∪ Ñ using Ñ = ∪ i Ñi where Ñi

)Corollary 4

 4 Therefore c(∆) ∩ c(∂S) is a 2-ball. Since S is a 3-ball, we see that S \ {∆} is a 3-ball (use Corollary 2 for the shelling O 0 = T ∞ \ S, O 1 = O 0 ∪ {∆} and Theorem 5).Last we show that c(A) ∩ c(S) = c(A) ∩ c(S \ {∆}). We havec(A) ∩ c(S) = (c(A) ∩ c(S \ {∆})) ∪ (c(A) ∩ c(∆)).(27) Since ∆ ∈ S and c(N ) = c(A) ∩ c(S), c(A) ∩ c(∆) = c(N ) ∩ c(∆) ⊆ c(∆) ∩ c(c * ). (28)Let σ be a simplex in c(A) ∩ c(∆). Thanks to Eq. 28, σ is a vertex or an edge. Since c(N ) = c(A) ∩ c(S) and thanks to Eq. 27, σ is in a triangle t ∈ N . Since c(A) ∩ c(∆) does not have a triangle, t ∈ c(A) ∩ c(S \ {∆}).Thus c(A) ∩ c(∆) ⊆ c(A) ∩ c(S \ {∆}). Let A ⊆ T ∞ such that ∂A is a 2-manifold.Let S ⊂ T \ A be a 3-ball such that c(A) ∩ c(S) = c(N ) and N is an annulus. There is a 3-ball S ⊆ S such that c(A) ∩ c(S ) = c(N ) and c(∆) ∩ c(∂(A ∪ S )) is not a 2-ball for every tetrahedron ∆ ∈ S .

Fig. 16

 16 Fig. 16 Illustrations for Theorem 15. Top: S (right) and ∪ i P i ∪ S (left). The pipes P i form a torus; we have c(∪ i P i ) ∩ c(S) = c(N ) where N is the annulus whose boundary is b * ∪ c * . Bottom: cross section by a plane including grey triangles a 0 b 0 c 0 and a 3 b 3 c 3 . The white triangles are tetrahedra in S (left), S is obtained by removing some of these tetrahedra such that c(∪ i P i ) ∩ c(S ) = c(N ) (middle), a singular vertex appears if we remove a tetrahedron from S (right).

6. 6

 6 Other shelling blocking After a lemma, Theorem 16 provides examples of residual 3-balls in the free-space that cannot be carved by a shelling during the surface reconstruction. Lemma 17 If a 3-ball O ⊆ T has at least two tetrahedra and ∆ ∈ O, there is a tetrahedron ∆ ∈ O \ {∆} such that ∆ ∩ ∆ is a triangle. Proof Assume (reductio ad absurdum) that ∂∆ ⊆ ∂O. Let O 0 = T ∞ \ O and O 1 = O 0 ∪ {∆}. We have

Fig. 17

 17 Fig. 17Two examples for Theorem 16: M includes a horizontal ground and a vertical wall (top) or includes two pillars on the ground (bottom). Left: ∂M including triangles a 0 b 0 c 0 and a 1 b 1 c 1 . Middle: ∂M and S. Right: ∂M and S and P .

  Fig. 17Two examples for Theorem 16: M includes a horizontal ground and a vertical wall (top) or includes two pillars on the ground (bottom). Left: ∂M including triangles a 0 b 0 c 0 and a 1 b 1 c 1 . Middle: ∂M and S. Right: ∂M and S and P .

  and N is an annulus (Eq. 22). Let P = p(a 0 b 0 c 0 , a 1 b 1 c 1 ) such that P ⊆ T \ (M ∪ S) and c(M )∩c(P ) = c(a 0 b 0 c 0 , a 1 b 1 c 1 ) and c(S)∩c(P ) = c(b 0 b 1 c 0 , b 1 c 0 c 1 ). Then there is a 3-ball S ⊆ S such that c(M ∪ P ) ∩ c(S ) = c(M ∪ P ) ∩ c(S) and, us-

  x ∈ |∂∆ x |, there is a point x very close to x such that x ∈ ∆x and y = c + (x -c)/τ ∈ B(y, ). If x / ∈ |∂∆ x |, we set x = x and y = y. Second we show that there are tetrahedron ∆ y ∈ T \ A and x ∈ ∆x such that y = c + (x -c)/τ ∈ ∆y . Since |T | is convex and includes {c, x }, y ∈ |T |. Since y / ∈ |A|, there is a tetrahedron ∆ y ∈ T \A such that y ∈ ∆ y . If y ∈ |∂∆ y |, there is a point y very close to y such that y ∈ ∆y and x = c + τ (y -c) ∈ ∆x .

Fig. 18 A

 18 Fig. 18 A non-shellable star-shape O with respect to h such that h / ∈ |∂O| (right): O is the union of ab × d-e-f -g-d (left) and {bcef , bcgd} (middle).

Property 2

 2 Fig. 18 shows another example O that is star-shaped with respect to a point h / ∈ |∂O|: O = S 1 ∪ {bcef , bcgd} where S 1 = ab × d-e-f -g-d. (30) Note that h is in the plane of the triangle bcg ∈ ∂O and b is a singular vertex of ∂O. Now we show that O can be star-shaped. Let S 2 = bc × d-e-f -g-d and h ∈ |S 1 | ∩ (bc). If both S 1 and S 1 ∪ S 2 are convex, O is h-star-shaped. Proof Let x ∈ |O| and show that xh ⊆ |O|. We have x ∈ |S 1 | or x ∈ bcef (or similarly x ∈ bcgd). Since S 1 is convex and h ∈ |S 1 |, x ∈ |S 1 | implies xh ⊆ |S 1 | ⊆ |O|. Now we assume x ∈ bcef and show xh ∩ bcde = xh ∩ bce. Since h ∈ (bc) and x ∈ bcef , hx and bcef are in the same half-space of bce. Since bcde is in the other half-space of bce, hx ∩ bcde is included in the plane of bce. We obtain xh ∩ bcde = xh ∩ bce and similarly xh ∩ bcfg = xh ∩ bcf . Since S 1 ∪S 2 is convex and h ∈ |S 1 ∪S 2 |, xh ⊆ |S 1 ∪S 2 | = |O ∪ {bcde, bcfg}|. Thus xh = xh ∩ |O ∪ {bcde, bcfg}| = xh ∩ (|O| ∪ bce ∪ bcf ). (31) Since bce ⊆ |O| and bcf ⊆ |O|, we obtain xh ⊆ |O|. D Proof of Theorem 10 Lemma 18 Assume that A ⊆ T ∞ and B ⊆ T \ A. Then c(A)∩c(B) is a simplicial complex in R 3 . Furthermore, c(A)∩ c(B) = c(∂A) ∩ c(∂B).

  and b * is a cycle. Since c(∂A)∩c(∂B) = c(A)∩c(B) (Lemma 18) and c(A) ∩ c(B) is a 2-manifold with boundary, there are

  and there are two cases: c * is a cycle and k ≥ 3, or all c i are distinct and k ≥ 2. Since (∂A ∩ ∂B) v ⊆ (∂A) v and (∂A ∩ ∂B) v ⊆ (∂B) v , we have c * ⊆ a * and c * ⊆ b * . Assume (reductio ad absurdum) that c * is a cycle. Since c * is included in a * and b * that are also cycles, a * = c * = b * . This implies (∂A) v = (∂B) v . Thanks to Eq. 32, (∂(A ∪ B)) v = ∅. This contradicts v ∈ c(∂(A ∪ B)).Now the c i are distinct and k ≥ 2. Since the c i are distinct and c * ⊆ a * , k ≤ m. We shift the a i such that a

2

  Addendum: use Lemma 24 in Appendix H.E Proof of Theorem 12First Theorem 17 details the splitting of a 2-sphere in c(T ) by a cycle. Then we show Theorem 12 (splitting of ∂S by the annulus N ) by applying Theorem 17 to every cycle in ∂N .Theorem 17 Let L ⊆ T be a 3-ball and b * ∈ c(∂L) be a cycle. There areB i such that B 1 ∪ B 2 = ∂L, ∂B 1 = ∂B 2 = b * , c(B 1 ) ∩ c(B 2 ) = c(b * ), every B i is strongly connected.Intuitively, the closed curve b * splits the 2-sphere ∂L in two disjoint and connected sets (2-balls) of triangles B 1 and B 2 that have the common boundary b * . This is a discrete version of the Jordan Theorem for a 2-sphere encoded by a simplicial complex.

2 .

 2 Since N ∩ C 1 = ∅, ∂(N ∪ C 1 ) = (∂N \ ∂C 1 ) ∪ (∂C 1 \ ∂N ) = ((b * ∪ c * ) \ c * ) ∪ (c * \ (b * ∪ c * )) = b * = ∂B 2 . (39)Therefore every t i ∩ t i+1 is not in ∂(N ∪ C 1 ). Now we havet i+1 ∈ N ∪ C 1 if t i ∈ N ∪ C 1 . Since t 0 ∈ N ∪ C 1 , we obtain t = t n ∈ N ∪ C 1 .Last we show c(B 1 ) ∩ c(C 1 ) = ∅ and conclude using B = B 1 andC = C 1 . Since C 1 ⊆ B 2 (see above), c(B 1 ) ∩ c(C 1 ) ⊆ c(B 1 ) ∩ c(B 2 ) = c(b * ). Furthermore B 1 ⊆ C 2 (indeed, B 1 ∩ C 1 = ∅ and B 1 ⊆ C 1 ∪ C 2 imply B 1 ⊆ C 2 ). Thus c(B 1 ) ∩ c(C 1 ) ⊆ c(C 2 ) ∩ c(C 1 ) = c(c * ). We obtain c(B 1 ) ∩ c(C 1 ) ⊆ c(b * ) ∩ c(c * ) = ∅.

3

  Addendum: more details in Appendix H. Lemma 19 Let M ⊆ c(T ) be a 2-manifold 4 . Let D ⊂ M . Then ∂(M \ D) = ∂D and c(M \ D) ∩ c(D) = c(∂D). Proof First we show ∂D = ∂(M \ D). Let e ∈ c(M ) be an edge. Since M is a 2-manifold, there are exactly two triangles t 1 and t 2 in M that includes e and e = t 1 ∩ t 2 . Since D ⊆ M , e ∈ ∂D iff t 1 ∈ D and t 2 ∈ M \ D iff e ∈ ∂(M \ D). If a simplex σ ∈ c(∂D), σ ∈ c(D) and σ ∈ c(∂(M \ D)) ⊆ c(M \ D). Therefore σ ∈ c(M \ D) ∩ c(D). Conversely, let σ ∈ c(M \ D) ∩ c(D) and show σ ∈ c(∂D). This means that there are triangles t 1 ∈ D and t 2 ∈ M \ D such that σ ⊆ t 1 ∩ t 2 .

Lemma 20

 20 Assume that M ⊆ c(T ∞ ) is a connected 2manifold6 . If a 2-ball D ⊆ M , M \ D is connected.Proof Let vertices v and v in c(M \ D). Since they are in c(M ) and M is connected, there is a pathv 0 -v 1 -• • • v n ⊆ c(M ) such that v 0 = v and v n = v .If this path has an edge which is not in c(M \ D), we modify it to obtain another path such that all its edges are in c(M \ D) (thus M \ D is connected).Let j be the smallest index i such thatv i v i+1 / ∈ c(M \D). We show that v j ∈ c(∂D). Since v j v j+1 ∈ c(M ) = c(M \ D) ∪ c(D), v j v j+1 ∈ c(D). If j = 0, we have v j ∈ c(M \ D) ∩ c(D) = c(∂D) (Lemma 19). If j > 0, v j-1 v j ∈ c(M \ D) and we have v j ∈ c(M \ D) ∩ c(D) = c(∂D).Let k be the greatest index i such thatv i v i+1 / ∈ c(M \D). Similarly, v k+1 ∈ c(∂D).Since D is a 2-ball, ∂D is a cycle of edges d i d i+1 . There are integers l and m such that the pathd l -d l+1 -• • • d m ⊂ ∂D meets d l = v j and d m = v k+1 . Thanks to Lemma 19, every edge d i d i+1 ∈ c(M \ D). Last we concatenate v 0 -• • • v j and d l -• • • d m and v k+1 -• • • v n to obtain a path v 0 -• • • v n ⊆ c(M \ D) such that v 0 = v and v n = v .Now we show Theorem 14.First we show that∂(A ∪ B) is a connected 2-manifold. Thanks to Theorem 10, ∂(A∪B) is a 2-manifold. Furthermore ∂A \ D is connected and ∂B \ D is connected (Lemma 20) and ∅ = c(∂D) ⊆ c(∂A \ D) ∩ c(∂B \ D) (thanks to Lemma 19). Thus ∂(A ∪ B) = (∂A \ D) ∪ (∂B \ D) is connected. Second we show that c(D)∩c(∂(A∪B)) = c(∂D). Lemma 19 using M ∈ {∂A, ∂B} implies c(D) ∩ c(∂A \ D) = c(∂D) = c(D) ∩ c(∂B \ D). Therefore c(D) ∩ (c(∂A \ D) ∪ c(∂B \ D)) = c(∂D).(40)We obtain the result using Lemma 15. Third we show that χ(c(∂(A ∪ B))) = χ(c(∂A)). Thanks to Lemma 15, D ∪ ∂(A ∪ B) = ∂A ∪ ∂B. Since χ(X ∪ Y ) = χ(X) + χ(Y ) -χ(X ∩ Y ), χ(c(D)) + χ(c(∂(A ∪ B))) -χ(c(D) ∩ c(∂(A ∪ B)))

  one of the triangles in Ñ where Ñ = {9.2.1, 2.1.10} ∪ {11.2.3, 2.3.10} ∪ {9.4.1, 4.1.12} ∪ {11.4.3, 4.3.12}. (57) Therefore c(S) ∩ c(P ) ⊆ c( Ñ ). Conversely 12 , Ñ ⊆ c(P ) and Ñ ⊆ c(S) implies c( Ñ ) ⊆ c(S) ∩ c(P ). Last we check that N = Ñ .

  The half-spaces H 1 , H 2 , H 3 and H 4 are below t 1 , t 2 , t 3 and t 4 respectively. Right: v = (v 1 + v 2 )/2 and c ∈ H 1 ∩ H 2 ∩ H 3 ∩ H 4 . The half-spaces H 1 , H 2 , H 3 and H 4 are below t 1 , t 2 , t 3 and t 4 respectively.

Addendum: t is a triangle.

Addendum: we also assume that M is a set of triangles.

Addendum: v is a redundant notation of σ.

Addendum: we also assume that M is a set of triangles.

= χ(c(∂A)) + χ(c(∂B)) -χ(c(∂A) ∩ c(∂B)).

(41)

Furthermore 7 , χ is known for 2-balls, cycles and 2-spheres:

Thus

Now we see that ∂A and ∂(A ∪ B) have the same genus.

G An example for Theorem 15

First we remind how Z is constructed in [START_REF] Ziegler | M: Shelling polyhedral 3-balls and 4-polytopes[END_REF] using shortened notations: a vertex is an integer between 1 and 12, the tetrahedron with vertices {1, 2, 3, 4} is written 1.2.3.4, the edge with vertices {1, 2} is written 1.2, 1.2 × 3-4-5-6 is the tetrahedron set {1.2.3.4, 1.2.4.5, 1.2.5.6} etc. Let V be the set of the vertices 1, 2 • • • 12. The 3D coordinates of the vertices in V are given in Tab. 1. Then Z is defined as the disjoint union of three subsets of tetrahedra (Fig. 19). The center subset is

The top subset is the union of the tetrahedron cycles Z 2.10 and Z 4.12 :

The bottom subset is the union of the tetrahedron cycles Z 1.9 and Z 3.11 :

We obtain

Second we check that Z is included in a set of tetrahedra T such that c(T ) is a 3D Delaunay triangulation.

where d is the Euclidean distance between two 3D points.

We have e = 0.5 > 0. Thus, for every ∆ ∈ Z, there is no V \ c(∆) vertex in the (interior of the) sphere that includes the four ∆ vertices. Therefore Z is included in a 3D Delaunay triangulation of V .

Third we show that Z is the union 8 of four pipes and a 3-ball.

Lemma 22

We have Z = P ∪ S where P = p(5.9. and S is a 3-ball 9 .

Proof Eq. 15 is rewritten as

Thanks to Eq. 53, p(5.9.

The vertices in bold fonts form edges in ∂N :

Proof Let σ ∈ c(S) ∩ c(P ) be a simplex. Since vertices 5,6,7,8 are not in c(S), σ does not have a vertex in {5, 6, 7, 8}. According 10 to Eq. 16, the only triangles in ∂p(a 0 b 0 c 0 , a 1 b 1 c 1 ) that does not have vertices a 0 and a 1 are {b 0 b 1 c 0 , b 1 c 0 c 1 }.

8 Addendum: Z is the disjoint union. 9 Addendum: we also have S ∩ P = ∅ (thanks to Eq. 54).