An Effective Condition for Sampling Surfaces with Guarantees

(1)

G. Elber, N. Patrikalakis, P. Brunet (Editors)

An Effective Condition for Sampling Surfaces with Guarantees

J-D Boissonnat and S. Oudot

INRIA, 2004 route des lucioles, 06902 Sophia-Antipolis, France. {Jean-Daniel.Boissonnat, Steve.Oudot}@sophia.inria.fr

Abstract

The notion ofε-sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces.

Of particular interest is the fact that, if E is anε-sample of a smooth surface S for a sufficiently smallε, then the Delaunay triangulation of E restricted to S is a good approximation of S, both in a topological and in a geometric sense. Hence, if one can construct anε-sample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms.

In this paper, we introduce the notion of looseε-sample. We show that the set of looseε-samples contains and is asymptotically identical to the set ofε-samples. The main advantage of looseε-samples overε-samples is that they are easier to check and to construct. We also present a simple algorithm that constructs provably good surface samples and meshes.

Categories and Subject Descriptors(according to ACM CCS): I.3.5 [Computer Graphics]: Curve, surface, solid, and object repre- sentations

This work has been partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG - Effective Computational Geometry for Curves and Surfaces).

1. Introduction

Meshing and reconstructing surfaces are two fundamental prob- lems in geometry processing. In surface reconstruction, a finite set of pointsE on a surfaceSis given and one wants to compute a good approximation ofSfromE. This is of course only possible if Eis a good sample ofSin some sense. In surface mesh generation, the problem is somehow opposite. A surfaceSis known and we want to compute a triangulated surface that suitably approximates S. Clearly, the vertices of the triangulated surface have to sample correctlyS. Hence, in both applications and also in many others, including the new arena of point set surfaces [1, 2], the notion of good sample is crucial.

The notion ofε-sample, as introduced by Amenta and Bern [3], has proven to be a key concept in the theory of sampled surfaces.

Roughly, anε-sampleE of a surfaceSis a (non necessarily uni- form) point set that is sufficiently dense with respect to thedistance to the medial axisofS– see section 2. Of particular interest is the fact that ifEis anε-sample of a smooth surfaceSfor a sufficiently smallε, the Delaunay triangulation ofErestricted toS, Del_|_S(E), is a good approximation ofS, both in a topological and in a geometric sense (see section 2 for more details). Hence, given anε-sample of a surface, it is easy to get a good approximation of the surface.

This result (and variants of it) plays a central role in the analysis

of all surface reconstruction algorithms that offer theoretical guarantees [9]. In particular, ifEis anε-sample of a smooth surfaceS for a sufficiently smallε, these algorithms can reconstruct a surface that has the same topology type asSand is close toS.

One drawback of the concept ofε-sample is the fact that it is difficult to check whether a sample is anε-sample of a given surface, and even more difficult to construct a (preferably sparse)ε-sample of a given surface. This is due to the fact that a direct application of the definition of anε-sample leads to complicated operations like cutting the surface with balls.

In this paper, we introduce the notion of looseε-sample. The set of looseε-samples contains and is asymptotically identical to the set ofε-samples. The main advantage of looseε-samples overε- samples is that they are easier to check and to construct. Indeed, checking that a sample is a loose ε-sample reduces to checking whether a finite number of spheres are small enough with respect to the distance from their centers to the medial axis of the surface.

We also present a construction algorithm which is a variant of Chew’s surface meshing algorithm [14]. Given a smooth closed sur- faceS, the algorithm generates a sparseε-sampleEand at the same time a triangulated surface Del_|_S(E). The triangulated surface has the same topological type asS, is close toSfor the Hausdorff distance (see theorem 4.8) and can provide good approximations of normals, areas and curvatures. A remarkable feature of the algorithm is that the surface needs only to be known through an oracle that, given a line segment, detects whether the segment intersects the surface and, in the affirmative, returns an intersection point and the distance to the medial axis at that point (or any smaller non-

(2)

zero quantity). This makes the algorithm useful in a wide variety of contexts and for a large class of surfaces.

The paper is organized as follows. In section 2, we recall useful concepts and introduce the notion of looseε-sample. In section 3, we present some local properties of looseε-samples that are used in section 4 to establish our main results. We prove that, for sufficiently smallε, Del_|S(E)is a 2-manifold without boundary that is ambient isotopic toSand whose Hausdorff distance toSisO(ε²).

We also prove thatSis covered by the so-called surface Delaunay balls, and that looseε-samples areε(1+16ε)-samples. In section 5, we bound the size of looseε-samples. As an application of our results, we present in section 6 our surface mesh generator.

2. Definitions and preliminary observations

In the paper,Sdenotes a compact, orientable, twice-differentiable surface without boundary.Swill be called a smooth closed surface for short. By−→n(p)we denote the surface normal at pointp∈S, and byT(p)the plane tangent toSatp.

Our analysis uses the fact that locally a smooth surface is the graph of a function. More precisely, given an orthonormal frame (O,x,y,z)ofR³, a subset ofR³is said to bexy-monotoneif it is the graph of a function of the two variablesxandy. Aterrainis a surface that isxy-monotone in some frame(O,x,y,z)ofR³. Similarly, given an orthonormal frame(O,x,y)ofR², a subset ofR²is said to bex-monotoneif it is the graph of a function of variablex.

