Jean-Daniel Boissonnat
email: jean-daniel.boissonnat@inria.fr

Ramsay Dyer
email: r.h.dyer@rug.nl

Arijit Ghosh

Steve Y Oudot
email: steve.oudot@inria.fr

Only distances are required to reconstruct submanifolds

Keywords: Witness complex, power protection, sampling, manifold reconstruction

In this paper, we give the first algorithm that outputs a faithful reconstruction of a submanifold of Euclidean space without maintaining or even constructing complicated data structures such as Voronoi diagrams or Delaunay complexes. Our algorithm uses the witness complex and relies on the stability of power protection, a notion introduced in this paper. The complexity of the algorithm depends exponentially on the intrinsic dimension of the manifold, rather than the dimension of ambient space, and linearly on the dimension of the ambient space. Another interesting feature of this work is that no explicit coordinates of the points in the point sample is needed. The algorithm only needs the distance matrix as input, i.e., only distance between points in the point sample as input.

Introduction

We present an algorithm for reconstructing a submanifold of Euclidean space, from an input point sample, that does not require Delaunay complexes, unlike previous algorithms, which either had to maintain a subset of the Delaunay complex in the ambient space [START_REF] Cheng | Manifold Reconstruction from Point Samples[END_REF][START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF], or a family of m-dimensional Delaunay complexes [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF]. Maintaining these highly structured data structures is challenging and in addition, the methods are limited as they require explicit coordinates of the points in the input point sample. One of the goals of this work was to develop a procedure to reconstruct submanifolds that only uses elementary data structures.

We use the witness complex to achieve this goal. The witness complex was introduced by Carlsson and de Silva [START_REF] Carlsson | Topological estimation using witness complexes[END_REF]. Given a point cloud W , their idea was to carefully select a subset L of landmarks on top of which the witness complex is built, and to use the remaining data points to drive the complex construction. More precisely, a point w ∈ W is called a witness for a simplex σ ∈ 2 L if no point of L \ σ is closer to w than are the vertices of σ, i.e., if there is a closed ball centered at w that includes the vertices of σ, but contains no other points of L in its interior. The witness complex is then the largest abstract simplicial complex that can be assembled using only witnessed simplices. The geometric test for being a witness can be viewed as a simplified version of the classical Delaunay predicate, and its great advantage is to only require mere comparisons of (squared) distances. As a result, witness complexes can be built in arbitrary metric spaces, and the construction time is bound to the size of the input point cloud rather than to the dimension d of the ambient space.

Since its introduction, the witness complex has attracted interest, which can be explained by its close connection to the Delaunay triangulation and the restricted Delaunay complex [AEM07, BGO09, CIdSZ08, CO08, CdS04, GO08]. In his seminal paper [dS08], de Silva showed that the witness complex is always a subcomplex of the Delaunay triangulation Del(L), provided that the data points lie in some Euclidean space or more generally in some Riemannian manifold of constant sectional curvature. With applications to reconstruction in mind, Attali, Edelsbrunner, and Mileyko [START_REF] Attali | Weak witnesses for Delaunay triangulations of submanifolds[END_REF], and Guibas and Oudot [START_REF] Guibas | Reconstruction Using Witness Complexes[END_REF] considered the case where the data points lie on or close to some m-submanifold of R d . They showed that the witness complex is equal to the restricted Delaunay complex when m = 1, and a subset of it when m = 2. Unfortunately, the case of 3-manifolds is once again problematic, and it is now a well-known fact that the restricted Delaunay and witness complexes may differ significantly (no respective inclusion, different topological types, etc) when m ≥ 3 [START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF]. To overcome this issue, Boissonnat, Guibas and Oudot [START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF] resorted to the sliver removal technique on some superset of the witness complex, whose construction incurs an exponential dependence on d, the dimension of the ambient space. The state of affairs as of now is that the complexity of witness complex based manifold reconstruction is exponential in d, and whether it could be made only polynomial in d (while still exponential in m) was an open question, which this paper answers affirmatively.

Our contributions

