当前位置：文档库 › ABSTRACT Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes

ABSTRACT Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes

Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes

Jean-Daniel Boissonnat INRIA,Geometrica

2004,route des lucioles

06902Sophia-Antipolis boissonn@sophia.inria.fr

Leonidas J.Guibas

Computer Science Dept.

Stanford University

Stanford,CA94305

guibas@https://www.wendangku.net/doc/73712725.html,

Steve Y.Oudot

Computer Science Dept.

Stanford University

Stanford,CA94305

steve.oudot@https://www.wendangku.net/doc/73712725.html,

ABSTRACT

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low di-mensions.Speci?cally,it has been proved that the witness complex coincides with the restricted Delaunay triangula-tion on curves,and is still a subset of it on surfaces,un-der mild sampling assumptions.Unfortunately,these re-sults do not extend to higher-dimensional manifolds,even under stronger sampling conditions.In this paper,we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between both complexes still hold on higher-dimensional manifolds.We also use our structural results to devise an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at dif-ferent scales.The algorithm combines a farthest-point re-?nement scheme with a vertex pumping strategy.It is very simple conceptually,and does not require the input point sample W to be sparse.Its time complexity is bounded by c(d)|W|2,where c(d)is a constant depending solely on the dimension d of the ambient space.

Categories and Subject Descriptors:I.3.5[Computer Graphics]:Curve,surface,solid,and object representations General Terms:Algorithms,Theory.

Keywords:Witness complex,restricted Delaunay triangu-lation,manifold reconstruction,sampling conditions.

1.INTRODUCTION

A number of areas of Science and Engineering deal with point clouds lying on submanifolds of Euclidean spaces.Such data can be either collected through measurements of nat-ural phenomena,or generated by simulations.Given a?-nite set of sample points W,presumably drawn from an un-known manifold S,the goal is to retrieve some information about S from W.This manifold learning problem,which is at the core of non-linear dimensionality reduction tech-niques[2527],?nds applications in many areas,including Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the?rst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior speci?c permission and/or a fee.

SCG’07,June6–8,2007,Gyeongju,South Korea.

Copyright2007ACM978-1-59593-705-6/07/0006...$5.00.machine learning[4],pattern recognition[26],scienti?c vi-sualization[28],image or signal processing[22],and neural computation[16].The nature of the sought-for information is very application-dependent,and sometimes it is enough to inquire about the topological invariants of the manifold, a case in which techniques such as topological persistence [81329]o?er a nice mathematical framework.However, in many situations it is desirable to construct a simplicial complex with the same topological type as the manifold,and close to it geometrically.

This problem has received a lot of attention from the com-putational geometry community,which proposed elegant so-lutions in low dimensions,based on the use of the Delaunay triangulation D(W)of the input point set W–see[6]for a survey.In these methods,the output complex is extracted from D(W),and it is equal or close to D S(W),the Delau-nay triangulation of W restricted to the manifold S.What makes the Delaunay-based approach attractive is that,not only does it behave well on practical examples,but its per-formance is guaranteed by a sound theoretical framework. Indeed,the restricted Delaunay triangulation is known to provide good topological and geometric approximations of smooth or Lipschitz curves in the plane and surfaces in3-space,under mild sampling conditions[125]. Generalizing these ideas to arbitrary dimensions and co-dimensions is di?cult however,because a given point set W may sample well various manifolds with di?erent homotopy types,as illustrated in Figure1.To overcome this issue,it has been suggested to strengthen the sampling conditions, so that they can be satis?ed by only one class of manifolds sharing the same topological invariants[121720].In some sense,this is like choosing arbitrarily between the possible reconstructions,and ignoring the rest of the information car-ried by the input.Moreover,the new sets of conditions on the input are so strict that they are hardly satis?able in practice,thereby making the contributions rather theoreti-cal.Yet[121720]contain a wealth of relevant ideas and results,some of which are used in this paper.

A di?erent and very promising approach[792123],rem-iniscent of topological persistence,builds a one-parameter family of complexes that approximate S at various scales. The claim is that,for su?ciently dense W,the family con-tains a long sequence of complexes carrying the same ho-motopy type as S.In fact,there can be several such se-quences,each one corresponding to a plausible reconstruc-tion–see Figure1.Therefore,performing a reconstruction on W boils down to?nding the long stable sequences in the

Figure1:A helical curve drawn on a torus(top). Any dense sampling of the curve is also a dense sampling of the torus.To deal with this ambiguity, the algorithm of[21]builds a sequence of complexes (bottom)approximating the input at various scales, and maintains their Betti numbers(top).

one-parameter family of complexes.This approach to re-construction stands in sharp contrast with previous work in the area.In[7923],the family of complexes is derived from theα-o?sets of the input W,whereαranges from zero to in?nity.The theoretical guarantees of[7]hold in a very wide setting,since W is assumed to be a su?ciently dense sampling of a general compact set.In[21],the family is given by the witness complex of L relative to W,or C W(L) for short,where L is a subset of W constructed iteratively, starting with L=?,and inserting each time the point of W lying furthest away from L.It is known that C W(L)coin-cides with D S(L)on smooth curves,and is still included in it on smooth surfaces[321].The assumptions on L in[21] are more stringent than the ones on W,but this is not an issue since L is generated by the algorithm.Unfortunately, the structural results of[321]do not hold in higher dimen-sions,which makes it very unlikely that the algorithm works on any manifold S of dimension greater than two.The rea-son is that the normals of D S(L)can be arbitrarily wrong if D S(L)contains badly-shaped simplices,called slivers[12]. As a consequence,C W(L)may not be included in D S(L), which may not be homotopy equivalent to S[24].This is true even if W and L satisfy strong sampling conditions, such as being arbitrarily dense uniform samples of S.

In this paper,we show how to enrich W and L in or-der to make the structural results of[321]hold for higher-dimensional manifolds.To each point p∈L we assign a non-negative weightω(p),so that D S(L)and C W(L)are now replaced by their weighted versions,D Sω(L)and C Wω(L). The idea of assigning weights to the vertices comes from[10], where it was used to remove slivers from3-dimensional De-launay triangulations.This sliver removal technique was extended to higher dimensions by Cheng et al.[12],who showed that,under su?cient sampling conditions on L,there exists a distribution of weightsωsuch that D Sω(L)is homeo-morphic to S.Our main result is that,for the same distribu-tion of weights and under similar conditions on L,C Wω(L)is included in D Sω(L),for all W?https://www.wendangku.net/doc/73712725.html,bined with the fact that C Sω(L)contains D Sω(L),we get that C Sω(L)=D Sω(L), which is homeomorphic to S.This is a generalization of the result of[3]to higher-dimensional manifolds.It is not quite practical since W has to be equal to S.In the more realistic case where W is a?nite subset of S,we enlarge it by replac-ing its points by balls of radiusζ.For su?ciently largeζ,this enlarged set Wζcontains S,and hence D Sω(L)?C Wζ

(L).

And ifζis not too large,then C Wζ

(L)is still included in

D Sω(L).Thus,we obtain C Wζ

(L)=D Sω(L)under su?cient conditions on W,L,ζ.Here again,the condition on L is stringent,but the one on W is mild.

These structural results suggest combining the method of [21]with the sliver exudation technique of[10],in order to make it work on higher-dimensional manifolds.Our com-bination is the simplest possible:at each iteration of the algorithm,we insert a new point p in L,compute its best

possible weight,and update C Wζ

(L).This algorithm is very simple conceptually,and to some extent it can be viewed as a dynamic version of the algorithm of[12],where the Delau-nay triangulation of W would be constructed progressively as the weights of the points of W are computed.This raises a number of questions,such as whether the weight assignment process removes all the slivers from the vicinity of D Sω(L), since some of the weights are assigned in early stages of the course of the algorithm.We prove that all slivers are in-

deed removed at some point,and that consequently C Wζ

(L) is homeomorphic to S,provided that W is a dense enough sampling of S.

Our assumption on W is much less stringent than the one used in[12],which makes our algorithm more practical.On the other hand,our assumption that S is a smooth man-ifold is stronger than the one of[7],but we get stronger

guarantees,namely C Wζ