2.1. Restricted Delaunay triangulation

In the paper,Edenotes a finite point sample ofSand Del(E)the 3- dimensional Delaunay triangulation ofE. ByV(E)we denote the set of the edges of the Voronoi diagram ofE.

We call Delaunay triangulation ofE restricted to S, and we note Del_|_S(E), the sub-complex of Del(E)that consists of the facets of Del(E)whose dual Voronoi edges intersectS. An edge or vertex of Del(E)belongs to Del_|S(E)if it is incident to at least one facet of Del_|_S(E). Notice that we depart from the usual definition [14, 19]

and do not consider vertices and edges with no incident facet of Del_|_S(E).

A facet (resp. edge, vertex) of Del_|_S(E)is called arestricted De- launay facet(resp.restricted Delaunay edge,restricted Delaunay vertex). For a restricted Delaunay facet f, we callsurface Delau- nay ballof f any ball circumscribing f centered at some point of S∩f^∗, where f^∗ is the Voronoi edge dual to f. We callsurface Delaunay patchthe intersection of a surface Delaunay ball withS.

Notice that the centers of the surface Delaunay balls are precisely the intersection points ofSandV(E).

2.2. ε-samples and looseε-samples

Themedial axisofS, denoted byM, is the topological closure of the set of points ofR³that have more than one nearest neighbour inS.

For a pointx∈R³, we calldistance to the medial axisatx, and writedM(x), the Euclidean distance fromxto the medial axis ofS.

As noticed by Amenta and Bern [3], dM is 1-Lipschitz, i.e.

|dM(x)−dM(y)| ≤ kx−yk.

We define d_M^inf = inf{dM(x),x∈S} and d_M^sup = sup{dM(x),x∈S}. Since S is a smooth closed surface, both d^inf_M andd^sup_M are finite and strictly positive constants.

We borrow from Amenta and Bern [3] the notion ofε-sample, defined below. In the whole paper,B(c,r)denotes the ball of center cand radiusr.

Definition 2.1Eis anε-sampleofSif∀x∈S,E∩B(x,εdM(x))6=

∅.

For sufficiently small values ofε,ε-samples enjoy many beautiful properties. We recall the most important ones in our context.

– Normals:the angle between the normal to a facet fof Del_|S(E) and the normal toSat the vertices offisO(ε)[3].

– Area:the area of Del_|S(E)approximates the area ofS[25].

– Curvatures: the curvature tensor of S can be estimated from Del_|S(E)[15].

– Homeomorphism:Del_|_S(E)is homeomorphic toS[3].

– Hausdorff distance: the Hausdorff distance between S and Del_|_S(E) isO(ε) [10]. In this paper, we give anO(ε²)bound (theorem 4.8).

– Reconstruction:several algorithms can reconstruct fromEa surface that is homeomorphic [3, 4, 9, 17] or even ambient isotopic [6] toS.

We will show that these properties hold for looseε-samples as well.

Definition 2.2E is alooseε-sampleofSif∀x∈S∩ V(E), E∩ B(x,εdM(x))6=∅.

Since the centers of the surface Delaunay balls are precisely the intersection points ofSwith the Voronoi edges,E is a loose ε-sample if and only if every surface Delaunay ballB(c,r)has a radius of at mostεdM(c).

ε-samples and looseε-samples are closely related but not identical concepts. The next lemma follows from definitions 2.1 and 2.2.

Lemma 2.3IfEis anε-sample, then it is a looseε-sample.

The converse is true asymptotically, as we will see in section 4.3 (corollary 4.13).

2.3. Other notations

The following constants are used in the paper:

• ε₀ is the only positive root of equation _1−8ε^2ε +arcsin_1−ε^ε −

π4 = 0.ε₀≈0.091.

•ε1is the only positive root of equation_1−7ε^2ε +arcsin^ε_1−ε^√³−^π₄=0.

ε1≈0.096.

•ε2=_4+9π^π ≈0.097.

• ε3 is the only positive root of equation _1−5ε^ε +arcsin^ε_1−ε^√³−

π2 = 0.ε3≈0.17.

• ε4 is the only positive root of equation _1−4ε^2ε +arcsin^ε_1−ε^√³−

π4 = 0.ε4≈0.12.

We also use the notation(−→u,−→v)to denote the modulus of the angle (measured in[−π,π]) between vectors−→u and−→v ofR³, and

−

→u.−→v to denote their dot-product.

102

(3)

3. Local properties of looseε-samples

In this section, we prove that surface Delaunay balls of sufficiently small radii keep important properties of planar disks. In particular, we show that they intersectSalong topological disks whose boundaries pairwise intersect in at most two points (proposition 3.9).

3.1. Technical lemmas

In this paragraph, we recall several lemmas by Amenta and Bern [3] that will be useful in the remainder of the paper.

Lemma 3.1 Let fbe a facet of Del_|_S(E). Assume that every surface Delaunay ballB(c,r)offis such thatr≤ρdM(c), withρ<¹₇. Letabe a vertex off. Ifahas an inner angle of at leastπ/3, then the smaller angle between the line normal tofand the normal toSata is at most arcsin^ρ_1−ρ^√³. Otherwise, the smaller angle between the line normal to fand the normal toSatais at most_1−7ρ^2ρ +arcsin^ρ_1−ρ^√³. Proof The radius of any surface Delaunay ball of f is at most