Our paper builds on recent results on the stability of Delaunay triangulations [START_REF] Boissonnat | The stability of Delaunay triangulations[END_REF] which we extend in the context of Laguerre geometry where points are weighted. We introduce the notion of power protection of Delaunay simplices and show that the weighting mechanism already used in [CDE + 00, CDR05] and [START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF] can be adapted to our context. As a result, we get an algorithm that constructs a (weighted) witness complex that is a faithful reconstruction, i.e. homeomorphic and a close geometric approximation, of the manifold. Differently from previous reconstruction algorithms [ [START_REF] Cheng | Manifold Reconstruction from Point Samples[END_REF][START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF][START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF], our algorithm can be simply adapted to work when we don't 1 have explicit coordinates of the points but just the interpoint distance matrix.

2 Definitions and preliminaries

General notations

We will mainly work in d-dimensional Euclidean space R d with the standard 2 -norm, • . The distance between p ∈ R d and a set X ⊂ R d , is

d(p, X) = inf x∈X x -p .
We refer to the distance between two points a and b as ba or d(a, b) as convenient.

A ball B(c, r) = {x : d(x, c) < r} is open, and B(c, r) = {x : d(x, c) ≤ r} is closed. Generally, we denote the convex hull of a set X by conv(X), and the affine hull by aff(X). The cardinality of X, and not its measure, is denoted by #X. If X ⊆ R, µ(X) denotes the standard Lebesgue measure of X.

For given vectors u and v in R d , u, v denotes the Euclidean inner product of the vectors u and v.

For given U and V vector spaces of R d , with dim U ≤ dim V , the angle between them is defined by

∠(U, V ) = max u∈U min v∈V ∠(u, v).
By angle between affine spaces, we mean the angle between corresponding parallel vector spaces.

The following result is a simple consequence of the above definition. For a proof refer to [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

Lemma 1 Let U and V be vector subspaces of R d with dim(U ) ≤ dim(V ).

1. If U ⊥ and V ⊥ are the orthogonal complements of U and V in R d , then ∠(U, V ) = ∠(V ⊥ , U ⊥ ).

2. If dim(U ) = dim(V ) then ∠(U, V ) = ∠(V, U ).

Let s i (A) denote the i th singular value of matrix A. The singular values are non-negative and ordered by decreasing order of magnitude. The largest singular value s 1 (A) is equal to the norm A of the matrix, i.e., s 1 (A) = A = sup

x =1
Ax .

If A is an r × c matrix, its smallest singular value is

s j (A) = inf x =1
Ax , where j = min{r, c}.

It is easy to see that:

Lemma 2 If A is an invertible j × j matrix, then s 1 (A -1 ) = s j (A) -1 .

Simplices

Given a set of j + 1 points p 0 , . . . , p j in R d , a j-simplex, or just simplex, σ = [p 0 , . . . , p j ] denotes the set {p 0 , . . . , p j }. The points p i are called the vertices of σ and j denotes the combinatorial dimension of the simplex σ. Sometimes we will use an additional superscript, like σ j , to denote a j-simplex. A simplex σ j is called degenerate if j > dim aff(σ). We will denote by R(σ), L(σ), ∆(σ) the lengths of the smallest circumradius, the smallest edge, and the longest edge of the simplex σ respectively. The circumcentre of the simplex σ will be denoted by C(σ) and N (σ) denotes the affine space, passing through C(σ) and of dimension ddim aff(σ), orthogonal to aff(σ).

Any subset {p i 0 , . . . , p i k } of {p 0 , . . . , p j } defines a k-simplex which we call a face of σ. We will write τ ≤ σ if τ is a face of σ, and τ < σ if τ is a proper face of σ. D(q, σ)

σ q q Figure 1: Figure show altitude D(q, σ) of the point q in the simplex σ.
For a given vertex p of σ, σ p denotes the subsimplex of σ with the vertex set {p 0 , . . . , p j }\p. If τ is a j-simplex, and p is not a vertex of τ , we can get a (j + 1)-simplex σ = p * τ , called the join of p and τ . We will denote τ by σ p and will also write σ = σ p * p.

The altitude of a vertex p in σ is D(p, σ) = d(p, aff(σ p )). A poorly-shaped simplex can be characterized by the existence of a relatively small altitude. The thickness of a j-simplex σ of diameter ∆(σ) is defined as

Υ(σ) = 1 if j = 0 min p∈σ D(p,σ) j∆(σ) otherwise.
Boissonnat, Dyer and Ghosh [START_REF] Boissonnat | The stability of Delaunay triangulations[END_REF] connected the geometric properties of a simplex to the largest and smallest singular values of the associated matrix:

Lemma 3 (Thickness and singular value [START_REF] Boissonnat | The stability of Delaunay triangulations[END_REF]) Let σ = [p 0 , . . . , p j ] be a non-degenerate j-simplex in R m , with j > 0, and let P be the m × j matrix whose i th column is p ip 0 . Then 1. s 1 (P ) ≤ √ j∆(σ), and 2. s j (P ) ≥ √ jΥ(σ)∆(σ).

A simplex that is not thick has a relatively small altitude, but we want to characterize bad simplices for which all the altitudes are relatively small.This motivates the definition of Γ 0 -slivers.

Definition 4 (Γ 0 -good simplices and Γ 0 -slivers) Let Γ 0 be a positive real number smaller than one. A simplex σ is Γ 0 -good if Υ(σ j ) ≥ Γ j 0 for all j-simplices σ j ≤ σ. A simplex is Γ 0 -bad if it is not Γ 0 -good. A Γ 0 -sliver is a Γ 0 -bad simplex in which all the proper faces are Γ 0 -good.

Remark 5 (On the good and bad simplex definitions)

1. Observe that in the definition of Γ 0 -good simplex the thickness bound goes down exponentially with dimensions. Ideally, one would like to have the thickness bound to be independent of the dimension of the simplex. We have defined it this way because with the current sliver removal technology we cannot guarantee the output triangulation to have thickness lower bound that is independent of the dimension of the simplices in the triangulation.

2. Observe that a sliver must have dimension at least 2, since Υ(σ j ) = 1 for j < 2. Observe also that our definition departs from the standard one since the slivers we consider have no upper bound on their circumradius, and in fact may be degenerate and not even have a circumradius. Also, observe that for a fixed Γ 0 we say a simplex σ is good if Υ(σ j ) ≥ Γ j 0 for all j-simplices σ j ≤ σ.

Ensuring that all simplices are Γ 0 -good is the same as ensuring that there are no slivers. Indeed, if σ is Γ 0 -bad, then it has a j-face σ j that is not Γ j 0 -thick. By considering such a face with minimal dimension we arrive at the following important observation:

Lemma 6 A simplex is Γ 0 -bad if and only if it has a face that is a Γ 0 -sliver.

Weighted points and weighted Delaunay complex

For a finite set of points L in R d , a weight assignment of L is a non-negative real function from L to [0, ∞), i.e., : L → [0, ∞). A pair (p, (p)), p ∈ L, is called a weighted point. For simplicity, we denote the weighted point (p, (p)) as p . The relative amplitude of is defined as

= max p∈L max q∈L\p (p) p -q . (1)
Given a point x ∈ R d , the weighted distance of x from a weighted point (p, (p)) is defined as

d(x, p ) = x -p 2 -(p) 2 .
We say a sphere S(c, r) is orthogonal to p = (p, (p)) if d(c, p ) = r 2 , i.e., if

p -c 2 = (p) 2 + r 2 .
For a simplex σ = [p 0 , . . . , p k ] with vertices in L and : L → [0, ∞) a weight assignment, we define the -weighted normal space, or just weighted normal space, N (σ) of σ as

N (σ) = x ∈ R d : d(x, p i ) = d(x, p j ), ∀ p i , p j ∈ σ .
We call S(c, r) a -ortho sphere, or just an ortho sphere, of σ if it is orthogonal to the vertices of σ, i.e., if for all p i ∈ σ, we have r 2 = d(c, p i ). Every c ∈ N (σ) is the center of an ortho sphere S(c, r) with r 2 = d(c, p 0 ), and conversely, every ortho sphere is centered in N (σ).

We define the -weighted (or just weighted) center of σ as

C (σ) = argmin x∈N (σ) d(x, p 0 ). N (σ) is an orthogonal compliment of aff(σ) intersecting aff(σ) at C (σ).
The -weighted (or just weighted) ortho-radius of σ is defined by

R (σ) 2 = d(C (σ), p 0 ).
Note that weighted othro-radius R (σ) 2 can be negative, i.e., R (σ) 2 < 0. For a point p ∈ L we define the weighted Voronoi cell Vor (p) of p as For a simplex σ = [p 0 , . . . , p k ] with vertices in L, the weighted Voronoi face Vor (σ) of σ is defined as

Vor (p) = {x ∈ R d : ∀ q ∈ L \ p, d(x, p ) ≤ d(x, q )}.
Vor (σ) = k i=0
Vor (p i ).

Observe that the Voronoi faces are convex. We define dim Vor (σ) to be the dimension of aff(Vor (σ)).

The weighted Voronoi cells give a decomposition of R d , denoted Vor (L), called the weighted Voronoi diagram of L corresponding to the weight assignment . Let c ∈ Vor (σ) and r 2 = d(c, p i ) where p i ∈ σ. We will call a S(c, r) -ortho Delaunay sphere, or just Delaunay sphere, of σ.

The weighted Delaunay complex Del (L) is defined as the nerve of Vor (L), i.e., σ ∈ Del (L) iff Vor (σ) = ∅. Federer [START_REF] Federer | Curvature Measures[END_REF] proved that rch(M) is (strictly) positive when M is of class C 2 or even C 1,1 , i.e. the normal bundle is defined everywhere on M and is Lipschitz continuous. For simplicity, we are anyway assuming that M is a smooth compact submanifold.

Manifolds and reach

T p M and N p M denote the tangent space and normal space at p ∈ M. We will use the following results from [START_REF] Federer | Curvature Measures[END_REF][START_REF] Giesen | Shape Dimension and Intrinsic Metric from Samples of Manifolds[END_REF][START_REF] Boissonnat | Constructing intrinsic Delaunay triangulations of submanifolds[END_REF]. See [

(T q M, T p M) M d(x, T p M) d(z, M) T q M T p M
Figure 4: Diagram for the Lemma 7.

Lemma 7 Let p be a point on the manifold M.

1. If x ∈ M and p -x < rch(M), then sin ∠(px, T p M) ≤ p-x 2rch(M) . 2. If z ∈ T p M and p -z < rch(M) 4 then d(z, M) ≤ 2 p-z 2 rch(M) .
3. If q ∈ M and pq < rch(M)

4

, then sin ∠(T p M, T q M) < 6 p-q rch(M) .

The following structural result is a restricted version1 of a result due to Boissonnat, Guibas and Oudot [START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF]Lem. 4.3 & 4.4].

Lemma 8 Let L ⊆ M be a -sample of M with < rch(M), and : L → [0, ∞) be a weight assignment with < 1 2 .

1. For all p ∈ L, (p) ≤ 2 .

2. If ≤ rch(M)

4

, then, for all x ∈ M and k ∈ {0, 1}, the Euclidean distance between x and its (k + 1)-nearest weighted neighbor in L is at most (1 + 2 + 2k(1 + 3 )) .

The following result, due to [START_REF] Boissonnat | Delaunay stability via perturbations[END_REF], bounds the angle between the affine plane of a simplex with vertices on the manifold M and the tangent planes to the manifold M at the vertices of the simplex.

Corollary 9 Let σ be a k-simplex with k ≤ m and the vertices of σ are on the submanifold M of dimension m. If σ is Γ 0 -good and ∆(σ) < rch(M), then for all p ∈ σ we have

sin ∠(aff(σ), T p M) ≤ ∆(σ) Γ m 0 rch(M)
.

The Witness Complex

Wit(L, W ) w Definition 2 Wit(L, W ) () 8⌧  9w 2 W with d(w, p)  d(w, q) 8p 2
8q 2 L \ L : Landmarks (black dots); the vertices of the complex W : Witnesses (blue dots)

R. Dyer (INRIA) Del(L, M) = Wit(L, W ) Assisi, EuroCG 2012 2 / 10 (a) (b)
Figure 5: (a) Blue points are the witnesses W and the black points are the landmarks L. All the landmarks in this example are assigned "zero" weights. The simplex σ is witnessed by w. Note that the figure is taken from the paper [START_REF] Boissonnat | A probabilistic approach to reducing algebraic complexity of computing Delaunay triangulations[END_REF]. (b) In the figure witness set (blue points) and the landmark set (red) are sampled from the black curve. The landmarks are assigned "zero" weight. The one-dimensional complex (drawn in blue) is the witness complex approximating the black curve

Witness, cocone and tangential complex

We now recall the definition of the weighted witness complex introduced by de Silva [dS08]. Let W ⊂ R d , and let L ⊆ W be a finite set, and : L → [0, ∞) be a weight assignment of L. The points in the set W are called witnesses and the points in L are called landmarks.

• We say w ∈ W is a -witness of a simplex σ = [p 0 , . . . , p k ] with vertices in L, if the p 0 , . . . , p k are among the k + 1 nearest neighbors of w in the weighted distance, i.e., p ∈ σ, q ∈ L \ σ, d(w, p ) ≤ d(w, q ). See Figure 5 (a).

• The -witness complex Wit (L, W ) is the maximum abstract simplicial complex with vertices in L, whose faces are -witnessed by points of W . When there is no ambiguity, we will call Wit (L, W ) just witness complex for simplicity. See Figure 5 (b).

For any point p on a smooth submanifold M and θ ∈ [0, π 2 ], we call the θ-cocone of M at p, or K θ 0 (p) for short, the cocone of semi-aperture θ around the tangent space T p M of M at p:

K θ (p) = x ∈ R d : ∠(px, T p M) ≤ θ .
Given an angle θ ∈ [0, π 2 ], a finite point set P ⊂ M, and a weight assignment : P → [0, ∞), the weighted θ-cocone complex of P, denoted by K θ (P), is defined as

K θ (P) = σ ∈ Del (P) : Vor (σ) ∩ p∈σ K θ (p) = ∅ .
(2)

The cocone complex was first introduced by Amenta, Choi, Dey and Leekha [START_REF] Amenta | A Simple Algorithm for Homeomorphic Surface Reconstruction[END_REF] in R 3 for reconstructing surfaces and was later generalized by Cheng, Dey and Ramos [START_REF] Cheng | Manifold Reconstruction from Point Samples[END_REF] for reconstructing submanifolds. The weighted tangential complex, or just tangential complex, of P is the weighted θ-cocone complex K θ (P) with θ equal to "zero" and will be denoted by Del (P, T M). The Tangential complex was first defined by Boissonnat and Flötotto [START_REF] Boissonnat | A coordinate system associated with points scattered on a surface[END_REF] for getting a coordinate system from a point set sampled from a surface. Boissonnat and Ghosh [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF] later extended the definition to the weighted setting and using the weighted tangential complex they gave the first manifold reconstruction algorithm whose time complexity depends linearly on the ambient dimension.

Hypothesis 10 For the rest of this paper, we take

θ 0 def = π 32 , K(p) def = K θ 0 (p), and
K (P) def = K θ 0 (P). 3 Power protection √ R 2 + δ 2 σ q R c
Figure 6: Example of δ 2 -power protection when points are not weighted, i.e., the points have "zero" weight.

Let P ⊂ R d be a finite point sample. A simplex σ ∈ Del (P) is δ 2 -power protected at c ∈ Vor (σ) if q -c 2 -(q) 2 > p -c 2 -(p) 2 + δ 2 for all q ∈ L \ σ and p ∈ σ.
For convenience, we will say a simplex σ ∈ Del (P) is δ 2 -power protected if ∃ c ∈ Vor (σ) such that σ is δ 2 -power protected at c. The following result shows that power protecting d-simplices implies power protecting lower dimensional subsimplices as well.

Lemma 11 Let P ⊂ R d be a set of points, and let : P → [0, ∞) be a weight assignment. In addition, let p be a point of P whose Voronoi cell Vor (p) is bounded. Then, if all the d-simplices

B(c 1 , R 1 ) B(c 1 , R 1 ) B(c 2 , R 2 ) B(c 2 , R 2 ) B(c, R) B(c, R ) σ σ 1 c c 2 c 1 σ 2
Figure 8: The two triangles σ 1 and σ 2 are δ 2 -power protected at c 1 and c 2 respectively. The figure shows that the edge σ = σ 1 ∩ σ 2 is δ 2 2 -power protected at c = c 1 +c 2 2 . Note that the vertices of the triangles have "zero" weight and for i ∈ {1, 2}, R i = R 2 i + δ 2 . See, Lemma 11 for a more general result.

incident to p in Del (P) are δ 2 -power protected, with δ > 0, then any j-simplex in Del (P) incident to p is δ 2 dj + 1 -power protected.

The proof of the Lemma 11 is done in the lifted R d+1 space where power protection translates to vertical distance of points from hyperplanes, see Section 3.3. Lemma 11 also implies that if aff P = R d and if all the d-simplices in Del (P) are δ 2power protected then all the simplices, not on the boundary of Del (P), are also power protected. Another interesting aspect of this result is the fact that the decay in power protection to lower dimensional simplices goes down linearly with the dimension of the ambient space.

To prove Lemma 11 we need the following lemma on power protection.

Lemma 12 Let P ⊂ R d and : P → [0, ∞) be a weight distribution. Let p ∈ P such that Vor (p) is bounded and all the d-simplices in Del (P) incident to p are δ 2 -power for some δ > 0.

Then 1. the dimension of the maximal simplices in Del (P) incident to p is equal to d; and 2. for all j-simplices σ j ∈ Del (P) incident to p, dim Vor (σ j ) = dj.

Proof of Lemma 12

Remark 13 (On Lemma 12) Observe that since Vor (p) is bounded, we have dim aff(P) = d.

The following lemma is analogous to [BDG13b, Lem. 3.2], and the proof is exactly like the proof of that lemma.

Lemma 14 (Maximal simplices) Every σ ∈ Del (P) incident to p is a face of a simplex σ ∈ Del (P) with dim aff(σ ) = d.

The following lemma is a direct consequence of the above result.

Lemma 15 (No degeneracies) If every d-simplex in Del (P) incident to p is δ 2 -power protected for some δ > 0, then there are no degenerate (see the definition of degenerate simplex given in Section 2.2) simplices in Del (P) that are incident to p.

Like in the case of Lemma 14, following result is analogous to [BDG13b, Lem. 3.3] and can be proved exactly along the same lines.

Lemma 16 (Separation) If σ j ∈ Del (P) is a j-simplex incident to p with Vor (σ j ) bounded, and q ∈ P \ σ j , then there is a d-simplex σ d ∈ Del (P) incident to p such that σ j ≤ σ d and q ∈ σ d .

Proof of Lemma 12

The first assertion follows directly from Lemmas 14 and 15.

For the second assertion, we observe that dim Vor (σ j ) ≤ dj since Vor (σ j ) ⊆ N (σ j ), and dim N (σ j ) = dj because σ j is nondegenerate. In particular, if j = d, then we must have dim Vor (σ j ) = 0. We obtain the result for all j by showing, by induction on i = dj, that if

σ j ≤ σ j+1 , then dim Vor (σ j ) > dim Vor (σ j+1 ). (3)
Assume then that dim Vor (σ j+1 ) = d -(j + 1). We will show that for any facet σ j < σ j+1 there is a point c ∈ Vor (σ j ) such that c ∈ N (σ j+1 ). The claim (3) then follows since aff(Vor (σ j+1 )) ⊆ aff(Vor (σ j )) and Lemma 15 implies dim N (σ j+1 ) = d -(j + 1), and therefore N (σ j+1 ) = aff(Vor (σ j+1 )) by the hypothesis on the dimension of Vor (σ j+1 ).

Let q ∈ σ j+1 \ σ j . From Lemma 16, there exists a d-simplex σ d ∈ Del (P) such that σ j < σ d and q ∈ σ d . Since all the d-simplices of Del (P) incident to p are δ 2 -protected, the circumcentre c ∈ Vor (σ d ) satisfies

d(c, r ) < d(c, s ) -δ 2 , for all r ∈ σ d and s ∈ P \ σ d . (4)
More specifically, this implies

d(c, r ) < d(c, q ) -δ 2 , ∀ r ∈ σ j , (5)
since q ∈ σ d and σ j < σ d . Thus c ∈ N (σ j+1 ), and c is the desired point since c ∈ Vor (σ d ) ⊆ Vor (σ j ).

x d+1 p = (p, (p))

X d (p) 2 (p) 2 H H p p p q Figure 9: In the figure p = φ(S(p, (p))), p = φ(S(p, r)) where r 2 = -(p) 2 and q = φ(S(p, 0)).
Note that the hyperplanes H and H p are parallel and the hyperplane H is tangential to the paraboloid (drawn in red), i.e.,

x d+1 = d i=1 x 2 i . Note that X d = (x 1 , . . . , x d ).

Lifting map, space of spheres and Voronoi diagram

We are going to argue about the power protection of Delaunay simplices in the "space of spheres" or "lifting space". For our purposes we will be working primarily from the Voronoi perspective.

We will give a self-contained summary of the properties of the space of spheres that we will use. Full details can be found in [BY98, Chap. 17]. Since we will be dealing with ortho spheres, see the definition in Section 2.3, in this section a sphere S(c, r) can have r 2 < 0.

The lifting map φ takes a sphere S(c, r) in R d , with centre c ∈ R d and radius r, to the point

(c, c 2 -r 2 ) ∈ R d+1 , i.e., φ(S(c, r)) = (c, c 2 -r 2 ).
We consider the points in R d to be spheres with r = 0, and thus R d itself is represented as a (hyper-) paraboloid in R d+1 , i.e, x d+1 = d i=1 x 2 i . Let P be a locally finite point set and : P → [0, ∞) be a weight distribution. The set of spheres that are orthogonal to point p, with weight (p), are represented by a hyperplane H p ⊂ R d+1 that passes through φ(S(p, r)) where r 2 = -(p) 2 . Indeed, for any sphere S(c, r) orthogonal to p = (p, (p)) satisfies

r 2 = c -p 2 -(p) 2 . This implies φ(S(c, r)) = (c, c 2 -r 2 ) = (c, 2 c, p + (p) 2 -p 2 ).

So the hyperplane is

H p = {(c, h) ∈ R d × R | h = 2 c, p + (p) 2 -p 2 }; see Figure 9.
For any p ∈ P ⊂ R d , we represent its Voronoi cell Vor (p) in the space of spheres by associating to each c ∈ Vor (p) the unique sphere S(c, r), where

r 2 = p-c 2 -(p) 2 . Thus φ(Vor (p)) ⊆ H p .
For any Delaunay simplex σ ∈ Del(P), its Voronoi cell Vor (σ) = p∈σ Vor (p) is mapped in the space of spheres to the intersection of the hyperplanes that support the lifted Voronoi cells of its vertices:

φ(Vor (σ)) ⊂ p∈σ H p .
If P is generic and σ is a k-simplex, then φ(Vor (σ)) lies in a (dk)-dimensional affine space.

We can say more. The lifted Voronoi cell φ(Vor (σ)) is a convex polytope. Any two points z, z ∈ φ(Vor (σ)) have corresponding points c, c ∈ Vor (σ) ⊂ R d , and a line segment between c and c gets lifted to a line segment between z and z in φ(Vor (σ)).

3.3 Proof of Lemma 11: power protection in the "space of spheres" framework We can talk about the power-protection at a point c ∈ Vor (σ): it is the power-protection enjoyed by the Delaunay sphere S(c, r) centered at c. For a point q ∈ P \ σ, we say that c is δ2 -power-protected from q if qc 2 -(q) 2r 2 > δ2 .

H q x d+1 X d z δ 2 < z
In the lifting space, if z = φ(S(c, r)), then the power protection of c from q is given by the "vertical" distance of z above H q , which we will refer to as the clearance of z above H q . See, Figure 10.

Thus for any q ∈ P \ σ we have a function f q : φ(Vor (σ)) → R which associates to each z ∈ φ(Vor (σ)) the clearance of z above H q . This is a linear function of the sphere centres. Indeed, if p ∈ σ and z = φ(S(c, r)), then r 2 + (p) 2 = pc 2 , and

f q (z) = 2 c, p -q -( p 2 -q 2 ) + ( (p) 2 -(q) 2 ). C (σ 1 ) C (σ 2 ) C (σ 3 ) c * Vor (σ) Figure 11: Diagram for Lemma 11. In the figure σ is a (d -2)-dimensional simplex with σ < σ i , with i ∈ {1, 2, 3}, where σ i is a d-dimensional simplex δ 2 -power protected at C (σ i ). From the proof of Lemma 11 we get that σ is δ 2 3 -power protected at c * = 1 3 3 i=1 C (σ i ) .

Proof of Lemma 11

We wish to find a bound h j (δ) such that if all the d-simplices in Del (P) incident to p are δ 2 -power-protected, then the Delaunay j-simplices incident to p will be h j (δ)power-protected. Since Vor (σ j ) ⊆ Vor (p) and Vor (p) is bounded, we observe that for any jsimplex σ j its Voronoi cell Vor (σ j ) is the convex hull of Voronoi vertices: the -weighted centres of the Delaunay d-simplices that have σ j as a face. It follows that φ(Vor (σ j )) is the convex hull of a finite set of points which correspond to these d-simplices. Note that from Lemma 12 we have that dim(Vor (σ j )), which is equal to dim(φ(Vor (σ j ))), is dj. We choose an affinely independent set {z i }, i ∈ {0, 1, . . . , k}, of k + 1 of these points, where k = dj. See Figure 11. Let

z * = 1 k + 1 k i=0 z i
be the barycenter of these lifted Delaunay spheres, and consider the clearance, f q (z * ), of z * above H q , where q ∈ P \ σ j . Observe that z * is an interior point of φ(Vor (σ j )). Let σ i be the Delaunay d-simplex corresponding to z i . There must be a σ , l ∈ {0, . . . , k}, which does not contain q, since otherwise the k-simplex defined by the set {z i } i∈{0,...,k} would lie in φ(Vor (q * σ j )), implying dim φ(Vor (q * σ j )) ≥ k, which contradicts Lemma 12. Since σ is δ 2 -power-protected, we have f q (z ) > δ 2 , and by the linearity of f q we get a bound on the clearance of z * above H q :

f q (z * ) = 1 k + 1 k i=0 f q (z i ) ≥ f q (z ) k + 1 > δ 2 k + 1 .
Since q was chosen arbitrarily from P \ σ j , this provides a lower bound on the power protection at c * ∈ Vor (σ j ), where z * = φ(S(c * , r * )), and hence a lower bound on the power protection of σ j .

Remark 17 If we could find two lifted Voronoi vertices z 1 and z 2 such that the line segment between them lies in the relative interior of φ(Vor (σ j )), then the midpoint of that segment would have a power protection of δ 2 2 . However, this isn't possible in general, for Vor (σ j ) could be a (dj)-simplex, when σ j is not a maximal shared face of any two Delaunay d-simplices.

Stability, protection, and the witness complex

Our main structural result, Theorem 19 below, gives conditions that guarantee that Del (L, T M) = Wit (L, W ). Since the proof of Theorem 19 is quite long and technical, it goes through multiple stages which we will only outline in this section. For full details refer to Appendix A. We begin by introducing some parameters and terminology employed in the statement of the theorem.

Let M be a m-dimensional submanifold of R d , α 0 < 1 2 an absolute constant 2 , and Γ 0 < 1 and δ 0 < α 0 parameters to the algorithm satisfying Inequality (12); see Lemma 21 from Section 5. We define α0

def = α 2 0 -δ 2 0 .
Definition 18 (Elementary weight perturbations and stable weight assignments) Let W ⊂ M be an ε-sample of M, L ⊂ W a λ-net of W with ε ≤ λ, and : L → [0, ∞) a weight assignment with relative amplitude (1) satisfying ≤ α0 . A weight assignment ξ : L → [0, ∞) will be called an elementary weight perturbation of (ewp for short) if

∃ p ∈ L, ξ(p) ∈ (p), (p) 2 + δ 2 0 λ 2 and ξ(q) = (q) if q ∈ L \ p.
We call the weight assignment : L → [0, ∞) stable (resp., locally stable at p ∈ L) if for all ewp ξ of , K ξ (L) contains no Γ 0 -slivers of dimension ≤ m + 1 (resp., no such slivers incident to p).

δ 2 0 m + 1 - 2 15 λ rch(M) (7) then, Del (L, T M) = Wit (L, W ).
In addition, if λ is sufficiently small, then Wit (L, W ) is homeomorphic to, and a close geometric approximation of, M.

Since is a stable weight assignment, K (L) contains no Γ 0 -slivers of dimension ≤ m + 1. The proof of Theorem 19 relies on the following three properties P1, P2 and P3, which hold for λ sufficiently small.

P1 For all σ ∈ K (L), ∠(aff σ, T p M) = O(λ).
P2 The simplices of Del (L, T M) have dimension at most m, and the maximal dimension of simplices in K (L) is ≤ m.

2 By absolute constant we mean that α0 is independent of the dimension of the manifold or other parameters of the algorithm. For simplicity, the reader can take α0 = 1 3 for the rest of this paper.

P3 For all σ ∈ Del (L, T M) and p ∈ σ, Vor (σ) ∩ T p M = ∅.

The above properties are direct consequence of results from [CDR05, BGO09, BG14]. For the full details see Lemma 32 in Appendix A. Using properties P1, P2 and P3, we will give the outline of the proof of Wit (L, W ) = Del (L, T M).

The part about homeomorphism and close geometric aspect of Theorem 19 will directly follow from a result of Boissonnat and Ghosh [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

We will now give an outline of the proof of Wit (L, W ) = Del (L, T M).

Step 1: Wit (L, W ) ⊆ Del (L, T M). This step is proved by contradiction in Lemma 34. Let σ k ∈ Wit (L, W ) be a k-simplex with σ k ∈ Del (L, T M) and p a vertex of σ k . We will show that if this is the case then there exists σ m+1 with σ k ≤ σ m+1 and σ m+1 ∈ K (L). We will reach a contradiction via Property P2.

Using the sampling assumptions on L and W , we can show that for any w ∈ W that is a -witness of σ k or of its subfaces,

p -w = O(λ) [BGO09, Lem. 4.4]. This implies, from [GW04, Lem. 6], d(w, T p M) = O λ 2 rch(M)
.

From [dS08, Thm. 4.1], we know that Vor (σ k ) intersects the convex hull of the -witnesses of σ k and its subfaces. Let c k ∈ Vor (σ k ) be a point in this intersection. We have

d(c k , T p M) = O λ 2 rch(M)
and, since L is λ-sparse and < 1 2 ,

d(p, c k ) ≥ d(p, C (σ k )) ≥ 3λ 8 . 3
Therefore, using the sampling assumption on λ, we get

d(c k , T p M) d(c k , p) = O λ rch(M) < sin θ 0 .
By the definition of the cocone complex, see Equation (2), this implies that

σ k ∈ K (L). Since ∠(aff σ k , T p M) is small (property P1), there exists c k ∈ T p M such that the line segment [c k , c k ] is orthogonal to aff(σ k ) and d(c k , c k ) = O λ 2 rch(M)
.

3 Let p and q be distinct vertices of σ k , and let x be an orthogonal projection of C (σ k ) on the line through p and q. Since < 1 2 , x ∈ pq. Using the facts that d(x, p ) = d(x, q ), pq ≥ λ and (q) < p-q 2 (as < 1/2), we get

p -x = p -q 2 1 + (p) 2 -(q) 2 p -q 2 ≥ p -q 2 1 - (q) 2 p -q 2 ≥ 3λ 8 (8)
The bound on d(p, C (σ k ) ) follows from the fact that d(p, x)

≥ d(p, C (σ k )).
Again, as λ is small, the line segment

[c k , c k ] is contained in K(p). Since σ k ∈ Del (L, T M), ∃ c k+1 ∈ [c k , c k ] and a Delaunay (k + 1)-simplex σ k+1 such that c k+1 ∈ Vor (σ k+1 ) with σ k < σ k+1 .
Therefore, σ k+1 ∈ K (L). If k = m, we have reached a contradiction with property P2. Otherwise, using the facts that

∠(σ k+1 , T p M) is small, d(c k+1 , T p M) = O λ 2 rch(M) and d(p, c k+1 ) = Ω(λ), we will find a c k+1 ∈ T p M such that [c k+1 , c k+1 ] ∈ K(p). Since σ k+1 ∈ K (L), ∃ c k+2 ∈ [c k+1 , c k+1 ] and (k + 2)-simplex σ k+2 ∈ K (L) such that c k+2 ∈ Vor (σ k+2 ) and σ k+1 < σ k+2 .
Continuing this procedure of walking on the Voronoi cell of the simplex from a point, like c k+1 , in the intersection the Voronoi cell of the simplex and K(p) towards T p M, we will get a sequence of points c k , . . . , c m+1 and simplies

σ k < • • • < σ m+1 with c j ∈ Vor (σ j ) ∩ K(p) and σ j ∈ K (L).
We have now reached a contradiction via property P2. This concludes the proof of Step 1.

Step 2: Del (L, T M) ⊆ Wit (L, W ). We say that a simplex σ ∈ Del (L, T M) is δ 2 -power protected on T p M if it is δ 2 -power protected at a point c ∈ Vor (σ) ∩ T p M. In Lemma 35 we show that the stable weight assignment implies that all m-simplices in Del (L, T M) are δ 2 -power protected on T p M, where δ = δ 0 λ. To reach a contradiction, let us assume that there exists a m-simplex σ ∈ Del (L, T M) that is not power protected on T p M for some p ∈ σ. Then for any c ∈ Vor (σ) ∩ T p M there exists q ∈ L \ σ such that

d(c, p ) ≥ d(c, q ) -δ 2 .
Consider now the following weight assignment:

ξ(x) = (x) if x = q (q) 2 + β 2 if x = q where β 2 = d(c, q ) -d(c, p ).
It is easy to see that ξ is an ewp of and ξ < 1/2. Observe that the (m + 1)-simplex σ = q * σ is in K ξ (L). Since λ is sufficiently small, σ is a Γ 0 -bad (m + 1)-simplex; broadly, the idea (see also the proofs of [CDR05, Lem. 13] and [BG14, Lem. 4.9]) is that the thickness of any (m + 1)-simplex embedded in R m is zero, and here σ is a (m + 1)-simplex embedded in R d , but whose vertices belong to a small neighborhood of a m-dimensional submanifold M of R d so we can show that its thickness is small. By proving that σ is Γ 0 -bad, we arrive at a contradiction with the fact that is a stable weight assignment.

In the first part of the proof of Lemma 38 we prove that all simplices (of all dimensions) in Del (L, T M) are δ 2 m+1 -power protected on T p M for all p ∈ σ. To establish this result, we want to use Lemma 11 but we cannot use the lemma directly since it only holds for d-simplices of R d . To overcome this issue, we resort to Lemma 2.2 of [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF] which states that Vor (L)∩T p M is identical to a weighted Voronoi diagram Vor ψ (L ) where L is the orthogonal projection of L onto T p M, i.e., Vor (σ) ∩ T p M = Vor ψ (σ ) where σ is the projection of σ onto T p M. Also we can prove, using P1, that δ 2 -power protection of a simplex σ ∈ Del (L, T M) incident to p on T p M implies δ 2 -power protection of σ ∈ Del ψ (L ). Using this correspondance, we can show that all m-simplices incident to p in Del ψ (L ) are δ 2 -power protected since all the m-simplices incident to p in Del (L, T M) are δ 2 -power protected on T p M. We can now use Lemma 11. Using the bound on λ, we can show that Vor ψ (p) = Vor (p) ∩ T p M is bounded, see [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF]Lem. 4.4]. From Lemma 11, we then get that all j-simplices in Del ψ (L ) incident to p are δ 2 m+1 -power protected. This result, together with the correspondence we have established between the power protection of simplices incident to p in Del ψ (L ) and the power protection on T p M of simplices incident to p in Del (L, T M), we deduce that all j-simplices incident to p in Del (L, T M) are δ 2 m+1 -power protected on T p M. Let σ be δ 2 m+1 -power protected at c ∈ Vor (σ) ∩ T p M, where p ∈ σ. We can show that there exists c ∈ M, such that cc is small compared to δ 2 m+1 and the line passing through c and c is orthogonal to aff(σ). Using simple triangle inequalities, we can prove that σ is Ω δ 2 m -power protected at c . See Lemma 38.

As W is an ε-sample of M, we can find a w ∈ W such that w -c < ε. Using the facts that ε is much smaller than δ 2 = δ 2 0 λ 2 and σ is Ω δ 2 m -power protected at c , we get w to be a -witness of σ. Since σ is an arbitrary simplex of Del (L, T M), we have proved that Del (L, T M) ⊆ Wit (L, W ). See Lemma 39.

This ends the proof of Theorem 19.

Reconstruction algorithm

Let M be a smooth submanifold with known dimension m, let W ⊂ M be an ε-sample of M, and let L ⊂ W be a λ-net of W for some known λ. We will also assume that ε < λ, which implies that L is a (λ, 2λ)-net of M. We will discuss the reasonability of these assumptions in Section 5.3. The primary task of the algorithm is to find a stable weight assignment : L → [0, ∞). We will prove that this is possible if Γ 0 , δ 0 , and the absolute constant α 0 < 1 2 satisfy Inequality (12) (Lemma 21).

Once we have calculated a stable weight assignment , we can just output the witness complex Wit (L, W ), which is a faithful reconstruction of M by Theorem 19.

Outline of the algorithm

We initialize all weights by setting 0 (q) = 0 for all q ∈ L. We then process each point p i ∈ L, i ∈ {1, . . . , n}. At step i, we compute a new weight assignment i satisfying the following properties:

C1. i ≤ α0 , and ∀ q ∈ L \ {p i }, i (q) = i-1 (q).
C2. i is locally stable at p i .

Once we have assigned weights to all the points of L in the above manner, the algorithm outputs Wit (L, W ) where = n is the final weight assignment n : L → [0, ∞).

The crux of our approach is that weight assignments will be done without computing the cocone complex or any other sort of Voronoi/Delaunay subdivision. Rather, we just look at local neighborhoods

N (p i ) def = x ∈ L : #(B(p i , d(p i , x)) ∩ L) ≤ N 1
where N 1 is defined in Lemma 22. The main idea is the following. We define the candidate simplices of p i as the Γ 0 -slivers σ of dimension ≤ m + 1, with vertices in N (p i ), p i ∈ σ, and of diameter ∆(σ) ≤ 16λ. For such a candidate simplex σ, we compute a forbidden interval I i-1 (σ, p i ) (to be defined in Section 5.2). We then select a weight for p i that is outside all the forbidden intervals of the candidate simplices of p i .

We will denote by S(p i ) the set of candidate simplices of p i . For a point p in L, we write

nn(p) def = min q∈L\p p -q .
Algorithm 1 Pseudocode of the algorithm Input: L, W , Γ 0 , δ 0 and m // let L = {p 1 , . . . , p n } // parameters Γ 0 , δ 0 and m satisfy Eq. ( 12)

Initialization: 0 : L → [0, ∞) with 0 (p) = 0, ∀ p ∈ L; Compute: nn(p), N (p) for all p ∈ L for i = 1 to n do Compute: candidate simplices S(p i ); I ← σ∈S(p i ) I i-1 (σ, p i ); i (q) ← i-1 (q) for all q ∈ L \ {p i }; x ← a point from [0, α2 0 nn(p i ) 2 ] \ I; i (p i ) ← √ x;
end for Output: Wit n (L, W );

Analysis

Correctness of the algorithm

Forbidden intervals and elementary weight perturbations are closely related (see Lemma 20 below) and we will prove in Lemma 21 that, if Inequality ( 12) is satisfied, we can find a locally stable weight assignment i at each iteration of the algorithm. Moreover, we will prove that if all i are locally stable, then we will end up with a stable weight assignment = n for which Theorem 19 applies. In this respect our algorithm is in the same vein as the seminal work of Cheng et al.

[CDE + 00]. See also [CDR05, BGO09, BG14].
For a given weight assignment : L → [0, ∞), and a simplex σ with vertices in L, we define

F (p, σ) def = D(p, σ) 2 + d(p, N (σ p )) 2 -R (σ p ) 2 . ( 9
)
Note that F (p, σ) depends on the weights of the vertices of σ p and not on the weight of p. This crucial fact will be used in the analysis of the algorithm. If σ is a candidate simplex of p, the forbidden interval of σ with respect to p is

I (σ, p) def = F (p, σ) - η 2 , F (p, σ) + η 2 , (10)
where

η def = 2 14 Γ 0 + δ 2 0 Γ m 0 λ 2 . ( 11
)
The following result relates candidate simplices, forbidden intervals and stable weight assignments. The proof is included in Appendix B.

Lemma 20 Let L ⊂ M be a (λ, 2λ)-net of M with λ < 1 18 (1sin θ 0 ) 2 rch(M) and : L → [0, ∞) be a weight assignment with ≤ α0 . Let, in addition, p be a point of L, and σ a candidate simplex of p. If there exists an ewp 1 of satisfying 1 ≤ α 0 and σ ∈ K 1 (L), then (p) 2 ∈ I (p, σ).

Lemma 20 shows that the emergence of a candidate simplex σ incident to p in the weighted cocone complex under an ewp implies that the original weight of p had to be in the forbidden interval, i.e., I (p, σ).

The following lemma shows that good weights, i.e., weights which do not lie in any forbidden intervals, exist, which ensures that the algorithm will terminate.

Lemma 21 (Existence of good weights) Assume that λ ≤ rch(M) 512 , and Γ 0 , δ 0 and α0 (=

α 2 0 -δ 2 0 ) satisfy Γ 0 + δ 2 0 Γ m 0 < α2 0 2 14 N ( 12
)
where N = 2 O(m 2 ) and will be defined explicitly in the proof. Then, at the i th step, one can find a weight i (p i ) ∈ [0, α0 nn(p i )] outside the forbidden intervals of the candidate simplices of S(p i ).

Moreover, i satisfies properties C1 and C2.

Using simple packing arguments and Lemma 7 (1), we get the following bound (similar arguments were used, for example, in [GW04, Lem. 9] and [BG14, Lem. 4.12]). For all : L → [0, ∞) with ≤ α 0 , we get from Lemmas 32 (2) and 22 that the set of Γ 0 -slivers of dimension ≤ m + 1 in K (L) that are incident to p i is a subset of S(p i ).

Recall, from Section 2.1, that for X ⊆ R, µ(X) denotes the standard Lebesgue measure of X. Since

µ   σ∈S(p i ) I i-1 (σ, p i )   ≤ σ∈S(p i ) µ(I i-1 (σ, p i )) ≤ N η < α2 0 λ 2 ≤ α2 0 nn(p i ) 2 , we can select (p i ) ∈ [0, α0 nn(p i )] such that (p i ) 2 is
I i-1 (σ, p i ).
By Lemma 20, the weight assignment i we obtain is a locally stable weight assignment for p i .

The following lemma shows that getting a locally stable weight assignment i at each iteration of the algorithm gives a globally stable weight assignment n at the end of the algorithm.

Lemma 23 The weight assignment n : L → [0, ∞) is stable.

Proof

It is easy to see that n ≤ α0 , since for all p ∈ L, the weights were chosen from the interval [0, α0 nn(p)].

We will prove the stability of n by contradiction. Let ξ : L → [0, ∞) be an ewp of n that modifies the weight of q ∈ L, and assume that there exists a Γ 0 -sliver σ = [p i 0 , . . . , p i k ] ∈ K ξ (L). Note that ξ ≤ α 0 , and that for any p ∈ σ, σ ∈ S(p) (from the definition of S(p) and Lemma 22). Without loss of generality assume that

i 0 < • • • < i k .
We will have to consider the following two cases:

Case 1. q is not a vertex of σ. This implies that σ ∈ K n (L) since ξ(x) = n (x) for all x ∈ L\{q}, and ξ(q) ≥ n (q). Using the same arguments, we can show that σ ∈ K i k (L). From Lemma 21 and the fact that i k is an ewp of itself, we have reached a contradiction as i k is a locally stable weight assignment for p i k .

Case 2. q is a vertex of σ. Using the same arguments as in Case 1 we can show that σ ∈ K ξ 1 (L) where ξ 1 : L → [0, ∞) is a weight assignment satisfying: ξ 1 (q) = ξ(q) and ξ 1 (x) = i k (x) for all x ∈ L \ {q}. Observe that ξ 1 is an ewp of i k . As in Case 1, we have reached a contradiction since i k is a locally stable weight assignment for p i k .

Complexity of the algorithm

The following theorem easily follows from the algorithm and the previous analysis.

Theorem 24 Let M be a m-dimensional submanifold of R d , and let W ⊂ M be an ε-sample of M and L ⊆ W be a λ-net of W with ε ≤ λ. Also, assume that the parameters α 0 , δ 0 and Γ 0 satisfy Equation (12) from Lemma 21, and ε and λ satisfy Equations (6) and (7) from Theorem 19. The time and space complexity of Algorithm 1 are

d#L 2 O(m) #L + 2 O(m 2 ) + O(m)#W + O(m 3 #W ) and d#W + #L 2 O(m 2 ) + d + O(m#L × #W )
respectively.

Proof

In the initialization phase of the algorithm one needs to compute nn(p) and N (p) for all p ∈ L. Time time complexity for this part of the procedure will be d2 O(m) (#L) 2 .

Inside the for-loop for each p i ∈ L, one needs to do the following:

1. compute candidate simplices S(p i ) 2. compute I = σ∈S(p i ) I i-1 (σ, p i ) 3. Find a point x in 0, α2 0 nn(p i ) 2 \ I
Observe that for all σ j ⊆ N (p i ) with p i ∈ σ and j ≤ m + 1, we need to check if σ j is in S(p i ) and the time complexity for this procedure for a given σ j is d 2 O(j) . The bound follows from the facts that the number of faces of σ j is 2 j , and for a given face σ k ≤ σ j and a vertex q ∈ σ k , we can compute D(p, σ k ) in time complexity O(d poly(k))4 . If σ j ∈ S(p i ), then the time complexity of computing I i-1 (σ j , p i ) is O(d poly(j)). Time complexity of computing I and finding a point x ∈ 0, α2 0 nn(p i ) 2 \ I will be at most O((#S(p i )) 2 ). Since #S(p i ) = 2 O(m 2 ) , therefore the overall time complexity for one execution of the for-loop will be d2 O(m 2 ) .

The above discussion implies the overall time complexity of computing a stable weight assignment :

L → [0, ∞) will be d 2 O(m 2 ) (#L).
Once a stable weight assignment has been computed then we can use Boissonnat and Maria's simplex-tree based witness complex computation algorithm [BM14, Sec. 3.2] for computing Wit (L, W ). Observe that since : L → [0, ∞) is a stable weight assignment the m-skeleton5 of Wit (L, W ) is equal to Wit (L, W ), see Theorem 19, and therefore we will only compute in the algorithm the m-skeleton of Wit (L, W ). Note that for constructing m-skeleton of Wit (L, W ), the simplex-tree based algorithm of Boissonnat and Maria [START_REF] Boissonnat | The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes[END_REF] will need access to (m + 1)-nearest -weighted neighbors in L for each w ∈ W . The time complexity for computing this (m+1)-nearest -weighted neighbors in L for all witness in W will be O(m#L × #W ). The time complexity of Boissonat and Maria's witness complex construction algorithm will be

O m 3 (#Wit (L, W ) + #W ) = O 2 O(m 2 ) #L + m 3 #W .
The last bound follows from the fact that #Wit (L, W ) = 2 O(m 2 ) #L. Note that the upper bound on #Wit (L, W ) follows from the facts that the dimensions of simplices in Wit (L, W ) are at most m, using ε ≤ λ and from triangle inequality we have L is a (λ, 2λ)-net of M, for all σ ∈ Wit (L, W ) we have ∆(σ) ≤ 16λ (see Lemma 29), and for all p ∈ L we have # (B(p, 16λ) ∩ L) = 2 O(m) (see Lemma 22).

Combining everything, we get that the time complexity of the algorithm is

d #L 2 O(m) #L + 2 O(m 2 ) + O(m)#W #L + O(m 3 #W ).
The space complexity of storing Wit (L, W ) in the simplex-tree data structure is bounded by O (#Wit (L, W )). Hence the overall space complexity of the algorithm is

d#W + (2 O(m 2 ) + d)#L + O(m#L × #W ).
Note that the 2 O(m 2 ) #L term bounds the space complexity of storing N (p) and S(p) for all p ∈ L and Wit (L, W ), the O(m#L × #W ) term comes from storing the -weighted (m + 1)-nearest neighbors in L for each witness w in W , and finally the terms d#L and d#W come from storing the coordinates of the points in L and W respectively.

Regarding the assumptions

We have assumed that we know the dimension of the manifold m, and the value of λ (having an upper bound would have been good enough) where L is a λ-net of W .

We will address the second question first. Given a point sample W , and beginning with an arbitrary point from W , it is simple to show that a furthest point sampling [START_REF] Gonzalez | Clustering to Minimize the Maximum Intercluster Distance[END_REF] from W will generate a λ-net of W , for some λ > 0, and it is possible to keep track of the value of λ. For an analysis of this procedure, refer to [BGO09, Lem. 5.1].

Let P ⊂ M be an (ν, )-net of M. If ν = O(1) and if we know an upper bound on this quantity and if ≤ 0 , where 0 depends only on the reach and the dimension of M, then we can learn the local dimension of the manifold at each sample point with time and space complexity 2 O(m) (#P) 2 and 2 O(m) #P respectively, see [START_REF] Cheng | Provable Dimension Detection Using Principal Component Analysis[END_REF][START_REF] Cheng | Dimension Detection via Slivers[END_REF][START_REF] Giesen | Shape Dimension and Intrinsic Metric from Samples of Manifolds[END_REF]. Note that, in these papers, the dimension estimation is done locally around each sample point and therefore is exactly in the spirit of this paper. For a more detailed discussions on these things refer to Section 6.

Conclusion: only distances required

The algorithm we have outlined can be simply adapted to work in the setting where the input is just a distance matrix corresponding to a dense point sample on the submanifold M. Rather than giving explicit coordinates of the points, we will be given a distance matrix M = (a ij ) where a ij = p ip j and p i , p j ∈ W .

In our reconstruction algorithm, we have to compute things like local neighbors N (p), candidate simplices S(p), forbidden intervals I (σ, p), and the witness complex. We will end the section with a discussion on the sampling conditions, extension to noisy distance matrix and comparisons with other methods.

λ-net L of W . As already discussed in Section 5.2.2, the distance matrix can be used to generate a λ-net L of W by repeatedly inserting a farthest point.

Computing N (p) and S(p). Computing N (p) is simple. For computing S(p), we need to compute the altitude of simplices. This reduces to computing volume of simplices,

D(p, σ j ) = j vol(σ j ) vol(σ j p )
, which can be done from the knowledge of the lengths of its edges. To see this, observe that for a simplex σ = [p 0 , . . . ,

p k ] vol(σ) = 1 k! | det M (σ) | where M (σ) def = (b ij ) 1≤i, j≤k with b ij = p i -p 0 , p j -p 0 = p i -p 0 2 + p j -p 0 2 -p i -p j 2 2 .
The above discussion shows that N (p) and S(p) can be computed directly from the distance matrix.

Computing forbidden intervals I (σ, p). Assume σ is a k-simplex. Recall that computing I (σ, p) will boil down to computing D(p, σ), d(p, N (σ p )) and R (σ p ), see Equations ( 9), ( 10) and (11). We have already discussed how to compute D(p, σ), but observe that d(p, N (σ p )) and R (σ p ) can be computed if we can find a distance preserving embedding of σ into an Euclidean space. Since we know the pairwise distance between vertices of the simplex, a distance preserving embedding of σ can be computed in O(k 3 ), where σ is a k-simplex. See [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF][START_REF] Matoušek | Lecture Notes on Metric Embeddings[END_REF].

Dimension estimation from distance matrix. We will now show that using known algorithms, such as, for example, [GW04, CC09, CWW08], on dimension estimation of submanifolds, one can estimate the dimensions of submanifolds from distance matrices. We will be adapting Cheng, Wang and Wu's approach [START_REF] Cheng | Provable Dimension Detection Using Principal Component Analysis[END_REF]. Let L ⊂ M be a (λ, 2λ)-net of the manifold M and p ∈ L. For the time being we will assume that we have explicit coordinates of the points in the R d , the ambient space, and rch(M) = 1. We want to estimate the unknown dimension m of the manifold at p. Cheng et al. [START_REF] Cheng | Provable Dimension Detection Using Principal Component Analysis[END_REF] showed that if λ is less than some λ 0 , where λ 0 depends only on m, then there exist an absolute constant C such that the covariance matrix6 of the set of vectors {qp | q ∈ X(p)}, where X(p) = {q ∈ L | pq ≤ Cλ}, has a sharp gap between the top m eigenvalues of the covariance matrix and the rest of the eigenvalues. More explicitly, if the

β 1 ≥ β 2 ≥ • • • ≥ β d are
the eigenvalues of the covariance matrix then

β k β i = Θ(1) and β j β i = O(λ 2 ), where 1 ≤ i, k ≤ m and m + 1 ≤ j ≤ d (13)
Using this gap Cheng et al. [START_REF] Cheng | Provable Dimension Detection Using Principal Component Analysis[END_REF] estimated the dimension of M at p. If the set X(p) is given, then the running time of this algorithm will be O(d2 O(m) ). First note that using the sparsity condition on L, as in Lemma 22, we can show that #X(p) = 2 O(m) , and secondly the set X(p) can be computed directly from the distance matrix. The part about covariance matrix can be done by first computing a distance preserving Euclidean embedding of the point set X(p) and then checking the gap in the eigenvalues of the covariance matrix constructed using the coordinate of the embedded points. Note that the dimension of the Euclidean space where the points in X(p) will be embedded is bounded by #X(p) = 2 O(m) . Therefore given the set X(p), the time complexity of the dimension procedure will be 2 O(m) .

Computing witness complex. By its very definition, the witness complex can be built from an interpoint distance matrix. So, we can easily adapt our algorithm, without increasing its complexity, to the setting of interpoint distance matrices, which was not possible with the other reconstruction algorithms that explicitly need coordinates of the points [CDR05, BGO09, BG14].

Noisy distances and geodesic distances. The algorithm given in this paper is quite robust to noise and other distortions of the Euclidean distances. For example, as we discuss below, it could accommodate a distance matrix defined via geodesic distances on the manifold. Recalling the input to the Algorithm 1, let W ⊂ M be an ε-sample of M, and L ⊂ W be a λ-net of W with ε ≤ λ. This implies that L is a (λ, 2λ)-net of M. Without loss of generality we will assume that rch(M) = 1.

We will have access to a noisy distance matrix d(•, •) of W satisfying the following inequality:

d(p, q) p -q -1 ≤ γ.
We will call γ the error fraction of the noisy distances. We will assume that γ = O(λ ρ ) for some ρ > 0. This is a standard noise model [NSW11, CWW08, CFG + 05, DG06], and we will show how the algorithm given in this paper can be adapted to handle this amount of noise, i.e., the case when the error fraction γ = O(λ ρ ) for some constant ρ > 0.

One of the central objects in the paper is thickness, but for the discussion on noisy distances we will be using the notion of fatness. The fatness of a j-simplex σ is defined as

Θ(σ) = vol(σ) ∆(σ) j .
Like in the case of thickness, using the definition of fatness one can characterize bad simplices.

Definition 25 (Θ 0 -good simplices and Θ 0 -slivers) Let Θ 0 be a positive real number smaller than one. A simplex σ is Θ 0 -good if Θ(σ j ) ≥ Θ j 0 for all j-simplices σ j ≤ σ. A simplex is Θ 0 -bad if it is not Θ 0 -good. A Θ 0 -sliver is a Θ 0 -bad simplex in which all the proper faces are Θ 0 -good.

Thickness and fatness are analogous concepts and the calculations done in this paper can easily be done using fatness. For more details on fatness refer to the manifold reconstruction paper of Boissonnat and Ghosh [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

Let σ be a j-simplex with vertices from L, and let vol(σ) and ∆(σ) denote noisy volume and noisy diameter of σ obtained by using noisy distances. Expressions for vol(σ) and ∆(σ) for the simplex σ = [p 0 , . . . , p j ] are the following:

∆(σ) def = max p i ,p k ∈σ d(p i , p k ), and vol(σ) def = det( M (σ)), where M (σ) def = (a ik ) 1≤i, k≤j with a ik = d(p i , p 0 ) 2 + d(p k , p 0 ) 2 -d(p i , p k ) 2 2 .
We came up with this definition of M (σ) to mimic the definition of M (σ) given earlier in the section.

We will call Θ(σ) := vol(σ) ∆(σ) j the noisy fatness of the j-simplex σ. Using [Gho12, Lem. 4.3.6] we can show that noisy fatness and actual fatness are closely related:

Θ(σ) 2 Θ(σ) 2 -1 ≤ O(jλ ρ ). ( 14
)
This shows that we can modify Algorithm 1 in terms of fatness and the candidate simplices can be detected using noisy fatness. Note that candidate simplices in the case of a noisy distance matrix will be defined using Θ 0 -slivers (defined in terms of fatness) rather than Γ 0 -slivers (defined in terms of thickness).

The calculation for computing forbidden intervals in Section B can be easily extended to the case of noisy distances. Also the dimension estimation algorithm of Cheng et al. [START_REF] Cheng | Provable Dimension Detection Using Principal Component Analysis[END_REF] works for noisy point samples and also can be directly extended to the case of noisy distance matrix. This shows that the algorithm given in this paper can be adapted to handle this amount of noise, i.e., the case when the error fraction γ = O(λ ρ ) for some constant ρ > 0.

Another interesting problem to consider is the case when the entries to the distance matrix are geodesic distances, i.e., the entries in the distance matrix are geodesic distances d M (p, q) between the points p and q on the manifold M. For the case of submanifolds, Niyogi, Smale and Weinberger [NSW08, Prop. 6.3] proved the following result connecting geodesic distance and Euclidean distances in a small neighborhood of the submanifold M.

Lemma 26 Let p and q be points on the submanifold M of R d with rch(M) = 1 and pq

≤ 1 2 . Then d M (p, q) p -q -1 ≤ O ( p -q ) .
Therefore for the case of geodesic distances we are again back to the noisy distance framework with the error fraction γ = O(λ).

Sampling conditions. The sampling condition, i.e., the bound on λ in Theorem 19 is quite pessimistic with respect to the reach of the manifold. Naturally this makes the results in this paper to be of more theoretical interest and less relevant for applications. But we feel that the techniques introduced in this paper could be used to get better reconstruction algorithms, and or design new and better reconstruction heuristics. Also, note that the only assumption in this paper was that M is a smooth submanifold with positive reach. If one restrict to a more narrow class of manifolds such as compact flat manifolds then one could easily improve on the sampling conditions. For more details on triangulating closed Euclidean Orbifolds refer to a recent paper of Caroli and Teillaud [START_REF] Caroli | Delaunay Triangulations of Closed Euclidean d-Orbifolds[END_REF].

Comparison with previous works. It is a natural question to ask how other manifold reconstruction algorithms [CDR05, BGO09, BG14] will fair when given only a distance matrix to work with. We will assume that input is a distance matrix corresponding to a dense point sample P of M. Since all the previous algorithms work with explicit coordinates of the points in the point sample one needs to start by first getting a distance preserving embedding into an Euclidean space. Note that this can be done in time O((#P) 3 ) via Cholesky factorization of positive definite matrix.

For more details on Cholesky factorization refer to [GVL13, TB97], and for details on distance preserving embedding into Euclidean space see [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF][START_REF] Matoušek | Lecture Notes on Metric Embeddings[END_REF]. Once we have the embedding then we can apply the previous manifold reconstruction algorithms [START_REF] Cheng | Manifold Reconstruction from Point Samples[END_REF][START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF][START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

We will now outline some of the issues with this approach:

1. Time complexity of getting a distance preserving embedding. The distance preserving embedding will be computed via Cholesky factorization with the time complexity O((#P) 3 ).

2. Noisy distance matrix and geodesic distances. These approaches won't work if the distance matrix given is noisy. Since the entries in the noisy distance matrix may not be Euclidean distance like for example when the entries are geodesic distance on the manifold M. Since in these cases the entries to the noisy distance matrix are not Euclidean distances, the approach via distance preserving Euclidean embedding won't work.

3. Large dimension of the embedding space. Observe that the dimension d of the Euclidean space we can get via the above distance preserving embedding can be as large as d = Ω(#P). This will make time complexity of the manifold reconstruction algorithms given in [CDR05, BGO09] exponential in #P, since both these approaches compute Voronoi diagrams in the ambient space using the whole point sample or a subset of the sample.

4. Problems with tangential Delaunay complex. Once we have the distance preserving embedding of the point sample P we can use the tangential Delaunay complex (TDC) for reconstruction [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF]. As already mentioned, the dimension of the Euclidean space obtained from a distance preserving embedding of P can be as large as Ω(#P). Note that TDC construction will compute the following structures:

(a) The approximate tangent space at each point of the point sample. This if the dimension of the embedding space is Ω(#P) will incur an Ω(#P) time complexity.

(b) The TDC construction will need to compute Delaunay triangulations restricted to the approximate tangent spaces. So the problem of using complicated and highly structured data structure still stays.

(c) In the TDC construction one needs to compute (m+1)-dimensional simplices corresponding to each inconsistent simplex. See the definition of inconsistent simplex from [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

The time complexity for constructing each of these simplices will be Ω(#P) if the dimension of the Euclidean space obtained from a distance preserving embedding is Ω(#P).

As with the other reconstruction algorithms [CDR05, BGO09], the TDC won't be able to handle noisy distance matrix as input or when the entries to the distance matrix are geodesic distances on the manifold M.

We will now give the proof of Properties P1, P2, and P3.

Lemma 32 Let L be an -sample of M with < 1 9 (1sin θ 0 ) 2 rch(M), and let : L → [0, ∞) be a weight assignment with < 1 2 . Let σ ∈ K (L). 3. Using the facts that L is 2 -sparse and < 1 2 , we can show ∀ p ∈ σ,

d(p, N (σ m )) ≥ 3 16 . ( 15
)
To reach a contradiction let p be a vertex of σ m such that Vor (σ) ∩ T p M = ∅ and q be a vertex of σ m with Vor (σ) ∩ T q M = ∅. Using the bound on and part 1 of this lemma, we can show, for all x ∈ σ m , that sin(aff σ m , T x M) ≤ sin

θ def = 8 Γ m 0 rch(M) < 1 2 and #(N (σ) ∩ T x M) = 1.
Observe that C (σ m ) is orthogonal projection of c onto aff(σ m ). Let c denotes the intersection of N (σ m ) and T q M. Note that, by construction, the line segment cc ∈ N (σ m ).

From part (1) of this lemma, we have for all x ∈ σ m ,

x -C (σ m ) ≤ x -c ≤ 4 . ( 16
) Therefore c -c ≤ c -C (σ m ) + C (σ m ) -c ≤ p -c sin θ + q -C (σ m ) tan θ ≤ 4 sin θ 1 + 1 cos θ < 12 sin θ Using the facts that ≤ Γ m 0 sin θ 0 2 9
rch(M) and d(p, N (σ m )) ≥ 3 16 , see Equation (15), we can show that the line segment cc ∈ K(p). So, Vor(σ m ) ∩ T p M = ∅ implies there exists a σ m+1 ∈ K (L) with σ m < σ m+1 . We have reached a contradiction via part 2 of this lemma.

A.2 Proof of Theorem 19

Homemorphism and geometric guarantees given in Theorem 19 is a direct consequence of the following lemma7 from [START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

Lemma 33 Let L ⊂ M be an (λ, 2λ)-net of M, and : L → [0, ∞) be a weight assignment satisfying the following properties:

1.

≤ α 0 . There exists λ 0 > 0 that depends only on α 0 , Γ 0 and m such that for λ ≤ λ 0 , Del (P, T M) is homeomorphic to and a close geometric approximation of M.

Dimension of maximal simplices in

Rest of this section is devoted to the proof of Wit (L, W ) = Del (L, T M).

The proof goes through multiple stages.

Note that λ is sufficiently small such that ρ 3λ 8 -2mρ ≤ sin θ 0 (18) and sin

θ def = 16λ Γ m 0 rch(M) < √ 3 2 . ( 19
)
We will now generate sequence of simplices

σ k < σ k+1 < • • • < σ m < σ m+1
and points c k , c k+1 , . . . , c m , c m+1 by walking on Vor (σ k ) satisfying the following properties:

Prop-1. For all σ k+i , there exists c k+i ∈ Vor (σ k+i ) such that

d(c k+i , T p M) ≤ ρ and p -c k+i ≥ p -c k -2iρ.
From Eq. ( 18), this implies σ k+i ∈ K θ 0 (L).

Prop-2. For all σ k+i , we have Vor (σ k+i ) ∩ T p M = ∅.

Note that once we have shown that such sequence of simplices exists, then we would have reached a contradiction from Lemma 32 (2).

We will now show how to generate the above sequence of simplices.

Base case. From Eq. (18), it is easy to see that σ k and c k satisfy Prop-1 and Prop-2.

Inductive step. Wlog lets assume that we have generated till σ k+i , satisfying properties Prop-1 and Prop-2, and we also assume k + i ≤ m. Since σ k+i ∈ K (L), we can show, using Lemma 32 (1), that sin ∠(N p M, N (σ k+i )) ≤ sin θ.

From Prop-1, we have pc k+i ≥ pc k -2iρ and d(c k+i , T p M) ≤ ρ. Therefore, from Eq. 19, there exists ck+i ∈ T p M ∩ N (σ k+i ) such that

c k+i -ck+i ≤ ρ cos θ ≤ 2ρ.
As Vor (σ k+i ) ∩ T p M = ∅ hence there exists c k+i+1 ∈ [c k+i , ck+i ) such that c k+i+1 ∈ Vor (σ k+i+1 ) with σ k+i < σ k+i+1 . Note that, as in the base case, we can show that d(c k+i+1 , T p M) ≤ ρ and pc k+i+1 ≤ pc k -2(i + 1)ρ .

q. Since < 1 2 , x ∈ pq. Using the facts that d(x, p ) = d(x, q ), pq ≥ λ and (q) < p-q 2 (as < 1/2), we get

p -x = p -q 2 1 + (p) 2 -(q) 2 p -q 2 ≥ p -q 2 1 - (q) 2 p -q 2 ≥ 3λ 8 (17)
The bound on d(p, C (σ k ) ) follows from the fact that d(p, x) ≥ d(p, C (σ k )).

We will now prove the power protection of simplices in Del (L, T M) on the manifold M. Let σ ∈ Del (L, T M) be a k-simplex, with k ≤ m, incident to p. From Prop. (e), ∃ c ∈ Vor ξ (σ ) such that ∀ x ∈ σ and ∀ y ∈ L \ σ yc 2ξ(y ≤ rch(M) 2 11 , we get

) 2 > x -c 2 -ξ(x ) 2 + δ 2 m + 1 . Which,
p -ĉ ≤ p -c + c -ĉ ≤ 8 + 1 16 λ < rch(M) 4 . (21)
Therefore, using sin ∠(aff(σ), T p M) ≤ Using the above bound on sin ∠(aff σ, T ĉM), the fact that cĉ ≤ 2 7 λ 2 rch(M) < rch(M)

25

(Eq. ( 20)) and Lemma 48, we get

c -c ≤ 4 c -ĉ ≤ 2 9 λ 2 rch(M) def = Cλ 2 rch(M) ≤ λ 4 .
Let q ∈ L \ σ and p ∈ σ. We will consider the following two cases:

Case-1. qc 2 > pc 2 + 2(2λ) 2 . Using the facts that (q) ≤ 4α 0 λ (from part 2(a) of Lemma 8) and α 0 < 1 2 , we have

q -c 2 -(q) 2 -( p -c 2 -(p) 2 ) > 8λ 2 -(q) 2 + (p) 2 > 8λ 2 -(q) 2 > 4λ 2
Let w ∈ W be such that cw ≤ ε. For all q ∈ L \ σ k and p ∈ σ k we have

p -w 2 -(p) 2 ≤ ( p -c + c -w ) 2 -(p) 2 = p -c 2 -(p) 2 + c -w ( c -w + 2 p -c ) ≤ p -c 2 -(p) 2 + 9ελ < q -c 2 -(q) 2 -(δ 2 1 -9ελ) ≤ q -w 2 -(q) 2 + β -(δ 2 1 -9ελ) (22)
Where β = wc ( wc + 2 qw ).

We have to consider the following two case:

1. If qw 2 > pw 2 + 4λ 2 . Using the fact that (q) < 2λ, from Lemma 8 (1), we get

q -w 2 -(q) 2 > p -w 2 + 4λ 2 -(q) 2 > p -w 2 ≥ p -w 2 -(p) 2 2. If q -w 2 ≤ p -w 2 + 4λ 2 . This implies q -w ≤ p -w + 2λ ≤ p -c + c -w + 2λ ≤ 7λ.
Now, using Eq. ( 22) and the facts that qw = 7λ and cw ≤ ε ≤ λ, we get

p -w 2 -(p) 2 ≤ q -w 2 -(q) 2 + β -(δ 2 1 -9ελ) ≤ q -w 2 -(q) 2 -(δ 2 1 -24ελ) as β ≤ 15ελ < q -w 2 -(q) 2
The last inequality follows from the fact that

λ < δ 2 0 rch(M) B m and ε < λ 24 δ 2 0 m - Bλ rch(M)
.

This implis w is a witness of σ k . As this is true for all σ k ∈ Del (L, T M), we get Del (L, T M) ⊆ Wit (L, W ).

B Proof of Lemma 20 B.1 Outline of the proof

We will use a variant of Pumping equation, Lemma 41, from [CDE + 00] and bound on the height of slivers, Lemma 42, from [START_REF] Boissonnat | Delaunay stability via perturbations[END_REF]. Let : L → [0, ∞) be a weight assignment with ≤ α0 , and σ ⊂ L be a Γ 0 -sliver incident to the point p ∈ L. As in Lemma 20, 1 is an ewp of such that σ ∈ K (L). To prove Lemma 20, we distinguish the following two cases depending on the point whose weight is changed when replacing by 1 :

Case 1. The point whose weight is changed is p. Lemma 43 takes care of this case and states that

(p) 2 ∈ J (p, σ) = F (p, σ) - η 1 2 -δ 2 0 λ 2 , F (p, σ) + η 1 2 , for some η 1 ≤ η -2δ 2 0 λ 2 . Case 2.
|F (p, σ) -F 1 (p, σ)| = O δ 2 0 λ 2 Γ m 0 One way to proving this is by proving max R (σ p ) 2 -R 1 (p, σ) 2 , d(p, N (σ p )) 2 -d(p, N 1 (p, σ)) 2 = O δ 2 0 λ 2 Γ m 0 ,
and this will be done in Lemma 46 using Lemma 44 and Corollary 45,

B.2 Details of the proof

For the rest of this section we will assume the following hypothesis

Hypothesis 40 L ⊂ M is a (λ, 2λ)-net of M with λ < 1 18 (1 -sin θ 0 ) 2 rch(M).
For a simplex σ and a vertex p ∈ σ, excentricity H (p, σ) of σ with respect to p is the signed distance of C (σ) from aff(σ p ), i.e., H (p, σ) is positive if C (σ) and p lie on the same side of aff(σ p ) and negative if they lie on different sides of aff(σ p ).

The following lemma is a variant of the pumping equation from [CDE + 00, BG14, CDR05].

Lemma 41 (Pumping equation, see Figure 13) We will assume that the weight of p is varying and the weight of the other vertices of σ are fixed. Then

2D(p, σ) H (p, σ) = F (p, σ) -(p) 2 .
The above "pumping equation" will be used to bound the length of the forbidden intervals.

The following result is from [START_REF] Boissonnat | Delaunay stability via perturbations[END_REF].

Lemma 42 (Sliver altitude bound) If a (k + 1)-simplex τ is a Γ 0 -sliver, then for any vertex p of σ we have

D(p, σ) < 2Γ 0 ∆(σ) 2 L(σ) .
A variant of the following result can be found in [CDR05, Lem. 10] and [BG14, Lem. 4.14]. We have included the proof for completeness. Lemma 43 (Case 1) Let : L → [0, ∞] be a weight assignment with ≤ α0 , and σ ⊂ L be a Γ 0 -sliver incident to the point p ∈ L. Let 1 be a ewp of satisfying the following conditions (q) = 1 (q), ∀ q ∈ σ \ p, and σ ∈ K 1 (L).

If λ is sufficiently small then

(p) 2 ∈ F (p, σ) - η 1 2 -δ 2 0 λ 2 , F (p, σ) - η 1 2 where η 1 def = 2 14 Γ 0 λ 2 . Proof Since |H 1 (p, σ)| ≤ C 1 (σ) -p , we have from Lemma 32 (1) |H 1 (p, σ)| ≤ C 1 (σ) -p < 8λ.
Since L is λ-sparse, we have from Lemma 32 (2)

λ ≤ L(σ) ≤ ∆(σ) < 16λ
From Lemma 42, we have

D(p, σ) < 2Γ 0 ∆(σ) 2 L(σ) < 2 9 Γ 0 λ.
Therefore, using Lemma 41, we have

F 1 (p, σ) -2D(p, σ)|H 1 (p, σ)| ≤ 1 (p) 2 ≤ F 1 (p, σ) + 2D(p, σ)|H 1 (p, σ)| F 1 (p, σ) -2 13 Γ 0 λ 2 ≤ 1 (p) 2 ≤ F 1 (p, σ) + 2 13 Γ 0 λ 2
The result now follows from the facts that • F 1 (p, σ) = F (p, σ) as, from the definition, F 1 (p, σ) (and F (p, σ)) depends only on the weights of the vertices in σ p and for all q ∈ σ \ p, (q) = 1 (q).

N ξ 2 (σ p ) σ p N ξ 1 (σ p ) d(N ξ 1 (σ p ), N ω 2 (σ p )) q p σ
• 1 (p) 2 ∈ [ (p) 2 , (p) 2 + δ 2 0 λ 2 ].
The following lemma show the stability of weighted centers of well shaped simplices under small perturbations of weight assignments. The proof is in the same vein as the proof of [BDG13b, Lem. 4.1], and will use singular values of matrices associated with the simplices.

Lemma 44 Let σ be a simplex with L(σ) ≥ λ and Υ(σ) > 0, and ξ i : σ → [0, ∞), with i ∈ {1, 2}, be weights assignments, with ξi ≤ α 0 , satisfy the following properties: ∃ p ∈ σ such that 1. ∀ q ∈ σ \ p, ξ 1 (q) = ξ 2 (q), and

2. |ξ 1 (p) 2 -ξ 2 (p) 2 | ≤ δ 2 0 λ 2 . Then C ξ 1 (σ) -C ξ 2 (σ) ≤ δ 2 0 λ 2Υ(σ) ,
and for r ∈ σ, we have

d(r, N ξ 1 (σ)) -d(r, N ξ 2 (σ)) ≤ δ 2 0 λ 2Υ(σ)

Proof

Let σ = [p 0 . . . p k ], and wlog let p = p 0 and σ ⊂ R k . The ortho-radius of σ satisfy the following system of k-linear equations:

(p j -p 0 ) T C ξ i (σ) = 1 2 ( p j 2 -ξ i (p j ) 2 -p 0 2 + ξ i (p 0 ) 2 )
Rewriting the above system of equation we get

(p j -p 0 ) T (C ξ 2 (σ) -C ξ 1 (σ)) = 1 2 (ξ 1 (p j ) 2 -ξ 2 (p j ) 2 + ξ 2 (p 0 ) 2 -ξ 1 (p 0 ) 2 ) = 1 2 (ξ 1 (p j ) 2 -ξ 2 (p j ) 2 ) as p = p 0
Letting P be a k × k matrix whose j th column is (p jp 0 ), we have

P T (C ξ 2 (σ) -C ξ 1 (σ)) = x ξ 2 where x ξ = (ξ 1 (p 1 ) 2 -ξ 2 (p 1 ) 2 , . . . , ξ 1 (p k ) 2 -ξ 2 (p k ) 2 ) T . Therefore C ξ 2 (σ) -C ξ 1 (σ) = 1 2 P -T x ξ ≤ 1 2 P -1 x ξ ≤ s 1 (P -1 ) × δ 2 0 λ 2 2 as s 1 (P -1 ) = P -1 and x ξ ≤ δ 2 0 λ 2 = s k (P ) -1 × δ 2 0 λ 2 2 as s 1 (P -1 ) = s k (P ) -1 , Lemma 2 ≤ δ 2 0 λ 2 2 √ kΥ(σ)∆(σ) as s k (P ) ≥ √ kΥ(σ)∆(σ), Lemma 3 ≤ δ 2 0 λ 2Υ(σ) as ∆(σ) λ ≥ 1
The bound on d(r, N ξ 1 (σ))d(r, N ξ 2 (σ)) follows directly from the part 1 of the lemma and the fact that d(r, N ξ 1 (σ))d(r, N ξ 2 (σ)) ≤ C ξ 1 (σ) -C ξ 2 (σ) .

Corollary 45 Let : L → [0, ∞] be a weight assignment with ˜ ≤ α0 , and σ ⊂ L be a jdimensional Γ 0 -sliver with p ∈ σ and j ≤ m + 1. In addition, we assume

δ 2 0 Γ m 0 ≤ 2.
If 1 be an ewp of satisfying the following: ∃ q ∈ σ p such that ∀ x ∈ L \ {q}, (x) = 1 (x) and σ ∈ K 1 (L, M). Then Since σ is a Γ 0 -sliver, j ≥ 2 (see Remark 5). As j ≥ 2, there exists r ∈ σ p \ q. This implies (r) = 1 (r).

Using the facts that 1 (r) = (r), C 1 (σ p )r ≤ 8λ (from Lemma 32 (1)) and C (σ p ) -C 1 (σ p ) ≤ δ 2 0 λ 2Γ m 0 (from Lemma 44 and the fact that Υ(σ p ) ≥ Γ j-1 0 ≥ Γ m 0 ), we get

R (σ p ) 2 = C (σ p ) -r 2 -(r) 2 ≤ ( C 1 (σ p ) -r + C (σ p ) -C 1 (σ p ) ) 2 -1 (r) 2 ≤ R 1 (σ p ) 2 + 2 C 1 (σ p ) -r + C (σ p ) -C 1 (σ p ) C (σ p ) -C 1 (σ p ) ≤ R 1 (σ p ) 2 + 16λ + δ 2 0 λ 2Γ m 0 δ 2 0 λ 2Γ m 0 ≤ R 1 (σ p ) 2 + 17δ 2 0 λ 2 2Γ m 0 and R (σ p ) 2 = C (σ p ) -r 2 -(r) 2 ≥ ( C 1 (σ p ) -r -C (σ p ) -C 1 (σ p ) ) 2 -1 (r) 2 ≥ R 1 (σ p ) 2 -2 C 1 (σ p ) -r -C (σ p ) -C 1 (σ p ) C (σ p ) -C 1 (σ p ) ≥ R 1 (σ p ) 2 -2 C 1 (σ p ) -r C (σ p ) -C 1 (σ p ) ≥ R 1 (σ p ) 2 - 8δ 2 0 Γ m 0 λ 2
Lemma 46 (Case 2) Assuming the same conditions on , 1 , p, q and σ as in Corollary 45, we get (p) 2 ∈ F (p, σ) -η 2 , F (p, σ) + η 2 .

projection onto T ĉM induces, in some neighbourhood V of ĉ, a diffeomorphism between M ∩ V , and T ĉM ∩ V (Lemma 51). We use T ĉM as an intermediary in this calculation (Lemma 50). Then, since N intersects T ĉM near ĉ (Lemma 49), we can argue that it must also intersect M because the established diffeomorphisms make a correspondence between points along segments parallel to N.

The final bounds are established in Lemma 52, from which Lemma 48 follows by a direct calculation, together with the following observations: If dim N = dim N ĉM, then ∠(N ĉM, N) = ∠(N, N ĉM), and if dim N ≥ dim N ĉM, then there is an affine subspace N ⊂ N, such that dim N = dim N ĉM, and ∠(N ĉM, N) = ∠(N ĉM, N). Indeed, we may take N to be the orthogonal projection of N ĉM into N.

We now bound distances to the intersection of N and T ĉM.

Proof

For a point x ∈ N ∩ T ĉM, let u x denote the unit vector from c to x, and let v x ∈ N ĉM be the unit vector that makes the smallest angle with u x . Let H denote the hyperplane passing through ĉ and orthogonal to v The following lemma is a direct consequence of the definition of the angle between two affine spaces.

Lemma 50 Let p be a point in M and let T p M denote a m-dimensional flat passing through p with ∠(T p M, T p M) ≤ α < π 2 . If f α p denote the orthogonal projection of T p M onto T p M, then 1. The map f α p is bijective.

Proof

Let Tĉ M denote the orthogonal complement of N in R d passing through ĉ. Note that ∠(T ĉM, T ĉM) = ∠(N, N ĉM).

Let x ∈ N ∩ T ĉM and x = f α ĉ (x). Then from Lemma 49, we have

xĉ ≤ xĉ ≤ 1 + 1 cos α ρ and xx ≤ xĉ sin α ≤ (sin α + tan α) ρ .

Using the fact that ρ ≤ r(α) cos α cos α 1 1+cos α

, we have

xĉ ≤ 1 + 1 cos α ρ ≤ r(α) cos α 1 .

Therefore, from Lemma 49, there exists an x ∈ B M (p, r(α)) such that g α p (x) = x and

xx ≤ xĉ tan α 1 ≤ 1 + 1 cos α tan α 1 ρ.

Therefore cx ≤ cx + xx + xx ≤ ρ cos α + 1 + 1 cos α (sin α + tan α 1 ) ρ = 1 cos α + 1 + 1 cos α (sin α + tan α 1 ) ρ.

Note that the line segment cx ∈ N.

This completes the proof of Lemma 48.

Figure 2 :

 2 Figure 2: The figure shows the weighted Voronoi diagram of weighted points, denoted by circles with centered at the points and radii equal to the weight of the points, in the plane.

Figure 3 :

 3 Figure 3: The figure shows the medial axis O C , drawn in black, of the blue curve C. For a given compact submanifold M of R d , the medial axis O M of M is defined as the closure of the set of points in R d that have more than one closest points in M. The reach of M is defined as rch(M) = inf x∈M d(x, O M ).

  c

Figure 7 :

 7 Figure 7: The figure shows existence of a point on a Voronoi face that is far from other Voronoi faces. The above result in the unweighted case implies that if Voronoi vertices are protected then any Voronoi face contains a point that is far from any of the other Voronoi faces. See Figure 7.Lemma 11 also implies that if aff P = R d and if all the d-simplices in Del (P) are δ 2power protected then all the simplices, not on the boundary of Del (P), are also power protected. Another interesting aspect of this result is the fact that the decay in power protection to lower dimensional simplices goes down linearly with the dimension of the ambient space.To prove Lemma 11 we need the following lemma on power protection.

Figure 10 :

 10 Figure 10: Diagram showing connection between protection and lifting.

Theorem 19

 19 Let M be a m-dimensional submanifold of R d , W ⊂ M an ε-sample of M, L ⊂ W a λ-net of W with ε ≤ λ, and : L → [0, ∞) a stable weight assignment with ≤ α0 . If

Lemma 22

 22 If λ ≤ rch(M) 512 , then for any p ∈ L, #(B(p, 16λ) ∩ L) ≤ 66 m def = N 1 . Proof of Lemma 21 Write S(p i ) for the set of candidate simplices of p i . We have #S(p i ) ≤ N

1.

  (Property P1) Assume dim σ = k ≤ m and Υ(σ) ≥ Γ k 0 . Additionally, if < rch(M) 8 then for all vertices p of σ we have sin ∠(aff(σ), T p M) ≤ 8 Γ m 0 rch(M) . 2. (Property P2) If K (L) does not contain any Γ 0 -slivers of dimension ≤ m + 1 and dimension of maximal simplices in K (L) is at most m. 3. (Property P3) Assume hypothesis in part (4) of this lemma. Additionally, if L is 2 -sparse and ≤ Γ m 0 sin θ 0 2 9 rch(M), then for all m-simplex σ m ∈ Del (L, T M) and ∀ p ∈ σ, we have Vor (σ m ) ∩ T p M = ∅.Proof 1. Follows directly from Corollary 9 and Lemma 32 (2). 2. Using part 1 and exactly the proof idea used in the proof of[START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF] Lem. 4.9], we can show that all m + 1-simplices in K (L) are either Γ 0 -bad or have thickness 12 Γ m 0 rch(M) . Using the bound on , we can complete the proof of part 4.

Figure 12 :

 12 Figure 12: Diagram for the Lemma 32 (3).

  Del (L, T M) is equal to m 3. All the simplices in Del (L, T M) are Γ 0 -good. 4. For all σ = [p 0 , . . . , p k ] ∈ Del (L, T M) and ∀ i ∈ {0, . . . , k}, Vor (p i ) ∩ T p i M = ∅.

  from the definition of ξ and Prop. (a), implies ∀ x ∈ σ and ∀ y ∈ L \ σ yc 2 -(y) 2 > xc 2 -(x) 2 + δ 2 m + 1 , and c ∈ Vor (σ). Let ĉ be the point closest to c on M and c denotes the point closest to c in M ∩ N (σ). Using the facts that pc ≤ 8λ (from Lemma 29 (1)) and cĉ ≤ 2 7 λ 2 rch(M)

0

  rch(M) (from Lemma 32 (1)) and sin ∠(T p M, T ĉM) < 6 p-ĉ rch(M) (from Lemma 7 (3) and pĉ < rch(M) 4 ), we have sin ∠(aff σ, T ĉM) ≤ sin ∠(aff σ, T p M) + sin ∠(T p M, T ĉM)

Figure 13 :

 13 Figure 13: Diagram for the Lemma 41.

Figure 14 :

 14 Figure 14: Diagram for the Lemma 44.

Proof

  d(p, N (σ p )) 2d(p, N 1 (σ p )) 2 , R (σ p ) 2 -R 1 (σ p )Using the fact that L is an (λ, 2λ)-net of M, and from Lemmas 32 (1) and (2) we haved(p, N 1 (σ p )) ≤ C 1 (σ p )q + pq ≤ 24λFrom Lemma 44 we haved(p, N (σ p )) + d(p, N 1 (σ p )) ≤ 2d(p, N 1 (σ p )) + δ 2 0 λ 2Υ(σ p ) ≤ 2d(p, N 1 (σ p )) + δ 2 0 λ 2Γ m 0 as σ is a Γ 0 -sliver ≤ 49λFrom Lemma 44 and the fact that d(p, N (σ p )) + d(p, N 1 (σ p )) ≤ 49λ, we have d(p, N (σ p )) 2d(p, N 1 (σ p ))

Lemma 49 Figure 16 :

 4916 Figure 16: Diagram for the Lemma 49.

  x . Since cĉ ≤ ρ, dist(c, H) ≤ ρ. Therefore, cx ≤ dist(c, H) cos α and ĉx ≤ ĉc + cx ≤ 1 + 1 cos α ρ

2.

  For r > 0, f α p (B p (r)) ⊇ B p (r cos α) where B p (r) = B(p, r)∩T p M and B p (r) = B(p, r)∩ T p M. Lemma 51 Let p be a point in M, and let T p M be a m-dimensional affine flat passing through p with ∠(T p M, T p M) ≤ α. There exists an r(α) satisfying : 7 r(α) rch(M) + sin α < 1 and r(α) ≤ rch(M) 10such that the orthogonal projection map, g α p , of B M (p, r(α)) = B(p, r(α)) ∩ M into T p M satisfy the following conditions:1. g α p is a diffeomorphism. 2. g α p (B M (p, r(α))) ⊇ B p (r(α) cos α 1 ) where sin α 1 = r(α) 2rch(M) + sin α. 3. Let x ∈ g α p (B M (p, r(α))), then x -(g α p ) -1 (x) ≤ px tan α 1 . Proof 1. Let π TpM denote the orthogonal projection of R d onto T p M.The derivative of this map, Dπ TpM , has a kernel of dimension (dm) that is parallel to the orthogonal complement ofT p M in R d .We will first show that Dg α p is nonsingular for all x ∈ B M (p, r(α)). From Lemma 7 (3) and the fact that ∠(T p M, T p M) ≤ α, we havesin ∠( T p M, T x M) ≤ sin ∠(T x M, T p M) + sin ∠(T p M, T p M) ≤ 6r(α) rch(M) + sin α < 1Since g α p is the restriction of π TpM to B M (p, r(α)), the above inequality implies that Dg α p is nonsingular. Therefore, g α p is a local diffeomorphism. Let x, y ∈ B M (p, r(α)). From Lemma 7 part (1) and (3), we havesin ∠([x, y], T p M) ≤ sin ∠([x, y], T x M) + sin ∠(T x M, T p M) + sin ∠( T p , T p M) α p (x) = g α p (y). Since g αp is nonsingular and injective on B M (p, r(α)), it is a diffeomorphism onto its image. 2. Notice that, for x ∈ B M (p, r(α)), the angle α 1 is a bound on the angle between px and Tp M. The inclusion g α p (B M (p, r(α))) ⊇ B p (r(α) cos α 1 ) follows since xg α P (x) is orthogonal to Tp M. 3. Follows similarly. Lemma 52 Let c, ĉ be points in R d such that the projection of c onto M is ĉ and cĉ ≤ ρ. Let N be a dm dimensional affine flat passing through c such that ∠(N, N ĉM) ≤ α. If ρ ≤ r(α) cos α cos α 1 1 + cos α Then there exists an x ∈ N ∩ M such that cα + sin α 1 ) ρ .

  outside the forbidden intervals of the candidate simplices of p i , i.e., (p i ) 2 ∈

σ∈S(p i )

  The point whose weight is changed is not p.Since J (σ, p) ⊂ I (σ, p), Lemma 20 is proved.The proof of Case 1 is in the same vein as the proofs of [CDR05, Lem. 10] and [BG14, Lem. 4.14].The main technical ingredient in completing the proof of Case 2 is in showing that

		Lemma 20 takes care of this case and states
	that	(p) 2 ∈ I (σ, p) = F (p, σ) -	η 2	, F (p, σ) +	η 2	.

Boissonnat, Guibas and Oudot [BGO09, Lem. 4.4] proved a more general result bounding the distance between x and its (k + 1)-nearest weighted neighbor for all k ≤ d. In Lemma 8 (2) we only stated the special case when k ∈ {0, 1}.

Note that poly(k) denotes a polynomial in k of degree O(1).

For a simplicial complex K, the m-skeleton of K is set of simplices of K of dimension at most m.

Covariance matrix Cov(V ) of the set of vectors V = {v1, . . . , v l } in R d is defined as Cov(V ) = l i=1 (vi1, vi2, . . . , v id ) T (vi1, vi2, . . . , v id ),where vi = (vi1, vi2, . . . , v id ). Observe that Cov(V ) is a d × d matrix.

Note that this lemma is a special case of the result proved in[START_REF] Boissonnat | Manifold Reconstruction Using Tangential Delaunay Complexes[END_REF].

Let p and q be distinct vertices of σ k , and let x be an orthogonal projection of C (σ k ) on the line through p and

Acknowledgements

This research has been partially supported by the 7th Framework Programme for Research of the European Commission, under FET-Open grant number 255827 (CGL Computational Geometry Learning). Partial support has also been provided by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).

Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany supported by the Indo-German Max Planck Center for Computer Science (IMPECS). Part of this work was also done when Arijit Ghosh was a Visiting Scientist at Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India.

* This research has been partially supported by the 7th Framework Programme for Research of the European Commission, under FET-Open grant number 255827 (CGL Computational Geometry Learning) and by the European Research Council (ERC) under the European Union's Seventh Framework Programme (FP/2007-2013) ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). † Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany supported by the Indo-German Max Planck Center for Computer Science (IMPECS). Part of this work was also done when

A Proof of Theorem 19

This section is devoted to the proof of Theorem 19. When we talk about properties P1, P2 and P3 in this section, we are actually referring to properties introduced in Section 4.

Before we go into the detailed calculations, we want to make this small and obvious observation that directly follows from triangle inequality.

Observation 27 If W is an ε-sample of M and L a λ-net of W with ε ≤ λ, then L is a (λ, 2λ)-net of M.

A.1 Proof of properties P1, P2 and P3

We will use the following structural result from [START_REF] Boissonnat | Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes[END_REF].

Lemma 28 Let θ ∈ [0, π 2 ), and P ⊂ M be an -sample of M with < 1 9 (1sin θ) 2 rch(M). For any weight assignment : L → [0, ∞) with < 1 2 , for any p ∈ P and x ∈ Vor (p) ∩ K θ (p), we have px ≤ 3 1sin θ .

Following lemma is a direct consequence of Lemma 28.

Lemma 29 Let L be an -sample of M with < 1 9 (1sin θ 0 ) 2 rch(M), and let : L → [0, ∞) be a weight assignment with < 1 2 . Let σ ∈ K (L). 1. Let p be a vertex of σ with Vor (p) ∩ K θ 0 (p) = ∅. For all vertices q of σ and x ∈ Vor (p) ∩ K θ 0 (p), we have xq < 4 . This implies for all the vertices q of σ, q -C (σ) < 4 .

The bound on q -C (σ) follows from the fact that qx ≥ q -C (σ) .

2. The bound on ∆(σ) follows from part (1) and triangle inequality.

The following corollary about witness complex is from [dS08, Cor. 7.6].

Corollary 30 For any subsets W, L ⊆ R d with L finite, for any : L → [0, ∞), we have Wit (L, W ) ⊆ Del (L). Moreover, for any simplex σ of Wit (L, W ), the weighted Voronoi face of σ intersects the convex hull of the -witnesses (among the points of W ) of σ and of its subsimplices.

Following result is a direct consequence of Lemma 8 (2).

4

, and : L → [0, ∞) be a weight assignment with < 1 2 . 1. For all pq ∈ Wit (L, W ), pq ≤ (4 + 10 )(λ + ε).

2. Let σ ∈ Wit (L, W ). The distance between any vertex p of σ and any witness w of τ ≤ σ is at most (5 + 12 )(λ + ε).

Proof 1. First observe that L is a (λ + ε)-sample of M via triangle inequality. Let w ∈ W be a -witness for the edge pq ∈ Wit (L, W ), and without loss of generality assume that p is closest neighbor of w in terms of the weighted distance. Then from Lemma 8 (2), we have wp ≤ (1 + 2 )(λ + ε) and wq ≤ (3 + 8 )(λ + ε). Therefore again from triangle inequality we get pq ≤ (4 + 10 )(λ + ε).

2. Let p be a vertex of σ, and let q ∈ τ is the vertex closest to w in terms of the weighted distance. Then from part (1), we have pq ≤ (4 + 10 )(λ + ε). From Lemma 8 (2), we have wq ≤ (1 + 2 )(λ + ε). From triangle inequality, we have pw ≤ (5 + 12 )(λ + ε).

Stage (1). We will first show, in Lemma 34, that no Γ 0 -slivers of dimension ≤ m + 1 in K (L) implies Wit (L, W ) ⊆ Del (L, T M).

Stage (2).

In Lemma 35 we prove that if : L → [0, ∞) is a stable weight assignment then for all m-simplices σ ∈ Del (L, T M) and p ∈ σ, σ will be δ 2 -power protected on T p M.

Stage (3). Let Del (L, T M) does not contain any Γ 0 -slivers and for all m-simplex σ m ∈ Del (L, T M) and ∀ p ∈ σ m , σ m is δ 2 -power protected on T p M. Then for all σ ∈ Del (L, T M), σ will be Ω δ 2 m+1 -power protected on M. See, Lemma 38.

Stage (4). Finally in Lemma 39, we will show that conditions in Stage (3) implies

To see that this will complete the proof, observe that being stable weight assignment implies K (L) contains no Γ 0 -slivers of dimension ≤ m + 1. This would imply dimension of maximal simplices in K (L) is at most m. Once we have this, simply going through Stage (1) till Stage (4) will give us the result.

Proof

Note that L is a (λ, 2λ)-net of M. To reach a contradiction, let σ k be a k-simplex in Wit (L, W ) and p be a vertex of σ such that Vor (σ k ) ∩ T p M = ∅.

Let w ∈ W be a -witness of a subface of σ k . From Lemma 31, and the facts that < 1 2 and ε ≤ λ, we have pw ≤ (5 + 12 )(λ + ε) < 22λ.

From Lemma 7, we have

From Corollary 30, there exist c k ∈ Vor (σ k ) that lies in the convex hull of the -witness of σ (in W ) and its subfaces. This implies,

The following lemma connects power protection of m-dimensional simplices in Del (T M) with stability of .

and let : L → [0, ∞), with ≤ α0 , be a stable weight assignment. Then all the m-simplices σ ∈ Del (L, T M) are δ 2 -power protected on T p M for all p ∈ σ, where δ = δ 0 λ.

Proof Note that L is (λ, 2λ)-net of M. For all m-simplices σ in Del (L, T M), we have Vor (σ)∩ T p M = ∅ for all p ∈ σ.

To reach a contradiction, lets assume that σ ∈ Del (L, T M) to be not δ 2 -power protected on

Since L is λ-sparse, δ = δ 0 λ and α2 0 + δ 2 0 ≤ α 2 0 , we have ξ ≤ α 0 . It is easy to see ξ is an ewp of , and the (m + 1)-dimensional simplex τ = q * σ ∈ K ξ (L). As is stable weight assignment and ξ is an ewp of , we get a contradiction from Lemma 32 (2) and the fact that

rch(M).

We will need the following result due to Boissonnat and Ghosh [BGO09, Lem 2.2].

Lemma 36 Let L ⊂ R d be a point set, : L → [0, ∞) be a weight distribution, and H ⊆ R d be a k-dimensional flat. Also, let L denotes the projection of the point set L onto H, and p denotes the projection of p ∈ L onto H. For all p ∈ L, we have

where ξ : L → [0, ∞) with ξ(q ) 2 = (q) 2qq 2 + max Following lemma connects power protection of m-simplices on the tangent space to that on the manifold.

Lemma 38 Let L ⊂ M be a (λ, 2λ)-net of M, and δ = δ 0 λ with δ 0 < 1. Let : L → [0, ∞) be a weight assignment with < 1 2 and satisfying the following properties: 1. Del (P, T M) does not contain any Γ 0 -sliver, and

then all σ ∈ Del (L, T M) are δ 2 1 -power protected on M where

Proof

Let p be a point in L, and L denotes the projection of the point sample L onto T p M. For a point x ∈ L, x is the projection of x onto T p M and vise versa, and similarly, let σ = [p 0 , . . . , p k ] be a simplex with p i 's in L then σ denotes the simplex [p 0 , . . . , p k ] and vise versa. Note that p = p.

The weight assignment ξ : L → [0, ∞) is defined in the following way:

For σ ⊆ L , Vor ξ (σ ) denotes the Voronoi cell in T p M and not in R d . From Lemmas 36 and 29 (1) we have:

From Prop. (a) and the definition of tangential complex, if σ ∈ st(p; Del ξp (L )) then σ ∈ Del (L, T M). Since all the m-simplices of Del (L, T M) are δ 2 -power protected on the tangent space of the vertices (Hyp. 4), therefore, from the definition of ξ :→ [0, ∞), all the m-simplices σ incident to p in Del ξ (L ) are also δ 2 -power protected on T p M, i.e., there exists x ∈ Vor ξp (σ ) such that for all q ∈ σ and r Prop. (e) Let σ ∈ Del ξ (L ) be a j-simplex incident, with p ∈ σ , then σ is δ 2 m-j+1 -power protected. Note that Prop. (c) and the definition of tangential complex implies the following Prop. (f ) Dimension of maximal simplices in Del (L, T M) is equal to m.

Case-2. qc 2 ≤ pc 2 + 8λ 2 . This implies qc < pc + 3λ.

Using the facts that pc ≤ 8λ (from Lemma 29 (1)), cc

where B = 2 15 .

From Case-1 and 2, we get

.

Lemma 39 Let W ⊆ M be an ε-sample of M, L ⊆ W be a λ-net of W with ε ≤ λ, and δ = δ 0 λ. Also, let : L → [0, ∞) be a weight assignment with < 1 2 and satisfying conditions (1) to (2) of Lemma 38.

.

From Lemma 8 (2) as c ∈ Vor (σ k ) ∩ M, we have for all p ∈ σ k , pc ≤ 4λ.

Proof

As in the proof of Lemma 43, we can show that |2D(p, σ)H 1 (p, σ)| ≤ 2 13 Γ 0 λ. From Corollary 45, we have

This implies, from the definition of F 1 (p, σ),

From Lemma 41, and the above bounds we get

The result now follows from the fact that (p) = 1 (p).

Remark 47 Note that η ≥ η 1 + 2δ 2 0 λ 2 . Combining Lemmas 43 and 46, completes the proof of Lemma 20. The following technical lemma, which asserts that, for j ≤ m = dim M, if a (dj)-flat, N, passes through a point c that is close to M, and the normal space at the point on M closest to c makes a small angle with N, then N must intersect M in that vicinity. The technical difficulty stems from the fact that the codimension may be greater than one.

C Almost normal flats intersecting submanifolds

Lemma 48 Let c ∈ R d be such that it has a unique closest point ĉ on M and cĉ ≤ ρ ≤ rch(M) 25 . Let j ≤ m = dim M, and let N be a (dj)-dimensional affine flat passing through c such that ∠(N ĉM, N) ≤ α with sin α ≤ 1 4 . Then there exists an x ∈ N ∩ M such that cx ≤ 4ρ.

The idea of the proof is to consider the m-dimensional affine space T ĉM that passes through ĉ and is orthogonal to a (dm)-dimensional affine subspace of N. We show that the orthogonal