(L)is homeomorphic to S,whereas the complex of[7]is only homotopy equivalent to S.Ob-serve also that the witness complex is always embedded in the ambient space R d,which is not the case of the nerve of an o?set.This is important if one wants to do fur-ther processing on the reconstruction.By considering the α-shape of W instead of the nerve of itsα-o?set,the au-thors of[7]get rid of this issue.Nevertheless,they cannot get rid of the so-called curse of dimensionality because,as αvaries from zero to in?nity,theα-complex spans the en-tire d-dimensional Delaunay triangulation of W,whose size isΘ“|W| d/2 ”.In contrast,the witness complex can be maintained by considering only theκ(d)nearest neighbors in L of each point of W,which reduces the time complex-ity of our algorithm to O`c(d)|W|2′,whereκ(d)and c(d) are constants depending solely on d.This is worse than the bound of[12](c(d)|W|log|W|)since we cannot bene?t from the sparseness assumption on W,which is essential for the correctness of the algorithm of[12].

The outline of the paper is as follows:after recalling the necessary background in Section2,we present our main structural result(Theorem3.1)in Section3,and we intro-duce our reconstruction algorithm in Section4.

2.BACKGROUND AND DEFINITIONS 2.1Manifolds and samples

The ambient space is R d ,d ≥3,equipped with the usual Euclidean norm p =q P d

i =1p 2

i .All manifolds considered

in this paper are compact closed submanifolds of R d ,of di-mension two or more.The case of curves has already been addressed 1in [21].The reach of a manifold S ,or rch(S )for short,is the minimum distance of a point on S to the medial axis of S .All manifolds in this paper are assumed to have a positive reach.This is equivalent to saying that they are C 1-continuous,and that their normal vector ?eld satis?es a Lipschitz condition.

Given a (?nite or in?nite)subset L of a manifold S ,and a positive parameter ε,L is an ε-sample of S if every point of S is at Euclidean distance at most εto L ,and L is ε-sparse if the pairwise Euclidean distances between the points of L are at least ε.Note that an ε-sparse sample of a compact set is always ?nite.Parameter εis sometimes made adaptative in the literature [1],its value depending on the distance to the medial axis of the manifold.

2.2Simplex shape

Given k +1points p 0,···,p k ∈R d ,[p 0,···,p k ]denotes the k -simplex of vertices p 0,···,p k .The geometric realiza-tion of this simplex is the convex hull of p 0,···,p k ,which has dimension k if the vertices are a?nely independent.Fol-lowing [11],we call sliver measure of [p 0,···,p k ]the ratio 2: ([p 0,···,p k ])=

vol([p 0,···,p k ])

min { p i ?p j ,0≤i

(1)

where vol([p 0,···,p k ])denotes the volume of the convex hull of p 0,···,p k in R k .In the special case where k =1,we have ([p 0,p 1])=1for any edge [p 0,p 1].We extend the notion of sliver measure to the case k =0by imposing ([p 0])=1for any vertex p 0.Given ˉ ≥0,simplex [p 0,···,p k ]is said to be

a ˉ -sliver if ([p 0,···,p k ])<ˉ k /k !.For su?ciently small ˉ ,

this means that the volume of the simplex is small compared to the volume of the diametral k -ball of its shortest edge.As a result,the simplex is badly-shaped.Note however that having a large sliver measure does not always mean being well-shaped.Take an isoceles triangle t of base b and height h ≥b √

2.Its sliver measure is (t )=h ·b 2

b 2

=h 2b .Reducing b while keeping h constant makes t arbitrarily skinny but (t )arbitrarily large –t is called a dagger in the literature [10].Parameter ˉ is called the sliver bound in the sequel.

2.3Weighted points,Delaunay triangulation,

and witness complex

Given a ?nite point set L ?R d ,a distribution of weights on L is a non-negative real-valued function ω:L →[0,∞).

The quantity max u ∈L,v ∈L \{u }ω

(u )

u ?v

is called the relative amplitude of ω.Given p ∈R d ,the weighted distance from p to some weighted point v ∈L is p ?v 2?ω(v )2.This is actually not a metric,since it is not symmetric.Whenever

The results of [21]apply to Lipschitz curves in the plane,but they can be extended to smooth curves in higher dimen-sions in a straightforward manner.2

This de?nition generalizes the one of [10]to higher dimen-sions.It departs from the de?nition of [12],which intro-duced a bug in the proof of Lemma 10of the same paper.

the relative amplitude of ωis less than 1,the points of L have non-empty cells in the weighted Voronoi diagram of L ,and in fact each point of L belongs to its own cell [10].

Given a ?nite point set L ?R d ,and a distribution of weights ωon L ,we denote by D ω(L )the weighted Delaunay triangulation of L [19].For any simplex σof D ω(L ),V ω(σ)denotes the face of the weighted Voronoi diagram of L that is dual to σ.Moreover,given any subset X of R d ,we call D X ω(L )the weighted Delaunay triangulation of L restricted to X .In the special case where all the weights are equal,D ω(L )coincides with the standard Euclidean Delaunay tri-angulation,and is therefore noted D (L ).Similarly,V ω(σ)

becomes V(σ),and D X

ω(L )becomes D X (L ).Definition 2.1.Let W,L ?R d be such that L is ?nite,and let ωbe a distribution of weights on L .

?Given a point w ∈W and a simplex σ=[p 0,···,p k ]with vertices in L ,w ω-witnesses σif p 0,···,p k are among the k +1nearest neighbors of w in the weighted metric,that is,?i ∈{0,···,k },?q ∈L \{p 0,···,p k }, w ?p i 2?ω(p i )2≤ w ?q 2?ω(q )2.

?The ω-witness complex of L relative to W ,or C W

ω(L )for short,is the maximum abstract simplicial complex with ver-tices in L ,whose faces are ω-witnessed by points of W .This de?nition comes from [1415].From now on,W will be referred to as the set of witnesses,and L as the set of landmarks.In the special case where all the weights are

equal,C W

ω(L )coincides with the witness complex for the standard Euclidean norm,and is therefore noted C W (L ).Given a distribution of weights ωon L ,for any simplex

σ=[p 0,···,p k ]of D W

ω(L )and any point w ∈W lying on the weighted Voronoi face dual to σ,we have that w is a ω-witness of σand that w ?p i 2?ω(p i )2= w ?p j 2?ω(p j )2?i,j ∈{0,···,k }.Hence,w is also a ω-witness of all the

subsimplices of σ,which therefore belong to C W

ω(L ).Corollary 2.2.For any W,L ?R d with L ?nite,for

any ω:L →[0,∞),D W ω(L )?C W

ω(L ).

D W ω(L )is sometimes called the strong witness complex of L relative to W in the literature [15].Given a distribution of weights ωon L ,we say that the weighted points of L lie in general position if no point of R d is equidistant to d +2points of L in the weighted metric,and if no d +1points on the convex hull of L are coplanar.Under this assumption,every simplex of D ω(L )has dimension at most d .

Theorem 2.3(Thm.2and §3of [14]).Let W,L ?R d

be such that L is ?nite.Let also ωbe any distribution of weights on L ,such that the weighted point set L lies in general position.Let σbe a simplex with vertices in L .If σand all its subsimplices are ω-witnessed by points of W ,

then σbelongs to D ω(L ).In other words,C W

ω(L )is a sub-complex of D ω(L ).Moreover,the dual weighted Voronoi face of σintersects the convex hull of the ω-witnesses of σand its subsimplices.

It is always possible to perturb the points of L or their weights in?nitesimally,so as to make them lie in general position.Therefore,in the rest of the paper we assume im-plicitely that the weighted point set L is in general position.On 1-and 2-dimensional manifolds,the unweighted wit-ness complex is closely related to the unweighted restricted Delaunay triangulation [321],which provides good topolog-ical and geometric approximations [12].However,as proved

in[24],these properties do not extend to higher-dimensional manifolds,even under stronger sampling conditions: Theorem2.4(see[24]).For any positive constantμ< 1/3,there exists a closed and compact hypersurface S of pos-

itive reach in R4,and an?(ε)-sparse O(ε)-sample L of S, withε=μrch(S),such that D S(L)is not homotopy equiv-alent to S.The constants hidden in the?and O notations are absolute and do not depend onμ.In addition,for any δ>0,there exists aδ-sample W of S such that C W(L)nei-ther contains nor is contained in D S(L).Furthermore,W can be made indi?erently?nite or in?nite.

The proof of this theorem builds on an example of[12,§11]. The intuition is that,when D S(L)contains slivers,it is pos-sible to make its normals turn by a large angle(sayπ/2)by perturbing the points of L in?nitesimally.Then,the com-binatorial structure of D S(L)can change arbitrarily under small perturbations of S.The consequence is that D S(L) may not be homotopy equivalent to S,and it may not con-tain all the simplices of C W(L)either.In addition,as em-phasized in[21],for any k≥2,the k-simplices of D S(L) may have arbitrarily small cells in the restricted Voronoi di-agram of L of order k+1,which implies that they may not be witnessed in W if ever W S.

2.4Weighted cocone complex

At any point p on a manifold S,there exist a tangent space T(p)and a normal space N(p).These two subspaces of R d are orthogonal,and their direct sum is R d.For any angle valueθ∈[0,π/2],we callθ-cocone of S at p,or Kθ(p) for short,the cone of semi-apertureθaround the tangent space of S at p:Kθ(p)={q∈R d|∠(pq,T(p))≤θ}.The name cocone refers to the fact that Kθ(p)is the complement of a cone of semi-apertureπ?θaround the normal space of S at p.

Given an angleθ∈[0,π/2],a manifold S,a?nite point set L?S,and a distribution of weightsω:L→[0,∞),the weightedθ-cocone complex of L,noted Kθω(L),is the subcom-plex of Dω(L)made of the simplices whose dual weighted Voronoi faces intersect theθ-cocone of at least one of their vertices.This means that a simplex[p0,···,p k]of Dω(L) belongs to Kθω(L)if,and only if,its dual weighted Voronoi face intersects Kθ(p0)∪···∪Kθ(p k).Note that the cones in [12]are de?ned around approximations of the tangent spaces of S at the points of L.However,the results of[12]hold a fortiori when the approximations of the tangent spaces are error-free,which is the case here.

Theorem2.5(Lemmas13,14,18of[12]).For any sliver boundˉ >0,there exists a constant cˉ >0such that, for any manifold S,for anyε-sparse2ε-sample L of S with ε≤cˉ rch(S),and for anyω:L→[0,∞)of relative ampli-

tude less than1

2,if Kπ/32

(L)has noˉ -sliver,then Kπ/32

(L)

coincides with D Sω(L),which is homeomorphic to S.

It is also proved in[12]that,for anyˉω∈(0,1/2),there exists a distribution of weightsωon L,of relative amplitude at mostˉω,that removes allˉ -slivers from Kπ/32

(L).This is true provided thatˉ is su?ciently small compared toˉω, and thatε≤cˉ rch(S)(as in Theorem2.5,the choice ofˉ in?uences the bound onε).The results of[12]hold in fact in the slightly more general setting whereεis a(non-uniform) 1-Lipschitz function,everywhere bounded by a fraction of the distance to the medial axis of S–see[12,§13].2.5Useful results

The following results,adapted from[1220],will be used in the sequel:

Lemma2.6(Lemma6of[20]).Let S be a manifold, and let p,q∈S be such that p?q

2rch(S)

Lemma2.7(Lemma2of[12]).Let S be a manifold andθ∈[0,π/2]an angle value.Let v∈S and p∈Kθ(v)be such that p?v

Lemma2.8(Lemma3of[12]).Let S be a manifold andθ∈[0,π/2)an angle value.Let L be anε-sample of S,withε<4

(1?sinθ)2rch(S).For anyω:L→[0,∞) of relative amplitude less than1,for any v∈L and any p∈Kθ(v)∩Vω(v),we have p?v ≤3ε.

3.STRUCTURAL RESULTS

In this section,ˉω∈(0,1/2)andˉ >0are?xed constants. For any k≥0,we de?ne c1(k)=4(1+2ˉω+k(1+3ˉω))and c2(k)=4(3+6ˉω+2k(1+3ˉω)).Let S be a manifold in R d, W a(?nite or in?nite)δ-sample of S in R d,and L a(?nite)ε-sparseε-sample of W,for two parametersδ,εto be speci?ed later on.Note that L is an(ε+δ)-sample of S.According to Theorem2.4,C W(L)may not coincide with D S(L),even under strong assumptions onδ,ε.Speci?cally:

?some simplices of D S(L)may not belong to C W(L)if W does not span S entirely.Our solution to this problem is to enlarge the set of witnesses,in order to make it cover S.More precisely,we dilate W by a ball of radiusζcentered at the origin,so that the set of witnesses is now Wζ=S w∈W B(w,ζ).Forζ≥δ,this set contains S,

hence D Sω(L)?D Wζ

(L)?C Wζ

(L).

?some simplices of C W(L)may not belong to D S(L)if the latter containsˉ -slivers.To remedy this problem, we assign non-negative weights to the landmarks,so that

D S(L)and C W(L)are now replaced by their weighted

versions,D Sω(L)and C Wω(L).Given any angle valueθ∈(0,π/2),our main structural result(Theorem3.1)states that,under su?cient conditions onδ,ε,ζ,Kθω(L)con-

tains C Wζ

(L)for anyω:L→[0,∞)of relative ampli-

tude at mostˉω.Therefore,C Wζ

(L)?D Sω(L)whenever

θ≤πandωremoves allˉ -slivers from Kπ/32

(L),by The-orem2.5.

Theorem 3.1.Given any angle valueθ∈(0,π/2),ifδ,ε,ζsatisfy the following conditions:

H152δ≤ε≤5(1?ˉω2)sinθ

2(1?ˉω2)sinθ+5c2(d)2

rch(S),

H2ζ∈hδ,2(1?ˉω2)sinθεi,

then D Sω(L)?D Wζ

(L)?C Wζ

(L)?Kθω(L)for any dis-tribution of weightsωon L of relative amplitude at most ˉω.If in additionθ≤π/32,ε≤cˉ rch(S),andωis such

that Kπ/32

(L)contains noˉ -sliver3,then Theorem2.5im-

plies that D Wζ

(L)=C Wζ

(L)=Kπ/32

(L)=D Sω(L),which is homeomorphic to S.

3As mentioned after Theorem 2.5,such distributions of weights exist,provided thatˉ is su?ciently small.

H1requires that W is dense compared to L,which must be dense compared to rch(S).This is very similar in spirit to the condition of[21].H2bounds the dilation parameterζ. The smaller the angleθof semi-aperture of the cocones, the smallerεmust be for Kθω(L)to contain D Sω(L),and the smallerζmust be for Kθω(L)to contain C Wζ

(L).Condition

ζ≥δensures that D Sω(L)?C Wζ

ω(L).

In the special case where W=S(which impliesδ=0) andζ=0,H2and the left-hand side of H1become void, and the theorem states that C Sω(L)coincides with D Sω(L)for a suitable distribution of weightsω:L→[0,∞),provided that L is anε-sparseε-sample of S,for a small enoughε. This is an extension of the result of Attali et al.[3]to higher dimensions,with an additional sparseness condition on L. This condition is mandatory for the existence of a suitable ωon manifolds of dimension three or higher[1012].The general case of Theorem3.1allows to have W S,which is more practical.

Another useful property,stated as Theorem3.2below, is that the weighted witness complex actually includes the weighted cocone complex,for any distribution of weights of relative amplitude at mostˉω,provided thatζis su?ciently large compared toε.Note that this condition onζis incom-patible4with H2:as a consequence,two di?erent values of ζhave to be used in order to bound Kθω(L),as emphasized in our algorithm–see Section4.

Theorem 3.2.Ifθ≤π,and ifδ,εsatisfy Condition H1of Theorem3.1,then,for anyζ≥7sinθε,for any ω:L→[0,∞)of relative amplitude at mostˉω,Kθω(L)?

D Wζ

ω(L)?C Wζ

(L).

The rest of Section3is devoted to the proofs of Theorems 3.1and3.2,and we give an overview below.

Overview of the proofs

The proof of Theorem3.1is given in Section3.1.Showing

that D Sω(L)?D Wζ

ω(L)?C Wζ

(L)is in fact easy:since W

is aδ-sample of S,Wζcontains S wheneverζ≥δ,which is guaranteed by H2;it follows immediately that D Sω(L)?

D Wζ

ω(L),which by Corollary2.2is included in C Wζ

(L)for

anyω:L→[0,∞).Showing that C Wζ

ω(L)?Kθω(L)re-

quires more work,but the core argument is very simple, namely:the Euclidean distances between a point of S and its k nearest landmarks in the weighted metric are bounded (Lemma3.4).From this fact we derive some bounds on

the Euclidean distances between the simplices of C Wζ

ω(L)

and theirω-witnesses(Lemma3.5).These bounds are then used to show that theω-witnesses of a simplexσlie in the θ-cocones of the vertices ofσ,from which we deduce that

C Wζω(L)?Kθω(L)(Lemma3.6).

The proof of Theorem3.2is given in Section3.2.In-tuitively,if L is a su?ciently dense sampling of S,then, for any simplexσ∈Kθω(L)and any vertex v ofσsuch that Vω(σ)∩Kθ(v)=?,the points of Vω(σ)∩Kθ(v)lie close to T(v)and hence close to S.Therefore,they be-long to Wζwheneverζis large enough,which implies that

σ∈D Wζ

ω(L)?C Wζ

(L).

4Indeed,the upper bound onζin H2is always smaller than the lower bound onζin Theorem3.2.3.1Proof of Theorem3.1

As explained above,all we have to do is to show that, whenever Conditions H1–H2are satis?ed,C Wζ

(L)is in-cluded in Kθω(L)for anyω:L→[0,∞)of relative amplitude at mostˉω.We will use the following bound on the weights: Lemma 3.3.Under Condition H1of Theorem 3.1,for any v∈L and anyω:L→[0,∞)of relative amplitude at mostˉω,ω(v)is at most2ˉω(ε+δ).

Proof.Let v∈L,and let S v be the connected com-ponent of S containing v.Consider the cell V(v)of v in the unweighted Voronoi diagram of L.Since L is an(ε+δ)-sample of S,S v∩V(v)is contained in the ball B(v)of center v and radiusε+δ.By H1,the radius of this ball is at most rch(S),hence we have S v∩B(v) S v.This implies that the boundary of V(v)intersects S v.Let p be a point of inter-section.There is a point u∈L such that p?u = p?v , which is at mostε+δ.Hence, v?u ≤2(ε+δ).We deduce thatω(v)≤ˉω v?u ≤2ˉω(ε+δ),sinceˉωbounds the relative amplitude ofω.

Here is now the core argument of the proof of Theorem3.1: Lemma 3.4.Under Condition H1of Theorem 3.1,for anyω:L→[0,∞)of relative amplitude at mostˉω,for any p∈S,and for any k≤d,the Euclidean distance be-tween p and its(k+1)th nearest landmark in the weighted metric is at most r k=(1+2ˉω+2k(1+3ˉω))(ε+δ).

Proof.The proof is by induction on k.Assume?rst that k=0.Let v1∈L be the nearest neighbor of p in the weighted metric,and u∈L the nearest neighbor of p in the Euclidean metric.Observe that u may or may not be equal to v1.Since L is an(ε+δ)-sample of S, p?u is at mostε+δ.Moreover,we have p?v1 2?ω(v1)2≤ p?u 2?ω(u)2, which gives p?v1 2≤ p?u 2+ω(v1)2?ω(u)2≤(ε+δ)2+ω(v1)2?ω(u)2.Note that?ω(u)2is non-positive,and that ω(v1)2is at most4ˉω2(ε+δ)2,by Lemma3.3.Therefore, p?v1 2≤(1+4ˉω2)(ε+δ)2≤(1+2ˉω)2(ε+δ)2,which proves the lemma in the case k=0.

Assume now that k≥1,and that the result holds up to k?1.Let v1,···,v k denote the k nearest landmarks of p in the weighted metric.By induction,we have{v1,···,v k}?B(p,r k?1).Moreover,by the case k=0above,for any i≤k we have S∩Vω(v i)?B(v i,(1+2ˉω)(ε+δ)),which is included in B(p,r k?1+(1+2ˉω)(ε+δ)).Let S p be the connected component of S that contains p.It follows from H1that r k?1+(1+2ˉω)(ε+δ)≤rch(S),hence we have S∩B(p,r k?1+(1+2ˉω)(ε+δ)) S p,which implies two things:?rst,v1,···,v k belong to S p;second,their weighted Voronoi cells do not cover S p entirely.As a consequence, S p must intersect the boundary of S k i=1(S∩Vω(v i)).Let q be a point of intersection:q lies on the bisector hyperplane between some v i and some point v∈L\{v1,···,v k},i.e. q∈Vω(v i)∩Vω(v).By the case k=0above, q?v i and q?v are at most(1+2ˉω)(ε+δ).Moreover,we have p?v i ≤r k?1,by induction.Therefore, p?v ≤ p?v i + v i?q + q?v ≤r k?1+2(1+2ˉω)(ε+δ). Since v∈L\{v1,···,v k},we have p?v k+1 2?ω(v k+1)2≤ p?v 2?ω(v)2,where v k+1is the(k+1)th nearest landmark of p in the weighted metric.Hence, p?v k+1 2≤ p?v 2+ω(v k+1)2≤( p?v +ω(v k+1))2,which is at most (r k?1+2(1+2ˉω)(ε+δ)+2ˉω(ε+δ))2=r2k,by Lemma3.3.

Using Lemma3.4,we can bound the Euclidean distances

between the simplices of C Wζ

ω(L)and theirω-witnesses.Our

bounds depend on quantities c1(k),c2(k),de?ned at the top of Section3:

Lemma3.5.Under Conditions H1–H2of Theorem3.1, for anyω:L→[0,∞)of relative amplitude at mostˉω,for

any k-simplexσof C Wζ

ω(L)(k≤d),and for any vertex v of

σ,we have:

(i)for anyω-witness c∈Wζofσ, c?v ≤c1(k)ε, (ii)for any subsimplexσ ?σand anyω-witness c ∈Wζofσ , c ?v ≤c2(k)ε.

Proof.Letσbe a k-simplex of C Wζ

ω(L).By de?nition,

there is a point c∈Wζthatω-witnessesσ.This means that the vertices ofσare the(k+1)nearest landmarks of c in the weighted metric.Unfortunately,we cannot apply Lemma 3.4directly to bound the Euclidean distance between c and its(k+1)nearest landmarks in the weighted metric,because c may not belong to S.However,since c∈Wζ,there is some point w∈W?S such that c∈B(w,ζ).By Lemma 3.4,the ball B(w,r k)contains at least(k+1)landmarks. Thus,at least one landmark u in B(w,r k)does not belong to the k nearest landmarks of c in the weighted metric.This means that,for any l≤k+1, c?v l 2?ω(v l)2≤ c?u 2?ω(u)2,where v l denotes the l th nearest landmark of c in the weighted metric.It follows that c?v l 2≤ c?u 2+ω(v l)2?ω(u)2≤( c?u +ω(v l))2,which by Lemma 3.3is at most( c?u +2ˉω(ε+δ))2.Since c?u ≤ c?w + w?u ≤ζ+r k,we get c?v l ≤ζ+r k+2ˉω(ε+δ), which by H1–H2is bounded by c1(k)ε.Since this is true for any l≤k+1,the Euclidean distance between c and any vertex ofσis at most c1(k)ε.This proves(i).

Letσ be any subsimplex ofσ.Sinceσbelongs to C Wζ

ω(L),

σ isω-witnessed by some point c ∈Wζ.Let w ∈W?S be such that c ∈B(w ,ζ).According to Lemma3.4,the Euclidean distance between w and its nearest landmark u in the weighted metric is at most r0=(1+2ˉω)(ε+δ).Hence, c ?u ≤ζ+r0.Let v 1be the nearest landmark of c in the weighted metric.We have c ?v 1 2≤ c ?u 2+ω(v 1)2?ω(u )2≤( c ?u +ω(v 1))2,which is at most (ζ+r0+2ˉω(ε+δ))2,by Lemma3.3.Since c ω-witnessesσ , v 1is a vertex ofσ and hence also a vertex ofσ.Thus,for any vertex v ofσ,we have c ?v ≤ c ?v 1 + v 1?v , which by(i)is at mostζ+r0+2ˉω(ε+δ)+2c1(k)ε.This quantity is bounded by c2(k)ε,since under H1–H2δandζare at mostε.This proves(ii).

We can now show that C Wζ

ω(L)?Kθω(L),which concludes

the proof of Theorem3.1:

Lemma3.6.Under Conditions H1–H2of Theorem3.1, for any distribution of weightsω:L→[0,∞)of relative

amplitude at mostˉω,for any k-simplexσof C Wζ

ω(L)(k≤

d),and for any vertex v ofσ,Vω(σ)∩Kθ(v)=?.As a consequence,C Wζ

(L)?Kθω(L).

Proof.Letσbe a k-simplex of C Wζ

ω(L),and let v∈L

be any vertex ofσ.If k=0,thenσ=[v].Since the relative amplitude ofωis at mostˉω<1,v belongs to its weighted Voronoi cell Vω(v).And since v belongs to Kθ(v),we have Vω(v)∩Kθ(v)=?,which proves the lemma in the case k=0.

Assume now that1≤k≤d.By Lemma3.5(ii),for any simplexσ ?σ,for anyω-witness c ofσ ,we have c ?v ≤c2(k)ε≤c2(d)ε.Since c ∈Wζ,there is a point w ∈W?S such that w ?c ≤ζ,which implies that w ?v ≤ε(c2(d)+ζ/ε).This quantity is at most rch(S),by H1–H2,hence the Euclidean distance from w

to T(v)is at mostε2

2rch(S)

(c2(d)+ζ/ε)2,by Lemma2.6.It follows that the Euclidean distance from c to T(v)is at most

ζ+ε2

2rch(S)

(c2(d)+ζ/ε)2.This holds for anyω-witness c ∈

Wζof any simplexσ ?σ.Sinceσis a simplex of C Wζ

(L), Theorem2.3tells us thatσbelongs to Dω(L),and that the dual weighted Voronoi face ofσintersects the convex hull of theω-witnesses of the subsimplices ofσ.Let p be a point of intersection.Since theω-witnesses of the subsimplices ofσdo not lie farther thanζ+ε2

2rch(S)

(c2(d)+ζ/ε)2from T(v), neither does p,which belongs to their convex hull.

Let us now give a lower bound on p?v ,which will allow us to conclude afterwards.Since the dimension k ofσis at least one,σhas at least two vertices.Hence,there exists at least one point u∈L\{v}such that p?v 2?ω(v)2= p?u 2?ω(u)2,which gives p?v 2= p?u 2+ω(v)2?ω(u)2. Sinceˉωbounds the relative amplitude ofω,we haveω(u)2≤ˉω2 u?v 2.Moreover,ω(v)2is non-negative.Hence, p?v 2≥ p?u 2?ˉω2 u?v 2.By the triangle inequality, we obtain p?v 2≥( p?v ? u?v )2?ˉω2 u?v 2, which gives p?v ≥1(1?ˉω2) u?v .This implies that p?v ≥1

(1?ˉω2)ε,since L isε-sparse.

To conclude,p is at mostζ+ε2

2rch(S)

(c2(d)+ζ/ε)2away

from T(v),and at least1

(1?ˉω2)εaway from v,in the Euclidean metric.Therefore,sin∠(vp,T(v))≤2ζ2+ε

(1?ˉω2)rch(S)

(c2(d)+ζ/ε)2,which is at most sinθ,by H1–H2.As a consequence,p belongs to Kθ(v).Now,recall that p is a point of Vω(σ).Hence,Vω(σ)∩Kθ(v)=?,which means thatσis a simplex of Kθω(L).Since this is true for

any k-simplexσof C Wζ

(L)(k≤d),and since,by Theorem

2.3,C Wζ

(L)is included in Dω(L),which has no simplex of dimension greater than d because the weighted point set L

lies in general position,C Wζ

(L)is included in Kθω(L).

3.2Proof of Theorem3.2

Letσbe a simplex of Kθω(L).By de?nition,the dual weighted Voronoi face ofσintersects theθ-cocone of at least one vertex v ofσ.Let c be a point of intersection. Since L is an(ε+δ)-sample of S,withε+δ<4

(1?

sinθ)2rch(S),Lemma2.8states that c?v ≤3(ε+δ)

1?sinθ

, which is less than rch(S)since by assumption we haveε+δ<1?sinθrch(S).Therefore,by Lemma2.7,we have

q ?c ≤3(ε+δ)

1?sinθ“sinθ+3(ε+δ)

2(1?sinθ)rch(S)”,where q is a point of S closest to c.Since W is aδ-sample of S,there exists some point w∈W such that q ?w ≤δ.Hence, c?w ≤δ+3(ε+δ)“sinθ+3(ε+δ)”,which is at mostζby hypothesis.It follows that c∈Wζ,and hence

thatσbelongs to D Wζ

(L).This concludes the proof of The-orem3.2.

4.MANIFOLD RECONSTRUCTION

In this section,we use our structural results in the context

of manifold reconstruction.From now on,we?xˉω=1

4and

θ=π,and we setˉ to an arbitrarily small positive value. We give an overview of the approach in Section4.1,then we present the algorithm in Section4.2,and we prove its correctness in Section4.3.Our theoretical guarantees are discussed in Section4.4.In Section4.5,we give some de-tails on how the various components of the algorithm can be implemented.These details are then used in Section4.6 to bound the space and time complexities of the algorithm.

4.1Overview of the approach

Let W be a?nite input point set drawn from some un-known manifold S,such that W is aδ-sample of S,for some unknownδ>0.Imagine we were able to construct anε-sparseε-sample L of W,for someε≤cˉ rch(S)satisfying Condition H1of Theorem3.1.Then,Theorems3.1and

3.2would guarantee that D Sω(L)?C Wζ1

ω(L)?Kπ/32

(L)?

C Wζ2

(L)for any distribution of weights of relative ampli-

tude at mostˉω,whereζ1=2(1?ˉω2)sinθ

5ε=3

sinπ

εand

ζ2=7sinπ/32

2(1?sinπ/32)

ε.We could then apply the pumping strat-

egy of[10]to C Wζ2

(L),which would remove allˉ -slivers

from C Wζ2

ω(L)(and hence from Kπ/32

(L))provided thatˉ is

su?ciently small.As a result,C Wζ1

ω(L)would coincide with

D Sω(L)and be homeomorphic to S,by Theorem2.5. Unfortunately,sinceδand rch(S)are unknown,?nding an ε≤cˉ rch(S)that provably satis?es H1can be di?cult,if not impossible.This is why we combine the above approach with the multi-scale reconstruction scheme of[21],which generates a monotonic sequence of samples L?W.Since L keeps growing during the process,εkeeps decreasing,even-tually satisfying H1ifδis small enough.At that stage, C Wζ1

(L)becomes homeomorphic to S,and thus a plateau

appears in the diagram of the Betti numbers of C Wζ1

ω(L),

showing the homology type of S–some examples can be found in[21].

Note that the only assumption made on the input point set W is that it is aδ-sample of some manifold,for some small enoughδ.In particular,W is not assumed to be a sparse δ-sample.As a result,W may well-sample several manifolds S1,···,S l,as it is the case for instance in the example of Figure1.In such a situation,the valuesδ1,···,δl for which W is aδi-sample of S i di?er,and they generate distinct

plateaus in the diagram of the Betti numbers of C Wζ1

ω(L)–

see Figure1.

4.2The algorithm

The input is a?nite point set W?R d.Initially,L=?andε=ζ1=ζ2=+∞.

At each iteration,the point p∈W lying furthest away5 from L in the Euclidean metric is inserted in L and pumped. Speci?cally,once p has been appended to L,its weightω(p) is set to zero,andεis set to max w∈W min v∈L w?v .

C Wζ1ω(L)and C Wζ2

(L)are updated accordingly,ζ1andζ2

being de?ned as in Section4.1.Then,p is pumped:the pumping procedure Pump(p)determines the weightωp of p that maximizes the minimum sliver measure among the 5At the?rst iteration,since L is empty,p is chosen arbitrar-ily in W.simplices of the star of p in C Wζ2

(L).After the pumping,

ω(p)is increased toωp,and C Wζ1

(L),C Wζ2

(L)are updated. The algorithm terminates when L=W.The output is the

one-parameter family of complexes C Wζ1

(L)built through-out the process.It is in fact su?cient to output the diagram of their Betti numbers,computed on the?y using the per-sistence algorithm of[29].With this diagram,the user can determine the scale at which to process the data:it is then easy to generate the corresponding subset of weighted land-marks(the points of W have been sorted according to their order of insertion in L,and their weights have been stored) and to rebuild its weighted witness complex relative to Wζ1.

Input:W?R d?nite.

Init:Let L:=?;ε:=+∞;ζ1:=+∞;ζ2:=+∞;

While L W do

Let p:=argmax w∈W min v∈L w?v ;

//p is chosen arbitrarily in W if L=?

L:=L∪{p};ω(p):=0;

ε:=max w∈W min v∈L w?v ;

ζ1:=3

sinπ

ε;ζ2:=7sinπ/32

2(1?sinπ/32)

ε;

Update C Wζ1

(L)and C Wζ2

(L);

ω(p):=Pump(p);

Update C Wζ1

(L)and C Wζ2

(L);

End while

Output:the sequence of complexes C Wζ1

(L)ob-tained after every iteration of the While loop.

Figure2:Pseudo-code of the algorithm.

The pseudo-code of the algorithm is given in Figure2.

The pumping procedure is the same as in[12],with Kπ/32

(L)

replaced by C Wζ2

(L).Given a point p just inserted in L,of weightω(p)=0,Pump(p)progressively increases the weight of p up toˉωmin{ p?v||,v∈L\{p}},while maintaining

the star of p in C Wζ2

(L).The combinatorial structure of the star changes only at a?nite set of event times.Between consecutive event times,the minimum sliver measure among the simplices of the star is constant and therefore computed once.In the end,the procedure returns an arbitrary value ωp in the range of weights that maximized the minimum sliver measure in the star of p.

4.3Theoretical guarantees

Assume that the input point set W is aδ-sample of some unknown manifold S.For any i>0,let L(i),ω(i),ε(i),ζ1(i),ζ2(i)denote respectively L,ω,ε,ζ1,ζ2at the end of the i th iteration of the main loop of the algorithm.Since L(i)grows with i,ε(i)is a decreasing function of i.More-over,since the algorithm always inserts in L the point of W lying furthest away from L,it is easily seen that L(i)is an ε(i)-sparseε(i)-sample of W[21,Lemma4.1].

Theorem 4.1.C Wζ1(i)

ω(i)

(L(i))coincides with D Sω(i)(L(i)) and is homeomorphic to S wheneverε(i)≤cˉ rch(S)satis-?es H1,which eventually happens during the course of the algorithm ifδis small enough.

The proof of the theorem uses the following intermediate result,whose proof(omitted here)is roughly the same as in Section8of[12]:

Lemma4.2.Wheneverδ≤ε(i)≤2rch(S)?δ,the star of p(i)in C Wζ2(i)

ω(i)

(L(i))contains noˉ -sliver.

Proof of Theorem 4.1.Let i>0be an iteration such thatε(i)≤cˉ rch(S)satis?es H1.Then,ζ1(i)=

2(1?ˉω2)sinθ

5ε(i)satis?es H2,andζ2(i)=7sinπ/32

2(1?sinπ/32)

ε(i)

satis?es the hypothesis of Theorem3.2.Since W is aδ-sample of S by assumption,and since L(i)is anε(i)-sparse

ε(i)-sample of W,Theorems3.1and3.2imply that D Sω(i)(L(i))?

C Wζ1(i)ω(i)(L(i))?Kπ/32

ω(i)

(L(i))?C Wζ2(i)

ω(i)

(L(i)).Let us show

that Kπ/32

ω(i)

(L(i))contains noˉ -sliver,which by Theorem2.5

will give the result.In fact,we will prove that C Wζ2(i)

ω(i)

(L(i))

contains noˉ -sliver,which is su?cient because Kπ/32

ω(i)

(L(i))?

C Wζ2(i)

ω(i)

(L(i)).Sinceε(i)satis?es H1,we haveδ≤ε(i)≤2rch(S)

7d?1

?δ.Therefore,Lemma4.2guarantees that the star

of p(i)in C Wζ2(i)

ω(i)

(L(i))contains noˉ -sliver.However,this

does not mean that C Wζ2(i)

ω(i)(L(i))itself contains noˉ -sliver,

because some of the points of L(i)were pumped at early stages of the course of the algorithm,when the assumption of Lemma4.2was not yet satis?ed.

Let i0≤i be the?rst iteration such thatε(i0)≤2rch(S)

7d?1?

δ.For any iteration j between i0and i,we haveε(j)≤

ε(i0)≤2rch(S)

7d?1?δandε(j)≥ε(i)≥δ,hence Lemma4.2

guarantees that the pumping procedure removes allˉ -slivers from the star of p(j)in C Wζ2(j)

ω(j)

(L(j))at iteration j.For any

k between j and i,the update of C Wζ2

ω(L)after the pumping

of p(k)may modify the star of p(j).However,since the pumping of p(k)only increases its weight,the new simplices in the star of p(j)belong also to the star of p(k),which contains noˉ -sliver,by Lemma4.2.Therefore,the star of

p(j)in C Wζ2(i)

ω(i)(L(i))still contains noˉ -sliver.

Consider now an iteration j≤i0?1.Sinceε(j)is greater than2rch(S)?δ,we cannot ensure that the star of p(j)in C Wζ2(j)

ω(j)

(L(j))contains noˉ -sliver.However,we claim that

the points of L(i)that are neighbors of p(j)in C Wζ2(i)

ω(i)(L(i))

were inserted in L on or after iteration i0.Indeed,for any such neighbor q,there is a point c∈Wζ2(i)thatω(i)-witnesses edge[p(j),q].According to Lemma3.5(i), c?p(j) and c?q are at most c1(1)ε(i).Hence,we have p(j)?q ≤ p(j)?c + c?q ≤2c1(1)ε(i).Now,recall that L(i0?1)isε(i0?1)-sparse,whereε(i0?1)>2rch(S)?δ, which by H1is greater than2c1(1)ε(i).It follows that q cannot belong to L(i0?1),since p(j)does.Hence,the star of q in C Wζ2(i)

ω(i)

(L(i))contains noˉ -sliver.Since this is true for

any neighbor q of p(j)in C Wζ2(i)

ω(i)(L(i)),the star of p(j)does

not contain anyˉ -sliver either.This concludes the proof of Theorem4.1.

4.4Discussion

Theorem4.1guarantees the existence of a plateau in the

diagram of the Betti numbers of C Wζ1

ω(L),but it does not

tell exactly where this plateau is located in the diagram, becauseδand rch(S)are unknown.Nevertheless,it does give a guarantee on the length of the plateau,which,in view of H1,is of the order of(a rch(S)?bδ),where a,b are two constants.Hence,for su?ciently smallδ,the plateau is long enough to be detected by the user or some statistical method applied in a post-processing step.If W samples several manifolds,then several plateaus may appear in the diagram:each one of them shows a plausible reconstruction, depending on the scale at which the data set W is processed. Observe that the structural results of Section3still hold6 if we relax the assumption on W and allow its points to lie slightly o?the manifold,at a Hausdor?distance ofδ.This gives a deeper meaning to Theorem4.1,which now guaran-tees that the algorithm generates a plateau whenever there exists a manifold S that is well-sampled by L and that passes close to the points of W.This holds in particular for small deformations S of the manifold S0from which the points of W have been drawn:the consequence is that the topo-logical features of S0(connected components,handles,etc.) are captured progressively by the algorithm,by decreasing order of size in the ambient space.For instance,if S0is a double torus whose handles have signi?cantly di?erent sizes, then the algorithm?rst detects the larger handle,generat-ing a plateau withβ0=β2=1andβ1=2,then later on it detects also the smaller handle,generating a new plateau withβ0=β2=1andβ1=4.This property,illustrated in the experimental section of[21],enlarges greatly the range of applications of our method.

Note?nally that our theoretical guarantees still hold if

C Wζ1

(L)and C Wζ2

(L)are replaced by D Wζ1

(L)and D Wζ2

(L) respectively.This means that the algorithm can use indi?er-ently the weak witness complex or the strong witness com-plex,with similar theoretical guarantees.

4.5Details of the implementation

Before we can analyze the complexity of the algorithm, we need to give some details on how its various components can be implemented.

4.5.1Update of the witness complex

Although the algorithm is conceptually simple,its im-

plementation requires to be able to update C Wζ

(L),where ζ∈{ζ1,ζ2}.This task is signi?cantly more di?cult than updating C Wω(L),mainly because Wζis not?nite,which makes it impossible to perform theω-witness test of De?ni-tion2.1on every single point of Wζindividually.However, since we are working in Euclidean space R d,for any w∈W it is actually possible to perform theω-witness test on the whole ball B(w,ζ)at once.Each time a point is inserted

in L or its weight is increased,C Wζ

(L)is updated by iter-ating over the points w∈W and performing theω-witness test on B(w,ζ).This test boils down to intersecting B(w,ζ) with the weighted Voronoi diagrams of L of orders1through d+1.In the space of spheres R d+1,this is equivalent to in-tersecting a vertical cylinder of base B(w,ζ)with the cells of an arrangement of|L|hyperplanes,which is a costly opera-tion.Fortunately,as shown below,we can restrict ourselves to constructing the arrangement of the hyperplanes of the κ(d)nearest landmarks of w in the Euclidean metric,where κ(d)=(2+2c1(d))d.This means that we do not actually

maintain C Wζ

(L),but another complex C,which might not

contain C Wζ

(L)nor be contained in it.Nevertheless,

6Wζstill covers S whenζ≥δ,and the proof that C Wζ

(L)?

Kθω(L)holds the same,with an additional termδin the bounds of Lemmas3.3through3.6.

Lemma4.3.C(i)coincides with C Wζ(i)

ω(i)(L(i))whenever

ε(i)satis?es H1.

Proof.Let w be a point of W,and letΛ(w)?L(i)de-note the set of itsκ(d)nearest landmarks in the Euclidean metric.For any point c∈B(w,ζ(i))and any positive in-teger k≤d,Lemma3.5(i)ensures that the k+1nearest landmarks of c in the weighted metric,p0,···,p k,belong to B(c,c1(d)ε(i)).Since w?c ≤ζ(i),p0,···,p k belong to B(w,r(i)),where r(i)=ε(i)(c1(d)+ζ(i)/ε(i)).Now,L(i)is ε(i)-sparse,hence the points of L(i)∩B(w,r(i))are centers of pairwise-disjoint balls of radiusε(i)/2.These balls are in-cluded in B(w,r(i)+ε(i)/2),thus their number is at most (1+2r(i)/ε(i))d=(1+2c1(d)+2ζ(i)/ε(i))d,which is bounded byκ(d)sinceζ(i)≤ζ2(i)<ε(i)/2.Therefore,p0,···,p k belong toΛ(w).As a result,in the weighted metric,the k+1nearest neighbors of c inΛ(w)are the same as its k+1 nearest neighbors in L(i).Since this is true for any w∈W and any c∈B(w,ζ(i)),and since all the balls of radiusζ(i) centered at the points of W are tested at each update of the complex,C(i)coincides with C Wζ(i)

ω(i)

(L(i)).

It follows from this lemma that our guarantees on the out-

put of the algorithm still hold if C Wζ

ω(L)is replaced by C.

Note also that,since any arrangement ofκ(d)hyperplanes in R d+1has O`κ(d)d+1′=d O(d2)cells[18],each point of W generates at most d O(d2)simplices in C.It follows that the size of our complex is bounded by|W|d O(d2).The same bound clearly holds for the time spent updating C after a point insertion or a weight increase,provided that theκ(d) nearest landmarks of a witness can be computed in d O(d2) time.In practice,we maintain the lists ofκ(d)nearest land-marks of the witnesses in parallel to C.Each time a new point is inserted in L,the list of each witness is updated in O(κ(d))time as we iterate over all the witnesses to up-date https://www.wendangku.net/doc/73712725.html,ing these lists,we can retrieve theκ(d)nearest landmarks of any witness in time O(κ(d))=d O(d2).