1−ρρ dM(a), thus the proof of lemma 7 of Amenta and Bern [3]

holds here.

Lemma 3.2 For any two points p and qon Swith kp−qk ≤ ρ dM(p), the smaller angle between the line segment pqand the surface normal atpis at least^π₂−arcsin^ρ₂.

Lemma 3.3 For any two points p and qon Swith kp−qk ≤ ρ min{dM(p),dM(q)}, for anyρ< ¹₃, the angle between the normals toSatpand atqis at most _1−3ρ^ρ .

We will need the two following corollaries of the above lemmas.

Lemma 3.4Letcandc⁰ be two points ofSsuch thatkc−c⁰k ≤ ε(dM(c) +dM(c⁰)), whereε<¹₈. There exists a vector−→v orthogonal to−→

cc⁰, such that the angle between−→v and the normal toSat any point ofS∩B(c,2εdM(c))is at most _1−8ε^2ε +arcsin_1−ε^ε . Hence, if ε≤ε₀, this angle is at most ^π₄.

Proof LetB⁺=B(c,2εdM(c)). We have

∀x∈B⁺∩S,kx−ck ≤2εdM(c) (1) thus

∀x∈B⁺∩S,dM(x) ≥dM(c)− kx−ck

≥(1−2ε)dM(c) (2) (1) and (2) give

∀x∈B⁺∩S,kx−ck ≤ 2ε

1−2ε min{dM(c),dM(x)} which implies, according to lemma 3.3,

∀x∈B⁺∩S,(−→n(x),−→n(c))≤ 2ε/(1−2ε)

1−6ε/(1−2ε) = 2ε 1−8ε We havekc−c⁰k ≤εdM(c) +εdM(c⁰)≤2εdM(c) +εkc−c⁰k, i.e.kc−c⁰k ≤_1−ε^2ε dM(c). Thus, lemma 3.2 tells that

min{(−→

cc⁰,−→n(c)),(−→n(c),−→ cc⁰)} ≥π

2−arcsin ε

1−ε (3) Inside plane(c,−→

cc⁰,−→n(c)), let−→v be the unitary vector that is orthogonal to−→

cc⁰and has a positive scalar product with−→n(c). Ac- cording to (3) we have(−→n(c),−→v)≤arcsin_1−ε^ε . Thus,

∀x∈S∩B⁺,(−→n(x),−→v) ≤(−→n(x),−→n(c)) + (−→n(c),−→v)

≤_1−8ε^2ε +arcsin_1−ε^ε

Lemma 3.5LetB=B(c,r)be a ball centered atc∈Sof radius r≤εdM(c), withε<¹₉, and letvbe a point ofS∩B. The normals toSatvand at any point ofS∩B(v,2r)make an angle of at most

1−9ε2ε . Hence, ifε<ε₂, this angle is less than^π₂and, by lemma 9.4, S∩B(v,2r)is a terrain.

Proof We haver≤εdM(c)≤ε (dM(v) +kv−ck), which is at mostε(dM(v) +r)sincevlies inB. Thus,r≤_1−ε^ε dM(v). There- fore,∀x∈S∩B(v,2r),

kx−vk ≤2r≤_1−ε^2ε dM(v)

≤_1−ε^2ε (dM(x) +kx−vk)

which implies kx−vk ≤ _1−3ε^2ε dM(x). It follows thatkx−vk ≤ ρmin{dM(x),dM(v)}, withρ= _1−3ε^2ε . Thus, according to lemma 3.3,

−

→n(x),−→n(v)

≤ ρ

1−3ρ= 2ε 1−9ε

3.2. Topological disks and terrains

Lemma 3.6 ([8])LetBbe a ball that intersectsS. If the intersection is not a topological disk, thenBcontains a point of the medial axis ofS. As a consequence, ifEis a looseε-sample, withε<1, then surface Delaunay patches are topological disks.

Lemma 3.7IfE is a loose ε-sample, withε<ε₂, then, for every surface Delaunay ball B=B(c,r), for any point x∈S∩B, S∩B(x,2r)is a topological disk and a terrain.

Proof Since E is a loose ε-sample, we have r ≤ε dM(c)≤ ε(dM(x) +kx−ck)≤ε(dM(x) +r), that is,r≤_1−ε^ε dM(x). Thus, 2r<dM(x)sinceε<ε₂<¹₃. According to lemma 3.6,S∩B(x,2r) is thus a topological disk. The fact thatS∩B(x,2r)is a terrain follows from lemma 3.5, sinceε<ε₂.

3.3. Pseudo-disks

Definition 3.8Topological disks are pseudo-disks if they pairwise intersect along topological disks (that may be empty or reduced to a point) and if their boundaries pairwise intersect in at most two points.

Observe that the boundaries of two pseudo-disks either do not intersect, or intersect in one point tangentially, or intersect in two points transversally.

Proposition 3.9IfEis a looseε-sample, withε≤ε₀, then surface Delaunay patches are pseudo-disks.

