C It

Discrete Comput Geom **:*** *** (****) Discrete & Computational

Geometry

DOI: 10.1007/s00454-007-1309-8

**** ******** *******+Business Media, Inc.

Stability and Computation of Topological

Invariants of Solids in Rn

Fr d ric Chazal1 and Andr Lieutier2

ee e

1 Institut de Math matiques de Bourgogne, Universit de Bourgogne,

e e

UMR 5584, UFR des Sciences et Techniques,

9 avenue Alain Savary, B.P. 478**-***** Dijon Cedex, France

*******@*-*********.**

2 Dassault Syst` mes (Aix-en-Provence)

e

and

LMC/IMAG, Grenoble, France

andre ********@**-**.***

Abstract. In this work one proves that under quite general assumptions one can deduce the

topology of a bounded open set in Rn from an approximation of it. For this, one introduces

the weak feature size (wfs) that extends for nonsmooth objects the notion of local feature

size. Our results apply to open sets with positive wfs. This class includes subanalytic open

sets which cover many cases encountered in practical applications. The proofs are based

upon the study of distance functions to closed sets and their critical points. The notion

of critical point is the same as the one used in riemannian geometry [22], [9], [20] and

nonsmooth analysis [10]. As an application, one gives a way to compute the homology

groups of open sets from noisy samples of points on their boundary.

1. Introduction and Related Works

The contribution of this work is theoretical. However, it addresses a question arising in

practice in the process of reverse engineering. Reverse engineering, in our context, is

the process of building a geometric model for a physical object, given a set of points

sampled on the object boundary. Does this geometric model, for example a polyhedron,

capture the right topology of the initial object? Intuitively, this seems possible if the size

of the features, such as the thickness of the thin parts, the diameter of holes, etc., are

large with respect to the sampling accuracy and density.

602 F. Chazal and A. Lieutier

In recent years, authors have worked out sampling conditions and associated recon-

struction algorithms that allow the reconstructed geometric model to re ect correctly the

topology of the sampled object. Amenta et al. [2] introduce the local feature size, or lfs,

de ned in each point as the distance to the medial axis of the object. Several algorithms

are proved to provide a result homeomorphic to the sampled object [1], [2], [4], given a

smooth object sampled with a local density at least around 20 times smaller than lfs.

Most studies assume exact sampling. In practice, measured points are assumed to lie

within a given tolerance from the object boundary. The case of noisy sampling has been

considered as well. In [14] it is proven that, as far as this noise is small with respect to

lfs, the topology can still be captured.

However, the problem of a density criterion relying on the local feature size is that

lfs vanishes on the boundary of nonsmooth objects. Theorems involving lfs do not help

on nonsmooth objetcs, such as solids with sharp edges. Fortunately, algorithms proved

correct in the case of smooth objects, behave relatively well in practice on solids with

sharp edges.

In [6] and [7], the authors examine, given a Hausdorff distance approximation of an

object O, the possibility of computing an approximation of the medial axis of O . For

this purpose, a new measure of the feature size of an object is introduced, the weak

feature size, or wfs (see Section 3). Wfs allows to consider nonsmooth objects, such as

polyhedra or, more generally, piecewise analytic or semianalytic sets, for which wfs > 0.

Wfs is de ned as the minimum distance between the boundary and the set of singular

points of the distance function (distance to the boundary). In other words, wfs is the

minimum singular value of the function distance to the boundary (see Sections 2.2 and

3 below).

In the present work the noisy sampling is modelized by a possibly nite set within a

given Hausdorff distance of the boundary of the original object. Using the tools developed

in [6] and [7], one shows, roughly speaking, that if two objects O and O, such that

wfs( O ) > 2 and wfs( O ) > 2, have their complement O c and O c within a Hausdorff

distance less than, dH ( O c, O c )

(see Theorem 3.3). A consequence is that if one is given an Hausdorff approximation

of the complement O c of an open set O with wfs( O ) > 4, then the homotopy type of

O is uniquely determined by the approximation. Indeed, we show that it is possible to

express the homology of the set O through the notion of persistent homology [27], [15]

from the given approximation (see Theorem 4.2).

If this approximation is a nite sample of the boundary, the algorithms for the com-

putation of persistent Betti numbers (see [27] and [15] ) may be used on a ltration in the

Voronoi complex, named the -medial axis, de ned in [23], [6], and [7], see Section 4.2.

We show that the persistent Betti numbers computation on the -medial axis ltration

is guaranteed to provide the Betti numbers of the originally sampled set (Theorem 4.4).

A similar computation for persistent homology on the -complex ltration allows us

to capture the homology of a thickening of the boundary of the initial object (Theorem

4.5). It has been independently observed by Cohen-Steiner and Edelsbrunner [12], in the

context of work on topological persistence and Morse functions, that sampling conditions

based on a variant of the wfs the homological feature size, and the use of topological

persistence techniques allow us to capture the homology of a thickening of the boundary

of the initial object.

Stability and Computation of Topological Invariants of Solids in Rn 603

2. Preliminaries

We introduce mathematical tools and results which are useful in the remainder of the

paper. The proof of the results of this section are available in [23].

2.1. The Gradient Vector Field of Distance Function

We use the following de nitions and notations. Throughout the paper, O and M always

denote respectively a bounded open subset of Rn and its Medial Axis de ned below.

For any set X, let X, X, X and X c denote respectively the closure, the interior, the

boundary and the complement of X . Bx,r and B,r respectively denote the closed and

x

open ball of center x and radius r in Rn . We denote by Sx,r the corresponding sphere,

that is Sx,r = Bx,r \B,r . For any point x O, we denote by (x ) the set of the closest

x

boundary points, that is,

(x ) = { y Oc, d (x, y ) = d (x, Oc )}

= { y O, d (x, y ) = d (x, O)}.

Because O is compact, (x ) is a nonempty compact set. For a set E, let E denote the

cardinal of E .

De nition 2.1 (Medial Axis). The Medial Axis M of the open set O is the set of points

x of O who have at least two closest boundary points:

M = {x O, (x ) 2}.

One denotes by R the distance function to the boundary of O de ned by

R(x ) = d (x, Oc ) x O.

for any

One can check, using the triangular inequality twice, that R is 1-Lipschitz. Given a point

x O, there always exists a unique closed ball with minimal radius enclosing (x ) [23].

One de nes a real-valued positive function F : F (x ) is the radius of this smallest closed

ball enclosing (x ) and one denotes its center by (x ) (see Fig. 1). In other words,

F (x ) = inf{r : y Rn, B y,r (x )}.

One proves in [23] that F is upper semicontinuous, that is,

R, {x O, F (x ) 0 be a positive real number. We denote by Od the set of points of O at distance

greater than d from the boundary,

Od = {x O, R(x ) > d },

and by Od the closure of Od .

In Theorem 1 of [7] one proves that if d 0 be such

that wfs(O) > 2 and wfs(O ) > 2 . If dH (Oc, O c ) 2, there exists > 0 with 2 + 4, one has in theory enough information to determine the homotopy type of

O. For example, we know that there exists at least O itself that satis es wfs(O) > 4, and

dH ( S, Oc ) 4

and dH ( S, O c ) 0.

This result has been proven by Fu [18, p. 1045] for semialgebraic sets. The proof

adapts easily to piecewise analytic sets and may be found in [7].

610 F. Chazal and A. Lieutier

4. Homotopy and Homology of Sets with Positive wfs

We now study the behavior of the homotopy and singular homology groups of open sets

O with positive wfs under small perturbations. Some of the ideas of this section are

closely related to the notion of topological persistence (see [15]). To be conceptual, all

the homology groups considered in what follows are with coef cients in Z/2. Proofs of

this section are clearly independent of the choice of the coef cients domain, so results

of this section remain true if one replaces Z/2 by another coef cients domain (e.g. Z).

If x is a point in a topological space X, one denotes by 1 ( X, x ) the fundamental group

of X with x as the base point.

4.1. Stability of Homology and Homotopy

If O and O are two bounded open sets in Rn and > 0 such that dH (Oc, Oc ) 0 be such

c c

that wfs(O) > 2 and dH (O, O ) 0 such that c1 and c2 are included in O2 +

and 2 + 0 be such that

wfs(O) > 4 and dH (Oc, Oc ) 0. In other

words, the homology groups of O are determined by the way O3 is included in O .

Proof. First, one has

im(i : Hk (O3, Z/2) Hk (O, Z/2)) Hk (O3, Z/2)/Ker(i ),

where Ker(i ) denotes the kernel of the homomorphism i .

Let j : O3 O be the canonical inclusion map and let j be the induced homo-

morphism between corresponding homology groups. Consider the following sequence

of inclusion maps:

O4 O3 O.

Because 4 2

while in Theorem 4.2 one needs wfs(O) > 4 to be satis ed. Notice also that previous

proposition and theorem generalize immediately to higher homotopy groups.

Using -Medial Axis

4.2.

In [7] a subset of the medial axis, called the -medial axis and denoted M is introduced.

Using the de nitions and notations of Section 2.1, for an open set O, its medial axis

M(O) can be de ned as

M(O) = {x O ; F (x ) > 0}.

For > 0, the -medial axis M (O) is de ned by

M (O) = {x O ; F (x ) }.

Notice that, because F is upper semicontinuous, M (O) is a closed set. For a nite set S,

the medial axis M( S c ) is the union of the cells of the Voronoi diagram of S of dimension

strictly less than the dimension n of the ambient space. Moreover, the function F being

constant on each Voronoi cell, M ( S c ) is a union of some Voronoi cells of the Voronoi

diagram of S (see [7]). Since M ( S c ) is closed, it is thus a subcomplex of the Vorono

diagram of S . Given the Voronoi diagram, it is straightforward to compute M ( S c ), by

selecting the cells on which F is greater than or equal to .

The set F = {x O ; (x ) = 0} of critical points of the distance function is

compact because O is bounded and x (x ) is lower semicontinuous. Therefore,

the set R(F) of critical values of the distance function is compact. We have the following

lemma:

Lemma 4.3. Let O be a bounded open set. If > 0 is not a critical value of the distance

function R, then O and M have the same homotopy type.

Proof. Because x O, F (x ) R(x ), one has of course M O . Because the

set R(F) of critical values is compact, there is > 0 such that there are no critical

values in [, + ]. Therefore, it is possible to shrink O on O +, using for example

Proposition 3.4.

Let us take > 0 such that

1 2 > . (7)

If D is a bound on the diameter of O, t R(C(t, x )) is bounded by D . Then, from (4),

there must be some t [0, D / 2 ] with (C(t, x )) 0 be such that

and 3 are not critical values of the distance function to Oc and such that wfs(O) > 4

and dH (Oc, Oc ) 0 from

a noisy sampling.

4.3. Homology of Thickenings of Compact Sets with Positive wfs

The wfs of a compact subset K of Rn is the wfs of its complement Rn \ K . Note that

Rn \ K is not bounded but one can de ne its wfs in the same way as for bounded open

sets. Let K Rn be a compact set such that wfs( K ) > 0. One denotes by K = {x

Rn : d (x, K ) 0 be such that

) 0 be such that + 4 4 and dH ( K, K

and denote by i : K + K +3 the canonical inclusion map and by i the induced

map between homotopy or homology groups. For any 0 0, the homology groups

of K and the homology groups of its thickenings are not always the same: consider

the following example (see also 2.4.8 of [26]). Let K R2 be the union of the four

sets K 1 = {(x, y ): x = 0, 2 y 1}, K 2 = {(x, y ): 0 x 1, y = 2},

K 3 = {(x, y ): x = 1, 2 y 0} and K 4 = {(x, y ): 0 4, Theorem 4.4 can be applied to the open sets O = B, R \ S and O.

0

The Delaunay ltration dual to the Voronoi ltration M is simplicial. It is then

possible to use techniques described in [15] and [27] on the ltration corresponding to the

M (O) when decreases from 3 to to compute the homology of i (Hk (M3 (O), Z/2))

and therefore, by Theorem 4.4, of Hk (B0,R \S, Z/2).

Notice that S c has exactly one unbounded connected component, which can be iden-

ti ed in the ltration M (O). Therefore, if one knows that Oc has only one connected

component (which means that O has no voids), then the homology of B, R \ S gives the

0

homology of O.

Homology through -Shape Filtration. Consider, in Theorem 4.5, the case where K

is a nite set. K r is then a union of balls, which is known to have the homotopy type

of the dual complex or -complex of K . One can use precisely the ltration mentioned

in [15] on the -complex and the associated algorithm for the computation of persistent

616 F. Chazal and A. Lieutier

homology. Then, according to Theorem 4.5, counting the cycles classes that survive

between the times and 3 gives the Betti numbers of K .

Finiteness of Homotopy Types. Theorem 3.3 also leads to a homotopy niteness theo-

rem for bounded open sets with positive wfs.

Theorem 5.2 (Homotopy Finiteness). Given an integer n 1 and two positive reals

> 0 and D > 0, there are at most nitely many homotopy types among bounded

open sets O in Rn satisfying wfs(O) > and diameter(O) and wfs(O) >, it follows from Theo-

rem 3.3 that O and O have the same homotopy type.

Note that given n, and D, the number of different homotopy types for open subset

of Rn with wfs greater than and diameter less than D is bounded by 2(4 D n / +1) . Such

n

a bound is far from being optimal.

To conclude note that the previous theorem together with Proposition 3.6 has the

following consequence in real analytic geometry.

Corollary 5.3. The number of homotopy types among bounded subanalytic open sets

in Rn with positive wfs is countable.

Acknowledgments

The authors are grateful to Pierre Pansu for helpful comments and remarks. They are

also grateful to David Cohen-Steiner for helpful discussions.

Stability and Computation of Topological Invariants of Solids in Rn 617

References

1. N. Amenta and M. Bern, Surface reconstruction by Voronoi ltering, Discrete Comput. Geom. 22 (1999),

481 504.

2. N. Amenta, S. Choi, T. Dey and N. Leekha, A simple algorithm for homeomorphic surface reconstruction,

Internat. J. Comput. Geom. Appl. 12(1,2) (2002), 125 141.

3. M. Berger, Geometry I, Universitext Series, Springer-Verlag, Berlin, 1998.

4. F. Cazals and J.D. Boissonnat, Smooth surface reconstruction via natural neighbour interpolation of

distance functions, Proc. Sixteenth ACM Symp. Computational Geometry, 2000, pp. 223 232.

5. F. Chazal and D. Cohen-Steiner, A condition for isotopic approximation, Proc. ACM Symp. Solid Modeling

and Applications, 2004, pp. 390 404.

6. F. Chazal and A. Lieutier, Stability and homotopy of a subset of the medial axis (extended abstract), Proc.

ACM Symp. Solid Modeling and Applications, 2004, pp. 243 248.

7. F. Chazal and A. Lieutier, The -medial axis, Graphical Models, 67(4) (2005), 304 331.

8. F. Chazal and R. Souf et, Stability and niteness properties of medial axis and skeleton, J. Dynam. Control

Systems 10(2) (2004), 149 170.

9. J. Cheeger, Critical Points of Distance Functions and Applications to Geometry, in Geometric Topology:

Recent Developments, Montecatini Terme, Springer Lecture Notes, 1504, Springer, Berlin, 1991, pp. 1 38.

10. F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, 1983.

11. F.H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247 262.

12. D. Cohen-Steiner, H. Edelsbrunner and J. Harer, Stability of persistence diagrams, Proc. 21st Annual ACM

Symp. Computational Geometry, 2005, pp. 263 271.

13. T. K. Dey, J. Giesen and M. John, Alpha-shapes and ow shapes are homotopy equivalent, Proc. 35rd

Annual ACM Symp. Theory of Computing (STOC), 2003, pp. 493 502.

14. T. K. Dey and S. Goswami, Provable surface reconstruction from noisy samples, Proc. 20th ACM Symp.

Computational Geometry, 2004, pp. 330 339.

15. H. Edelsbrunner, D. Letscher and A. Zomorodian, Topological persistence and simpli cations, Discrete

Comput. Geom. 28 (2002), 511 533.

16. H. Edelsbrunner and E. P. Mucke, Three-dimensional alpha shapes, ACM Trans. Graphics 13 (1994),

43 72.

17. H. Federer, Curvature measure, Trans. Amer. Math. Soc. 93 (1959), 418 491.

18. J.H.G. Fu, Tubular neighborhoods in Euclidean spaces, Duke Math. J. 52(4) (1995), pp. 1025 1046.

19. W. Fulton, Algebraic Topology, A First Course, Graduate Texts in Mathematics, Springer-Verlag, New

York, 1997.

20. M. Gromov, Curvature, diameter and Betti numbers, Comment. Math. Helv. 56 (1981), pp. 179 195.

21. K. Grove, Critical point theory for distance functions, Proc. of Symposia in Pure Mathematics, Vol. 54,

American Mathematical Society, Providence, RI, 1993.

22. K. Grove and K. Shiohama, A generalized sphere theorem, Ann. of Math. 106 (1977), 201 211.

23. A. Lieutier, Any open bounded subset of R n has the same homotopy type as its medial axis, J. Comput.-

Aided Design 36 (2004), 1029 1046.

24. W. Massey, Algebraic Topology: An Introduction. Harbrace College Mathematics Series, Harcourt, Brace

and World, Orlando, FL, 1967.

25. J.R. Munkres, Elements of Algebraic Topology. Addison-Wesley Publishing Company, 1984.

26. E.H.Spanier. Algebraic Topology McGraw-Hill Series in Higher Mathematics, McGraw-Hill, New York,

1966.

27. A.J. Zomorodian Computing and comprehending topology: persistence and hierarchical morse complexes,

Thesis, University of Illinois at Urbana-Champaign, 2001.

Received October 11, 2005, and in revised form October 17, 2006. Online publication April 17, 2007.

9.tex.dvi

Contact this candidate