4.5.2Pumping procedure

As mentioned in Section4.2,only a?nite number of events occur while a point p∈L is being pumped.The sequence of events can be precomputed before the beginning of the pumping process,by iterating over the points of W that have p among theirκ(d)nearest landmarks.For each such point w,we detect the sequence of simplices incident to p that start or stop beingω-witnessed by points of B(w,ζ2)as the weight of p increases.In the space of spheres R d+1,this is equivalent to looking at how the cells of the arrangement ofκ(d)hyperplanes evolve as the hyperplane of p translates vertically.The number of events that are generated by a point of W is of the order of the size of the arrangement of κ(d)hyperplanes in R d+1,hence the total number of events is at most|W|d O(d2),and the time spent computing them is also bounded by|W|d O(d2).

For the sake of e?ciency,we need to reduce the size of the sequence of events to d O(d2)before any further processing. To this end,we prune out most of the events,keeping only those involving simplices whose vertices belong to theκ(d) nearest neighbors of p among L in the Euclidean metric.By the same argument as above,there are at most d O(d2)such simplices.Nevertheless,the sequence of events may still be much larger,because a simplex may appear in or disappear from the star of p several times7.To bound the total number of events,for each simplexσwe report only the?rst time whereσappears in the star of p and the last time where it disappears from the star of p.Thus,the number of events reported per simplex is at most two,which implies that the total number of events reported is bounded by d O(d2). Once the sequence of events has been computed and sim-pli?ed,the pumping procedure iterates over the events.At each iteration,the weight of p is increased,and C Wζ2