Proof LetB=B(c,r)andB⁰=B(c⁰,r⁰)be two surface Delaunay balls. According to lemma 3.6,D=B∩SandD⁰=B⁰∩Sare topological disks, sinceε≤ε₀<1. Their boundariesCandC⁰are topological circles. Let us assume that ballsBandB⁰intersect, the other case being trivial. Notice that none of them can be contained in the other one, since they are Delaunay balls. Thus, their bounding 103

(4)

P c z

y x

G

Γ

∆ Ll

Lr

Figure 1:Definition of G

P c Cone

z y x

G’

G

Figure 2:Definition of G⁰

spheres∂Band∂B⁰also intersect. LetΓbe the circle∂B∩∂B⁰,ρ its radius (ρ<min{r,r⁰}) andPits supporting plane. We define

∆=B∩Pand notice thatΓ=∂∆. SinceSis a closed surface, we haveC⊂∂BandC⁰⊂∂B⁰, which implies that

C∩C⁰⊆S∩Γ (4)

LetB⁺=B(c,2r). Sincekc−c⁰k ≤r+r⁰≤εdM(c) +εdM(c⁰), whereε≤ε0, by lemma 3.4 there exists a vector−→v orthogonal to

−→

cc⁰such that

∀x∈S∩B⁺,(−→n(x),−→v)≤π

4 (5)

Let us choose inR³a reference frame of originc, ofy-axis directed along−→

c⁰c, and ofz-axis directed along−→v. We callL_landLrthe two lines ofP, parallel to thez-axis, that are tangent toΓ. The region of Pbounded byLlandLris calledG(see figure 1). In the following, ξdenotesS∩B⁺∩G.

Lemma 3.10ξis a connectedx-monotone arc.

Proof According to (5), we have∀x∈S∩B⁺, (−→n(x),−→v)≤^π₄. Thus, by lemma 9.4, B⁺∩Sisxy-monotone, which implies that ξisx-monotone. Moreover, according to lemma 9.5,B⁺∩Slies outside the cone of apexc∈S, of vertical axis and of half-angle^π₄.

The equation of the cone in our frame isz²=x²+y². It intersects Palong two hyperbolic arcs of equationsz=±√

x²+d², where d≤ris the distance fromctoP. Consider the subregionG⁰ ofG that is bounded vertically by the two hyperbolic arcs (see figure 2).

SinceS∩B⁺lies outside the cone,ξis included inG⁰.

The points of G⁰ that are farthest from c are the points (±ρ,−d,±p

ρ²+d²). Their distance tocis q2(ρ²+d²)<2r

In other words, G⁰ ⊂int(B⁺). It follows that ξ is included in int(B⁺)and cannot intersect∂B⁺. Its endpoints must then lie on the vertical linesLr andLl. But there can be only one endpoint per vertical line, sinceξisx-monotone. Hence,ξhas at most two endpoints and is thus connected.

Lemma 3.11|S∩Γ| ≤2.

Proof Let us assume for a contradiction that|S∩Γ|>2. First, we show that there exists a point where the curvature ofξis high and hence the distance to the medial axisMis small. Then we work out a contradiction with the fact thatEis a looseε-sample, withε≤ε0. Claim 1There exists a pointqat which the curvature ofξis at least

1ρ.

Proof We made the assumption that|S∩Γ|>2. SinceΓ⊂Gand Γ⊂B⁺,ξalso intersectsΓmore than twice. And sinceξis connected by lemma 3.10, there is a subarcabofξthat lies outside∆ and whose endpointsaandblie onΓ. This subarc may be reduced to a point (a=b), sinceξmay be tangent toΓ. But in this case, in the vicinity ofa,ξis locally included in∆and tangent toΓata.

Thus, its curvature atais at least ¹_ρ, which proves the claim with q=a. So now we assume that arcabofξis not reduced to a point.

Sinceξisx-monotone by lemma 3.10,aandblie on the same half ofΓ, upper half or lower half (say upper half). Thus, the smaller arc ofΓthat joinsaandbis alsox-monotone. Then, by lemma 9.3, there is a pointqof arcabofξat which the curvature ofξis at least

1ρ, which proves the claim.

Claim 2dM(q)≤ρ√ 2.

Proof Let−→n_ξ(q)be the normal to planar curveξat pointq. By inequation (5),−→n(q)is not orthogonal toP, thus−→n_ξ(q)is oriented along the projection of−→n(q)ontoP. Hence, by lemma 9.2, we have (−→n(q),−→n_ξ(q))≤(−→n(q),−→v)which is at most^π₄by inequation (5).

According to theorem 9.1, we then have atq II(ξ⁰,ξ⁰)≥cosπ

4kξ⁰⁰k

ξ⁰is the unit tangent vector ofξatqandkξ⁰⁰kis the curvature ofξ atq, which is more than ¹_ρaccording to claim 1. So, atqwe have

II(ξ⁰,ξ⁰)≥ 1 ρ√

2 (6)

Recall thatIIis a symmetric bilinear form, thus it can be diago- nalized in an orthonormal frame, and its eigenvalues are the min- imum and maximum curvatures ofSatq. Let us call these val- uesκmin(q)andκmax(q)respectively. Sinceξ⁰is a unit vector, we haveII(ξ⁰,ξ⁰)≤max{|κmin(q)|,|κmax(q)|}. It follows, according to (6), that max{|κmin(q)|,|κmax(q)|} ≥_ρ^√¹₂, or, equivalently, that the minimal radius of curvature ofSatqis at mostρ√

2. The result follows.

104

(5)

The end of the proof of the lemma is immediate. We have dM(c) ≤ dM(q) +kc−qk

≤ ρ√ 2+2r

≤ r(√ 2+2) So, the radius of ballBis at least √¹

2+2 dM(c), which contradicts the assumption thatE is a looseε-sample, withε≤ε0< √¹

2+2. From lemma 3.11, it immediately follows that|C∩C⁰| ≤2, by (4).

Lemma 3.12S∩∆is not reduced to two points.

Proof Let us assume thatSintersects∆in two points exactly, say aandb. Then, the subarc ofξthat joins pointsaandblies outside

∆. It follows, by the same reasoning as in the proof of claim 1, that there exists some pointqofξat which the curvature ofξis at least ¹_ρ. It follows by claim 2 thatdM(q)≤ρ√

2, which leads to a contradiction, as in the end of the proof of lemma 3.11.

It follows from the above lemmas thatDandD⁰ intersect along a topological disk. The result is clear if D⊆D⁰ or if D⁰ ⊆D.

Otherwise, we have|C∩C⁰| ≤2, by lemma 3.11. If|C∩C⁰|=0, thenD∩D⁰ is empty. If|C∩C⁰|=1, thenD∩D⁰ is reduced to a point. If |C∩C⁰|=2, thenD∩D⁰ is either a topological disk or equal toC∩C⁰. But ifD∩D⁰=C∩C⁰, then S∩∆=C∩C⁰ sinceC∩C⁰⊆S∩∆⊆D∩D⁰. This contradicts lemma 3.12. Hence, D∩D⁰is not equal toC∩C⁰and is therefore a topological disk. This ends the proof of proposition 3.9.

4. Global properties of looseε-samples

In this section,Eis a looseε-sample ofS, withε≤ε0. We prove that Del_|S(E)is a manifold without boundary (theorem 4.5), ambient isotopic toS(corollary 4.7), at Hausdorff distanceO(ε²)from S(theorem 4.8). From the latter we deduce thatEis anε(1+16ε)- sample ofS(corollary 4.13). We also prove that the surface Delau- nay balls coverS(theorem 4.15).

4.1. Manifold

We first prove that every edge of Del_|_S(E)is incident to exactly two facets of Del_|_S(E). We then prove that every vertex of Del_|_S(E)has only oneumbrella. An umbrella of a vertexvis a subset of facets of Del_|_S(E)incident tovwhose adjacency graph is a cycle.

Lemma 4.1The dual of a facet of Del_|_S(E)intersectsSonly once, and transversally.

Proof Let f be a facet of Del_|_S(E), and f^∗its dual Voronoi edge.

We denote byathe vertex offthat has the largest inner angle. We have ˆa≥^π₃, and sinceε≤ε0<¹₇, lemma 3.1 says that

−

→n(a),−→n_f

≤arcsinε√ 3

1−ε (7)

where−→n_f denotes the unitary vector orthogonal to f that makes the smaller angle with−→n(a). LetBabe the ballB(a,_1−ε^ε dM(a)).

For any surface Delaunay ballB(c,r)that circumscribesf, we have kc−ak=r ≤εdM(c)

≤ε(dM(a) +kc−ak)

Hence,kc−ak ≤_1−ε^ε dM(a). In other words, every center of surface Delaunay ball offlies inBa. In addition, we have

∀x∈Ba∩S,kx−ak ≤_1−ε^ε dM(a)

≤_1−ε^ε (dM(x) +kx−ak) which implieskx−ak ≤_1−2ε^ε dM(x). According to lemma 3.3, we then have∀x∈Ba∩S,

(−→n(x),−→n(a))≤ ε/(1−2ε)

1−3ε/(1−2ε)= ε

1−5ε (8)

(7) and (8) give

∀x∈Ba∩S, −→n(x),−→nf

≤(−→n(x),−→n(a)) + −→n(a),−→nf

≤_1−5ε^ε +arcsin^ε_1−ε^√³

which is less than^π₂ sinceε≤ε₀<ε₃. Thus, by lemma 9.4,Ba∩S is a terrain over the planeΠ_fthat supportsf. Sincef^∗is orthogonal toΠf, it cannot intersectBa∩Smore than once, nor tangentially.

And since every center of surface Delaunay ball of flies inBa, f^∗ cannot intersectSmore than once, nor tangentially.

For a restricted Delaunay facetf, we denote byBf= (cf,rf)the corresponding surface Delaunay ball. The surface Delaunay patch of f,S∩Bf, is denoted byDf. We defineCf=∂Df.

Lemma 4.2Let f and f⁰be restricted Delaunay facets that share an edge. They make a dihedral angle greater than^π₂.

Proof This result is a consequence of theorem 1 of [24]. The latter states that the dihedral angle is at leastπ−2 _2ε

1−4ε+arcsin^ε_1−ε^√³ , which is greater than ^π₂sinceε≤ε₀<ε₄.

From lemmas 4.1 and 4.2 we deduce the following result.

Proposition 4.3Every edge of Del_|_S(E)is incident to exactly two facets of Del_|_S(E).