(L) (or rather the complex C of Section4.5.1)is updated.The minimum sliver measure in the star of p is computed on the ?y,during the update of C.The number of iterations of the pumping procedure is precisely the number of events, bounded by d O(d2).At each iteration,the update of C takes time at most|W|d O(d2),which also includes the computation of the minimum sliver measure in the star of p.All in all, the time complexity of the pumping procedure is bounded by|W|d O(d2).

The downside is that the pumping procedure works with a wrong sequence of events,since some events have been dis-carded during the precomputation.As a result,the pump-ing process may not remove all theˉ -slivers from the star of p.Nevertheless,wheneverε(i)≤cˉ rch(S)satis?es H1,no simplex is discarded during the precomputation phase,by an argument similar to the one used in the proof of Lemma 4.3.Furthermore,Lemma4.2still holds,with exactly the same proof–described in Section8of[12]and omitted here. Hence,Theorem4.1still applies.

4.5.3Computation of p andε

At each iteration of the main loop of the algorithm,the computation of p=argmax w∈W min v∈L w?v andε= max w∈W min v∈L w?v is done naively by iterating over the points of W and computing their Euclidean distance to L.This takes O(|W|)time once the sets ofκ(d)nearest landmarks have been updated.

4.6Complexity of the algorithm

Theorem 4.4.The space and time complexities of the al-gorithm are respectively|W|d O(d2)and|W|2d O(d2).