Proof Letebe an edge of Del_|S(E). We denote bye^∗the Voronoi face dual toe. SinceShas no boundary,S∩aff(e^∗)is a union of simple closed curves, none of which intersects the boundary∂e^∗of e^∗tangentially, by lemma 4.1. Thus, by the Jordan curve theorem, each curve ofS∩aff(e^∗)intersects∂e^∗at an even number of points.

It follows thatSintersects∂e^∗at an even number of points. More- over, by lemma 4.1, each edge of∂e^∗can be intersected at most once byS. Thus,Sintersects an even number of edges of∂e^∗, and eis incident to an even number of restricted Delaunay facets.

In addition, two restricted Delaunay facets incident toemake a dihedral angle greater than ^π₂, by lemma 4.2. It follows thatemay be incident to at most three restricted Delaunay facets. In conclu- sion, the number of restricted Delaunay facets incident toeis even, strictly positive (sincee∈Del_|_S(E)) and at most three, hence it is equal to two.

It follows from the above proposition that the restricted Delau- nay facets incident to a vertex of Del_|_S(E)form a set of umbrellas.

Proposition 4.4Every vertex of Del_|S(E)has exactly one umbrella.

Proof Letabe a vertex of Del_|_S(E). Let F(a)be the set of all facets of Del_|_S(E)that are incident toa. Letfabe the facet ofF(a) that has the surface Delaunay ball of largest radius. We callrfathis radius. ThenB(a,2rf_a)contains the surface Delaunay balls of all facets ofF(a). Moreover, by lemma 3.7,S∩B(a,2rfa)is a topological disk and a terrain over some planeΠ. We projectS∩B(a,2rfa) ontoΠ. This projection preserves topological properties such as 105

(6)

pseudo-disks. For simplicity of notations, we shall identify objects with their projection ontoΠ. LetF₁(a)be an umbrella ofa. We call U₁(a)the union of the facets ofF₁(a), andR₁(a)the union of the surface Delaunay patches associated with the facets ofF₁(a).

Claim a∈int(R₁(a)).

Proof Ifa∈int(U₁(a)), then it is clear thata∈int(R₁(a)), since surface Delaunay patches are pseudo-disks, by proposition 3.9.

Now, let us assume thatalies on the boundary ofU₁(a). Let[av]

be an edge of the boundary that is incident toa. By proposition 4.3, [av]is incident to two facets of Del_|_S(E), say(a,v,x)and(a,v,x⁰).

These facets belong toF₁(a)since they are incident toa, and they both lie on the same side of[av]which is a boundary edge ofU₁(a).

Thus, since surface Delaunay patches are pseudo-disks by proposition 3.9, eitherxis included in the interior of the surface Delaunay patch of(a,v,x⁰)orx⁰is included in the interior of the surface De- launay patch of(a,v,x), which violates the Delaunay property.

We now assume for a contradiction that there exists a restricted Delaunay facet f= (a,b,d)∈/F₁(a)that is incident toa. Vertices banddlie outside int(R₁(a)), whereasalies in int(R₁(a)), by the above claim. It follows thatCf intersects the boundary ofR₁(a), at some pointzthat lies on the boundary of the surface Delaunay patch of some facet f⁰= (a,b⁰,d⁰)ofF₁(a). By proposition 3.9,Cf and C_f⁰ intersect at pointsaandzonly. By the same proposition, open arcs(a,b⁰)and(a,d⁰)ofCf⁰are included in int(R₁(a)). Sincea∈ int(R₁(a)),zlies on arc(b⁰,d⁰)ofCf⁰. Ifz6=b⁰andz6=d⁰, thenb⁰ andd⁰lie on different sides ofCf, hence one of them lies in int(Df), which violates the Delaunay property. Otherwise (sayz=b⁰),d⁰ must lie outsideD_f. In this case, consider the facet f⁰⁰= (a,b⁰,d⁰⁰) ofF₁(a)that is incident to f⁰through edge[a,b⁰]. By proposition 3.9,Cfintersects arc(b⁰,d⁰⁰)ofC_f⁰⁰at pointb⁰only, thusd⁰andd⁰⁰ lie on different sides ofCf. Hence, eitherd⁰ord⁰⁰lies in int(Df), which violates the Delaunay property.

The next theorem follows from propositions 4.3 and 4.4.

Theorem 4.5 LetSbe a smooth closed surface andE a looseε- sample ofS. Ifε≤ε0≈0.091, then Del_|_S(E)is a 2-manifold without boundary.

Since Del_|_S(E)is a closed 2-manifold embedded inR³, we can orient the normals of its facets consistently. For instance, they can be chosen so as to point to the unbounded component of R³\Del_|_S(E).

4.2. Homeomorphism and ambient isotopy

Letπ: R³→Smap each point ofR³to the closest point ofS. In [4], the authors have shown that the restriction ofπto a 2-simplicial complexW whose vertices lie onSis a homeomorphism between WandS, provided that:

H0 Wis a manifold without boundary.

H1 Whas a vertex on each connected component ofS.

H2 The angle between the oriented normals of any two incident facets ofWis less than^π₂.

H3(SMALLTRIANGLECONDITION) every facet f ofW has a circumcircle of radius at most _1−ε^1.3εdM(a), whereais any vertex of

f.

H4 (FLAT TRIANGLE CONDITION) the normal to every facet f of W makes an angle of at most arcsin_1−ε^1.3ε + arcsin ₂