Proof.As reported in Section4.5.1,the size of the com-plex maintained by the algorithm never exceeds|W|d O(d2), therefore the space complexity of the algorithm is at most |W|d O(d2).At each iteration of the main loop of the algo-rithm,the computation of p andεtakes O(|W|)time,ac-cording to Section4.5.3,and the pumping of p takes|W|d O(d2)

time,by Section4.5.2.Moreover,each update of C Wζ1

(L)

and C Wζ2

(L)takes d O(d2)time,by Section4.5.1.Therefore, the time spent during each iteration of the main loop of the algorithm is at most|W|d O(d2).It follows that the time complexity of the algorithm is bounded by|W|2d O(d2),since the number of iterations of the main loop of the algorithm is|W|.

Note that the bounds of Theorem4.4do not take into ac-count the(optional)computation of the Betti numbers of 7The cell of a k-simplexσin the weighted Voronoi diagram of L of order k+1evolves as the weight of p increases, and therefore it may intersect Wζseveral times during the process,since Wζis not convex.

C Wζ1(i)ω(i)(L(i))at each iteration of the algorithm,which can

take a time cubic in the size of the complex[29].

5.CONCLUSION

We have proved that the structural properties of the wit-ness complex on low-dimensional manifolds can be extended to manifolds of arbitrary dimensions and co-dimensions.To avoid pathological cases generated by slivers,we have as-signed weights to the landmarks,so that,for carefully-chosen distributions of weights,the witness complex is included in the weighted restricted Delaunay triangulation,which is homeomorphic to the underlying manifold.Moreover,both complexes coincide if the set of witnesses is dilated by a ball of suitable radius.We have also introduced a conceptu-ally simple reconstruction algorithm,based on the witness complex,which combines a farthest-point re?nement scheme with a vertex pumping https://www.wendangku.net/doc/73712725.html,ing our structural re-sults,we have proved the correctness of the algorithm when applied to su?ciently dense samplings of smooth manifolds. These mild assumptions on the input make the approach rel-evant on practical data,even though constructing arrange-ments of hyperplanes is not desirable in practice.We also believe the approach is generic enough to be applicable to related problems,such as manifold sampling and meshing. Note that our structural results still hold in the somewhat more general setting where W is an adaptiveδ-sample of S, in the sense of[1],and where L is an(ε,κ)-sample of W,in the sense of[12].The proofs are roughly the same,with an additional twist which slightly degrades the constants. 6.ACKNOWLEDGEMENTS

The authors thank the anonymous referees for their in-sightful comments.The?rst author was supported in part by the Program of the EU as Shared-cost RTD(FET Open) Project under Contract No IST-006413(ACS Algorithms for Complex Shapes).The second and third authors were supported by NSF grants FRG-0354543and ITR-0205671, by NIH grant GM-072970,and by DARPA grant32905. 7.REFERENCES

[1]N.Amenta and M.Bern.Surface reconstruction by Voronoi

?ltering.Discrete Comput.Geom.,22(4):481–504,1999. [2]N.Amenta,M.Bern,and D.Eppstein.The crust and the

β-skeleton:Combinatorial curve reconstruction.Graphical Models and Image Processing,60:125–135,1998.

[3] D.Attali,H.Edelsbrunner,and https://www.wendangku.net/doc/73712725.html,eyko.Weak witnesses

for Delaunay triangulations of submanifolds.In Proc.ACM Sympos.on Solid and Physical Modeling,2007.To appear.

[4]M.Belkin and P.Niyogi.Semi-supervised learning on

Riemannian manifolds.Machine Learning,56(1-3):209–239, 2004.

[5]J.-D.Boissonnat and S.Oudot.Provably good sampling

and meshing of Lipschitz surfaces.In Proc.22nd Annu.

https://www.wendangku.net/doc/73712725.html,put.Geom.,pages337–346,2006.