√3sin

2arcsin^1.3ε_1−ε

with−→n(a), whereais the vertex with the largest interior angle inf.

We will show that H0, H2, H3 and H4 are satisfied byW = Del_|_S(E)in our context. H0 has already been stated for Del_|_S(E) in theorem 4.5.

Proofof H2

Letabe a vertex of Del_|S(E)and letF(a)be the umbrella ofa. By lemma 3.1, the smaller angle between−→n(a)and the line normal to any facet ofF(a)is at most _1−7ε^2ε +arcsin^ε_1−ε^√³, which is less than

π4 sinceε≤ε0<ε1. It follows that the angle between−→n(a)and the oriented normal of the facet is less than ^π₄ or greater than ^3π₄. Moreover, any two consecutive facets in the umbrella ofamake a dihedral angle greater than ^π₂, by lemma 4.2, thus the angles between−→n(a)and the oriented normals of the facets ofF(a)are all less than^π₄, or they are all greater than^3π₄. It follows that the angle between the oriented normals of any two facets ofF(a)is less than

π2.

Proof of H3

SinceEis a looseε-sample, every facetfof Del_|_S(E)has a surface Delaunay ballBf=B(cf,rf)of radiusrf≤εdM(cf). Letabe any vertex of f. We havedM(cf)≤dM(a) +ka−cfk ≤dM(a) +rf, thus rf ≤ _1−ε^ε dM(a). It follows that the circumcircle of f has a radius of at most_1−ε^ε dM(a)≤_1−ε^1.3εdM(a). Sinceε≤ε₀, the radius is at most _1−ε^ε⁰₀ dM(a)≈0.1dM(a).

Proof of H4

Let f∈Del_|S(E)andabe the vertex of f with the largest inner angle. By lemma 3.1, we have(−→nf,−→n(a))≤arcsin^ε_1−ε^√³, which is at most arcsin_1−ε^1.3ε+arcsin ₂

√3sin

2arcsin^1.3ε_1−ε

. Sinceε≤ε₀, the angle is at most arcsin^ε_1−ε⁰^√³₀≈0.175 radians.

The following result is then a direct consequence of theorem 19 of [4].

Theorem 4.6LetSbe a smooth closed surface andE a looseε- sample ofS, withε≤ε₀≈0.091, such that Del_|_S(E)has a vertex on each connected component ofS. Then the restriction of the map- pingπto Del_|S(E)is a homeomorphism between Del_|S(E)andS.

Corollary 4.7LetSbe a smooth closed surface andEa looseε- sample ofS, withε≤ε₀≈0.091, such that Del_|_S(E)has a vertex on each connected component ofS. Then Del_|S(E)andSare ambient isotopic.

ProofSince the SMALLTRIANGLECONDITIONis verified by the facets of Del_|_S(E), lemma 12 of [4] tells that∀x∈Del_|_S(E),kx− π(x)k<0.165dM(π(x)). Moreover, according to theorem 4.6,πis a homeomorphism between Del_|S(E)andS. Thus, by theorem 9 of [6], Del_|_S(E)andSare ambient isotopic.

4.3. Hausdorff distance

Theorem 4.8LetSbe a smooth closed surface andE a looseε- sample ofS, withε≤ε₀≈0.091, such that Del_|S(E)has a vertex on each connected component ofS. Then the Hausdorff distance betweenSand Del_|_S(E)is at most 8.5ε²d_M^sup.

106

(7)

The idea is to bound the distance from Del_|_S(E)toS, and then to use the surjectivity ofπto prove that the bound also holds for the distance fromSto Del_|_S(E).

Lemma 4.9 Let c∈S. For any point x∈Sat distance at most εdM(c)fromc, the distance fromxtoT(c)is at most¹₂ε²dM(c).

Proof LetB₁andB₂be the two balls of radiusdM(c), tangent toS atc. Their interiors cannot intersectSand therefore do not contain x. Letx⁰be the intersection point other thancof the segment[c,x]

with the boundary ofB₁∪B₂. Lethbe the distance ofxtoT(c)and θthe angle between−→cxandT(c). We have

kc−x⁰k=2dM(c)sinθ≤ kc−xk ≤εdM(c) Therefore, sinθ≤^ε₂ andh=kc−xksinθ≤¹₂ε²dM(c).

Lemma 4.10Letc∈Sand letybe a point ofT(c)at distance at mostεdM(c)fromc. The distance ofytoSis at most 8ε²dM(c).

Proof Letzbe the point ofSclosest toy,tits projection ontoT(c) andφ=∠yzt, which is also the angle between the normals toSat candz. We have

kc−zk ≤ kc−yk+ky−zk ≤2kc−yk ≤2εdM(c) It then follows from lemma 4.9 thatkz−tk ≤4ε²dM(c). Moreover, dM(c)≤dM(z) +kc−zk, thuskc−zk ≤ _1−2ε^2ε dM(z). It follows from lemma 3.3 thatφ≤_1−8ε^2ε . Sinceε≤ε₀≤0.1, we have_1−8ε^2ε ≤ 1, thusφ≤1. It follows that _cos¹_φ ≤₁₋¹φ2

2 ≤1+φ², from which we deduce

ky−zk=^k_cosφ^z⁻^t^k ≤4ε²dM(c)