[6] F.Cazals and J.Giesen.Delaunay triangulation based

surface reconstruction.In J.D.Boissonnat and M.Teillaud, editors,E?ective Computational Geometry for Curves and Surfaces,pages231–273.Springer,2006.

[7] F.Chazal,D.Cohen-Steiner,and A.Lieutier.A sampling

theory for compact sets in Euclidean space.In Proc.22nd

Annu.ACM https://www.wendangku.net/doc/73712725.html,put.Geom.,pages319–326,

2006.

[8] F.Chazal and A.Lieutier.Weak feature size and persistent

homology:Computing homology of solids in R n from noisy

data samples.In Proc.21st Annual ACM Symposium on

Computational Geometry,pages255–262,2005.

[9] F.Chazal and A.Lieutier.Topology guaranteeing manifold

reconstruction using distance function to noisy data.In

Proc.22nd Annu.Sympos.on Comput.Geom.,pages

112–118,2006.

[10]S.-W.Cheng,T.K.Dey,H.Edelsbrunner,M.A.Facello,

and S.-H.Teng.Sliver exudation.Journal of the ACM,

47(5):883–904,2000.

[11]S.-W.Cheng,T.K.Dey,and E.A.Ramos.Manifold

reconstruction from point samples.Journal version,in

preparation.

[12]S.-W.Cheng,T.K.Dey,and E.A.Ramos.Manifold

reconstruction from point samples.In Proc.16th Sympos.

Discrete Algorithms,pages1018–1027,2005.

[13] D.Cohen-Steiner,H.Edelsbrunner,and J.Harer.Stability

of persistence diagrams.In Proc.21st Annu.ACM Sympos.

Comput.Geom.,pages263–271,2005.

[14]V.de Silva.A weak de?nition of Delaunay triangulation.

Manuscript.Preprint available at

https://www.wendangku.net/doc/73712725.html,/comptop/preprints/weak.pdf, October2003.

[15]V.de Silva and G.Carlsson.Topological estimation using

witness complexes.In Proc.Sympos.Point-Based

Graphics,pages157–166,2004.

[16] D.DeMers and G.Cottrell.Nonlinear dimensionality

reduction.Advances in Neural Information Processing

Systems5,pages580–587,1993.

[17]T.K.Dey,J.Giesen,S.Goswami,and W.Zhao.Shape

dimension and approximation from samples.Discrete and

Computational Geometry,29:419–434,2003.

[18]H.Edelsbrunner.Algorithms in Combinatorial Geometry,

volume10of EATCS Monographs on Theoretical Computer Science.Springer-Verlag,1987.

[19]H.Edelsbrunner.Geometry and Topology for Mesh

Generation.Cambridge,2001.

[20]J.Giesen and U.Wagner.Shape dimension and intrinsic

metric from samples of manifolds with high co-dimension.

Discrete and Computational Geometry,32:245–267,2004.

[21]L.G.Guibas and S.Y.Oudot.Reconstruction using

witness complexes.In Proc.18th ACM-SIAM Sympos.on Discrete Algorithms,pages1076–1085,2007.

[22] A.B.Lee,K.S.Pederson,and D.Mumford.The nonlinear

statistics of high-contrast patches in natural images.

Internat.J.of Computer Vision,54(1-3):83–103,2003. [23]P.Niyogi,S.Smale,and S.Weinberger.Finding the

homology of submanifolds with high con?dence from

random samples.Discrete Comput.Geom.,to appear. [24]S.Y.Oudot.On the topology of the restricted Delaunay

triangulation and witness complex in higher dimensions.

Manuscript.Preprint available at http://geometry.

https://www.wendangku.net/doc/73712725.html,/member/oudot/drafts/Delaunay_hd.pdf,

November2006.

[25]S.T.Roweis and L.K.Saul.Nonlinear dimensionality

reduction by locally linear embedding.Science,

290(5500):2323–2326,2000.

[26]M.-J.Seow,R.C.Tompkins,and V.K.Asari.A new

nonlinear dimensionality reduction technique for pose and

lighting invariant face recognition.In Proc.IEEE Conf.on Computer Vision and Pattern Recognition-Workshops,

page160,2005.

[27]J.B.Tenenbaum,V.de Silva,and https://www.wendangku.net/doc/73712725.html,ngford.A global

geometric framework for nonlinear dimensionality

reduction.Science,290(5500):2319–2323,2000.

[28]M.Vlachos,C.Domeniconi,D.Gunopulos,G.Kollios,and

N.Koudas.Non-linear dimensionality reduction techniques for classi?cation and visualization.In Proc.8th ACM

SIGKDD Internat.Conf.on Knowledge discovery and data mining,pages645–651,2002.

[29] A.Zomorodian and https://www.wendangku.net/doc/73712725.html,puting persistent

homology.Discrete Comput.Geom.,33(2):249–274,2005.