1+ _2ε

1−8ε

2

≤8ε²dM(c)

With lemmas 4.9 and 4.10, we can bound the distance from Del_|_S(E)toS.

Proposition 4.11Every pointx∈Del_|_S(E)is at distance at most 8.5ε²dM(c)≤8.5ε²d_M^supfromS, wherecis the center of the surface Delaunay ball of the facet that containsx.

Proof Letx∈Del_|_S(E). Let f be a facet of Del_|_S(E)on whichx lies, and letB(c,r)be the surface Delaunay ball off. Letx⁰be the orthogonal projection ofxontoT(c). For any vertexaof f, we haveka−ck ≤r, which is at mostεdM(c)sinceE is a looseε- sample. Thus, by lemma 4.9, the distance fromatoT(c)is at most

12ε²dM(c). Since this is true for every vertex off, it is also true for any point of f, and forxin particular. Hence,kx−x⁰k ≤¹₂ε²dM(c).

In addition, we havekx⁰−ck ≤ kx−ck ≤εdM(c). Thus, by lemma 4.10, the distance fromx⁰toSis at most 8ε²dM(c). It follows that the distance fromxtoSis at most 8.5ε²dM(c)≤8.5ε²d_M^sup.

We can now bound the distance fromSto Del_|_S(E), which com- pletes the proof of theorem 4.8.

Proposition 4.12 Every point x ∈ S is at distance at most min{8.5ε²d^sup_M ,10.5ε²dM(x)}from Del_|_S(E).

Proof Letx∈S. Since the restriction ofπto Del_|_S(E)is surjec- tive, we haveπ⁻¹_|_Del_|S_(E)(x)6=∅. Letx⁰∈π⁻¹_|_Del_|S_(E)(x). According to proposition 4.11,kx−x⁰k ≤8.5ε²dM(c)≤8.5ε²d_M^sup, wherecis the center of the surface Delaunay ball of the facet that containsx⁰.

In addition, we havekx⁰−ck ≤ε dM(c), since E is a looseε- sample. Thus,kx−ck ≤(ε+8.5ε²)dM(c)≤(ε+8.5ε²)(dM(x) + kx−ck). It follows that kx−ck ≤ _1−ε−8.5^ε+8.5^ε²_ε2dM(x), which is at most 0.2dM(x)sinceε≤ε0. Hence,

kx−x⁰k ≤8.5ε²dM(c)≤8.5ε²(dM(x) +kx−ck)≤10.5ε²dM(x)

By lemma 2.3, we know thatε-samples are looseε-samples. The converse is not true but the following corollary shows that loose ε-samples are close to beε-samples.

Corollary 4.13LetSbe a smooth closed surface andEa looseε- sample ofS, withε≤ε₀≈0.091, such that Del_|S(E)has a vertex on each connected component ofS. ThenEis anε(1+16ε)-sample ofS.

Proof By proposition 4.12, any pointx∈Sis at distance at most 10.5ε²dM(x)from Del_|_S(E). Letx⁰be the point of Del_|_S(E)closest tox, and f the facet of Del_|_S(E)that contains x⁰. We callc the center of the surface Delaunay ball of f, andc⁰the center of the circumcircle off. Letabe the vertex of f closest tox⁰. Since x⁰ belongs to f, we havekx⁰−ak ≤ kc⁰−ak ≤ kc−ak. More- over,kc−ak ≤εdM(c)≤ε(dM(a) +kc−ak), that is,kc−ak ≤

1−εε dM(a). Thus,

kx−ak ≤ kx−x⁰k+kx⁰−ak

≤10.5ε²dM(x) +_1−ε^ε dM(a)

≤10.5ε²dM(x) +_1−ε^ε (dM(x) +kx−ak) It follows that

kx−ak ≤10.5(1−ε)

1−2ε ε²dM(x) + ε 1−2εdM(x) Sinceε≤ε0, we have^10.5(1−ε)_1−2ε ≤12 and _1−2ε¹ ≤1+4ε, thus,

kx−ak ≤12ε²dM(x) +ε(1+4ε)dM(x)

4.4. Covering

Let^S_f∈Del|S(E)Bf (or^S_fBf, for short) denote the union of the surface Delaunay balls.

Letf₀= (a,b,c)be a facet of Del_|_S(E). Our goal is to prove that Cf0⊂int

SfBf

. In fact, we will prove a slightly more precise result, stated as lemma 4.14.

LetF(f₀)be the set of all facets of Del_|_S(E)that are incident to f₀, except f₀. Since, by theorem 4.5, Del_|_S(E)is a manifold without boundary,F(f₀)contains one facet of Del_|_S(E)incident tof₀ through each edge of f₀. We defineR(f₀)as the union of all surface Delaunay patches associated with facets ofF(f₀).

Lemma 4.14Cf0⊆int(R(f₀)∪Df0).

Proof We call f_ab, f_bcand facthe three facets ofF(f₀)that are incident to f₀through edgesab,bcandacrespectively. By proposition 3.9, arcsab,bcandacofCf0are included inDf_ab,Df_bcand D_f_acrespectively, and only their endpoints may lie onC_f_ab,C_f_bcor Cfac. Thus, the three arcs are included in the interior ofR(f₀), except for their endpoints which may possibly lie on some boundary 107