On the Recognition of Tori Embedded in R3

On the Recognition of Tori Embedded in R3. Hélène Arnaud Université de Poitiers, Laboratoire de Mathématiques et Applications, France [email protected] Abstract Many known algorithms allow us to topologically recognize surfaces in 3D images. However, none of them permits us to distinguish different types of embeddings of surfaces. In this paper, we restrict our study to the case of embedded tori, and focus on their recognition up to isotopy. We recall the mathematical definition of isotopy, then we define the two key elements which will enable us to classify an embedded torus in R3up to isotopy : its state and the knot associated with it. At the end of the paper, we bring up two algorithms which aim at finding the isotopy type of an embedded torus, by determining its state and computing its associated knot. Keywords torus, embedding, isotopy, solid torus, knots, 3D images. 1 Introduction In medical imaging for instance, it would be helpful to have algorithms able to fully recognize surfaces in 3D images. Numerous programs computing topological properties such as the Euler characteristic, the genus, and the homology of a surface already exist (see for instance [Mun84], [DG98] and [DE95]). They enable computers to recognize surfaces in images up to homeomorphism. It means that these programs can tell us if a given surface in the image is a sphere, a torus, a projective plane... However, a single surface can be embedded in very different ways in an image. For instance, both surfaces of Figure 1 are orientable surfaces of genus 2. Topologically, they are the same surface, and yet by virtue of their position in R3they are different, the second one is not just a deformation of the first one. Figure 1: The same surface embedded in two different ways in R3. That is why algorithms allowing us to recognize embedded surfaces “up to deformation” would be of interest. We will restrict our study to the case of embedded tori. Our purpose is thus to recognize tori in 3D images “up to deformation”. The paper is organized as follows. In section 2basic notions necessary to the understanding of the rest of the article are recalled. Section 3deals with recognition of embedded tori: it contains a definition and a description of the different states of tori embedded in R3, and it introduces the notion of knot associated with a torus. Finally, section 4mentions briefly two algorithms that have been implemented in order to recognize embedded tori. 1 65 2 Preliminaries 2.1 Conventions and notations In this paper, maps and spaces will be assumed to be piecewise-linear (denoted by P.L.). It means that each space is a simplicial complex, and that each map, after some subdivision of its domain and range, sends simplexes linearly onto simplexes (see [Hud69], and [RS72]). This assumption is natural, since we deal with images, and necessary to use several theorems as Dehn’s lemma, the loop theorem, and hence the solid torus theorem (see [Rol76]). If Σis a topological manifold with boundary, we will denote by Bd(Σ)its boundary, and by Int(Σ)its interior. Given n∈N(the set of non-negative integers), we will use the classical notation of the ndimensional unit sphere : Sn={x∈Rn+1,"x"=1}. Moreover, the n-dimensional unit disc will be denoted by Dn={x∈Rn,"x"≤1}. Let Xa be topological space, E⊂Xand n∈N. Then we say that Eis a n-sphere if Eis homeomorphic to Sn, that Eis a n-disc if Eis homeomorphic to Dn, and that Eis a disc if Eis a2-disc. 2.2 Alexandroffone-point compactification This compactification will be useful to apply results valid for S3to R3. Alexandroffcompactification extends a noncompact topological space to a compact one, by adding a single point. More precisely, let Xbe a locally compact topological space. The Alexandroffextension of Xis the space ˜ X=X∪{x}where x/∈X, endowed with the topology whose open sets are the open sets of Xtogether with the sets of the form {x}∪(X\K)where Kis a compact subset of X. Then ˜ Xis compact (see [Kel75]). The point xis usually called point at infinity and is denoted by ∞. Its is well known that for n∈N∗, the Alexandroffextension of Rnis an n-sphere. For instance, if n=2,S2can be seen as R2glued with a point at infinity (see Figure 2). The case which will be useful in this paper is n=3. Figure 2: The Alexandroffextension of R2. 2.3 Isotopy Our goal is to recognize embedded tori “up to deformation”. Thus we need to define mathematically what we mean by deformation. This deformation is conveyed by the notion of isotopy (see [Cro04]). We firstly define isotopy of maps : Definition 1. Let X, Y be topological spaces. Two homeomorphisms ϕ0,ϕ1:X→Yare said to be isotopic if there exists a continuous map Φ:X×[0,1] →Ysuch that : 1. Φ(x, 0) = ϕ0(x)∀x∈X 2. Φ(x, 1) = ϕ1(x)∀x∈X 3. For all t∈[0,1], the partial map ϕt:X→Ydefined by ϕt(x)=Φ(x, t)is a homeomorphism. 2 66 Thus the notion of isotopy is similar to homotopy, but stronger since isotopy requires the partial functions to be homeomorphisms. Example 1. Let X=Y=[−1,1] and let fbe given by f(x)=!3x+2 if x∈"−1,−1 2# 1 2x+2 3if x∈"−1 2,1#. Then fis isotopic to identity (id[−1,1]) through the map (see Figure 3) : Φ:[−1,1] ×[0,1] →[−1,1] (x, t)+→   't+2 2−t(x+'2t 2−t(if x∈"−1,−1 2t# '2−t t+2 (x+'2t t+2 (if x∈"−1 2t, 1#. 1 !1 1 !1 graph(ϕt) graph(f) graph(id) Figure 3: fis isotopic to id[−1,1]. We can now state a geometrical definition of isotopy (often called ambient isotopy): Definition 2. Let Xbe a topological space. Two subsets X1,X 2⊂Xare (ambient) isotopic in Xif there exists a homeomorphism h:X→Xisotopic to the identity map idXof X, and such that h(X1)=X2. Geometrically, this means that X1and X2are isotopic if and only if X1can be continuously deformed inside Xto obtain X2, without cutting. For instance, in Figure 4, surfaces (a) and (b) are isotopic in R3(the second one can be continuously deformed to obtain the first one), while (a) and (c) are not isotopic in R3(to obtain (a) from (c), we need to cut it). (a) (b) (c) Figure 4: Surfaces (a) and (b) are isotopic in R3, whereas (a) and (c) are not. 2.4 Embedded tori Since this article deals with embedded tori, we now quickly recall what is an embedded torus. By torus, noted T2, we mean any space homeomorphic with the product S1×S1. The picture to keep in mind is the surface of a doughnut. 3 67 Let Σbe a topological manifold (with or without boundary). An embedding of Σin a topological space Eis a map p:Σ→Ewhich is a homeomorphism onto its image. Thus, an embedded torus is a topological space which can be written as p(S1×S1)for some embedding p. Consequently two embedded tori in R3are always homeomorphic, but not necessarily isotopic in R3. For instance, the two embedded tori of Figure 5 are not isotopic. The difference between them comes from their embedding in R3, hence from the ambiant space. Figure 5: Two non isotopic embedded tori in R3. Therefore, to distinguish two embedded tori, we study their complement in R3. 3 Recognition of tori embedded in R3 3.1 Embedded tori in R3and solid tori By solid torus, denoted by T2 p, we mean any space homeomorphic with the product S1×D2. This time, the picture to keep in mind is the whole doughnut. If Tpis a solid torus embedded in R3, then its boundary is an embedded torus in R3. Then, the question that comes to mind is whether each torus embedded in R3is the boundary of an embedded solid torus in R3. The following fundamental results will help us to answer this question. These results are stated for tori embedded in S3, and we will apply them to R3through Alexandroffcompactification. Given a torus Tembedded in S3, the Jordan-Brouwer theorem ensures that S3\Tconsists of two open connected components, where the boundary of each component is T. The following result, adapted from [Rol76], provides a sufficient condition for the closure of one of these two components to be a solid torus. Proposition 1. Let Tbe a torus embedded in S3,Cone of the two connected components of S3\T, and A=C∪T=C. Assume that there exists a disc D⊂Asuch that •Int(D)⊂C, •Bd(D)⊂T, •Bd(D)is non-trivial in π1(T)(the fundamental group of T). Then Ais a solid torus. Figure 6: The existence of the disc D ensures that Ais a solid torus 4 68 Figure 6 provides an illustration of this result. One of the consequences of this proposition is the following fundamental result. Reader shall refer to [Rol76] for a proof. Theorem 1. (Solid torus theorem) Let Tbe a torus embedded in S3and C1,C2the two connected components of S3\T. Then C1or C2is a solid torus. In other words, any torus embedded in S3bounds a solid torus on at least one side. This gives rise to our definition of the three states of embedded tori in R3. 3.2 The three states of tori embedded in R3 Keeping in mind that our main concern is to recognize tori in 3-dimensional images, we now focus on the case of R3. Contrary to knot theory, which is unchanged in S3and in R3, the theory of torus embeddings is more complicated in R3. As S3is the Alexandroffextension of R3, we can use what has already been done in this case. Definition 3. Let Tbe a torus embedded in R3. Let us consider the Alexandroffextension S3=R3∪{p∞}of R3. Let C1,C 2the connected components of S3\T. Assume that p∞∈C1. Three cases may happen : 1. both C1and C2are solid tori, Tis then said canonical, or standard, 2. only C2is a solid torus. : we say that Tis a knotted torus, 3. only C1is a solid torus : Tis then called a knotted anti-torus. Figure 7 shows these three states of embedded tori. In each case, the component C1is white, while C2is shaded. Figure 7: The three states of tori embedded in R3 We could state a similar definition of the different states of tori embedded in S3, but there would be only two possibilities, due to the fact that if Tis a torus embedded in S3then both connected components of S3\Tare bounded. Let C1,C 2be the connected components of S3\T. Then two cases may occur : either both C1and C2are solid tori (we say that Tis canonical in S3), or only one of them is a solid torus (Tis then said standard in S3). Since we want to recognize tori up to isotopy, this definition of the three states of embedded tori in R3needs to fit with isotopy, and fortunately it is the case : Proposition 2. Two isotopic embedded tori in R3have the same state (both are canonical, both are knotted, or both are knotted anti-tori). Proof : Let T1and T2be two isotopic embedded tori in R3,C1,C 2the two connected components of R3\T1and C$ 1,C$ 2those of R3\T2. Assume that C1and C$ 1are the bounded ones. Since T1 and T2are isotopic, there exists a homeomorphism h:R3→R3isotopic to identity and such that h(T1)=T2. As C1is connected and his a homeomorphism, h(C1)is connected. Moreover, h(C1)⊂ (R3\T2), since his a bijection such that h(T1)=T2. Therefore, h(C1)is included in one of the connected components of R3\T2:h(C1)⊂C$ 1or h(C1)⊂C$ 2. 5 69 •Assume that h(C1)⊂C$ 1. By the same argument, we have h−1(C$ 1)⊂C1or h−1(C$ 1)⊂C2. If we had h−1(C$ 1)⊂C2, as h(C1)⊂C$ 1, it would imply that C1=h−1(h(C1)) ⊂C2, which is absurd. Consequently h−1(C$ 1)⊂C1, and so h(C1)=C$ 1. •If h(C1)⊂C$ 2, the same proof shows that h(C1)=C$ 2. Thus we have h(C1)=C$ 1or h(C1)=C$ 2. And yet C1is bounded, hence compact. Thus h(C1) is compact too, therefore h(C1)⊂h(C1)is bounded. Consequently h(C1)=C$ 1, and in the same way h(C2)=C$ 2. Since his a homeomorphism, this proves that for i∈{1,2},Ciis a solid torus if and only if C$ iis, hence the announced result. ! However, it is obvious that two tori of the same state are not always isotopic. Figure 8 gives an example of two knotted tori that are not isotopic. Therefore knowing the state (canonical, knotted torus or knotted anti-torus) is not sufficient to tell two embedded tori apart, and we will have to add extra information. Figure 8: Two knotted tori that are not isotopic. S1 γ Figure 9: A knot is an embedding of the unit sphere S1. 3.3 Knot associated with an embedded torus in R3 In order to distinguish two embedded tori of same state, we are going to associate a knot with each embedded torus. First of all, let us recall what is a knot: Definition 4. Aknot in R3(respectively S3) is a map γ:S1→R3(respectively γ:S1→S3) which is a homeomorphism onto its image. In other words, a knot is an embedding of the unit sphere S1(see Figure 9). We will sometimes refer the image of the map γas a knot. A knot can be naturally associated with a solid torus, thanks to the following result : Proposition 3. Let Tpbe a solid torus embedded in S3. Then Tpadmits a deformation retraction to a knot in S3(unique up to isotopy). This means that a solid torus in S3shrinks continuously into a knot. This result enables us to define the knot associated with a torus embedded in R3. Definition 5. Let Tbe a torus embedded in R3,S3=R3∪{p∞}the Alexandroffextension of R3, and C1,C2the connected components of S3\T. Assume that p∞∈C1. 1. If C1and C2are solid tori (i.e. Tis standard), then both admit a deformation retraction to the trivial knot, and the knot associated with the embedded torus Tis the trivial knot (see Figure 10). 2. Otherwise, only one of the Ciis a solid torus, and the knot to which Ciretracts is called knot associated with T(see Figure 10). Thus, the recognition of a torus Tembedded in R3consists of two steps : firstly we have to determine its state (standard, knotted torus or knotted anti-torus), and then we need to find and recognize its associated knot. This last step involves knot theory, several algorithms are available (for example, the Jones polynomial is easy to compute, see [Kau91]). Even if they unfortunately can’t distinguish all knots, since they are based on knots invariants, they are efficient with common knots. Our main concern is thus the first step and the very begining of the second step of knot recognition : finding the state of an embedded torus and computing its associated knot. 6 70 (a) The knot associated with a standard torus in R3is the trivial knot. (b) Knot associated with a knotted torus. (c) Knot associated with a knotted anti-torus Figure 10: Knots associated with tori embedded in R3. 4 Implementation In this article, the choice was made to focus on theory. The two algorithms that we already have implemented are prototypes intended to show the effectiveness of the theoretical study. Therefore, they are briefly described, without getting down to the specifics (formal description, complexity, memory occupation ...). The first one aims at finding the state of a torus Tembedded in R3. It is based on an algorithm from [DPF08] which computes the three dimensional minimal generalized map homologous to a 3D object in order to find its homology group generators. We isolated a part of this algorithm and adapted it to simplicial complexes. Given our definition of the state of an embedded torus, determining it amounts to telling if the connected components of R3\Tare, or not, solid tori. This algorithm starts with a simplicial complex Kwhose boundary is T, and may ensure that this complex is a solid torus by finding a disc which satisfies the conditions of Proposition 1. For instance, applied to the simplicial complex of Figure 11 (a), it gives the disc shown in (b). This proves that this simplicial complex is a solid torus. However, even if Kis a solid torus, the algorithm may not be able to find such a disc. Thus this algorithm enables us to find the state of some embedded tori, but not of all of them. (a) A simplicial complex which is a solid torus (b) The first algorithm applied to the solid torus of (a) gives a disc (c) The second algorithm applied to the solid torus of (a) returns a knot Figure 11: The two algorithms applied to an example of solid torus. The point of the second algorithm is twofold : to determine the state of an embedded torus Tand, at the same time, to compute its associated knot. It starts with a simplicial complex K whose boundary is T, and rectracts, shrinks it as much as possible. We have proved that if the result of the algorithm is a knot, then Kis a solid torus, and this knot is the one associated with 7 71 T. For example, when we apply it to the simplicial complex of Figure 11 (a), we obtain the knot (c). This shows, once again, that the starting simplicial complex is a solid torus. We are now trying to prove that if Kis a solid torus, then the algorithm necessarily gives a knot. If this were true, the algorithm would be able to recognize solid tori, thus to determine the state of any embedded torus. In this case, it would allow us to determine both the state of embedded tori and their associated knots. 5 Conclusion and outlook Our algorithms can determine the state and the knot associated with some embedded tori. If we manage to prove that applied to any solid torus, the second one always returns a knot, then we will be able to find the state and the knot associated with each embedded torus. Using algorithms from knot theory, we may then recognize this associated knot, and thus obtain a complete description of the embedded torus. There currently does not exist algorithm able to determine all knots, however existing ones are very efficient with common knots. A future (difficult) task will be to generalize this study to embedded surfaces of genus greater than one. Acknowledgements. The author would like to thank Pol Vanhaecke and Laurent Fuchs for their help in the preparation of this paper. References [Cro04] Peter R. Cromwell. Knots and links. Cambridge University Press, Cambridge, 2004. [DE95] Cecil Jose A. Delfinado and Herbert Edelsbrunner. An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere. Comput. Aided Geom. Design, 12(7):771–784, 1995. [DG98] Tamal K. Dey and Sumanta Guha. Computing homology groups of simplicial complexes in R3.J. ACM, 45(2):266–287, 1998. [DPF08] G. Damiand, S. Peltier, and L. Fuchs. Computing homology generators for volumes using minimal generalized maps. In Proceedings of 12th International Workshop on Combinatorial Image Analysis, volume 4958 of LNCS, pages 63–74, Buffalo, NY, USA, April 2008. Springer. [Hud69] J. F. P. Hudson. Piecewise linear topology. University of Chicago Lecture Notes prepared with the assistance of J. L. Shaneson and J. Lees. W. A. Benjamin, Inc., New York- Amsterdam, 1969. [Kau91] Louis H. Kauffman. Knots and physics, volume 1 of Series on Knots and Everything. World Scientific Publishing Co. Inc., River Edge, NJ, 1991. [Kel75] John L. Kelley. General topology. Springer-Verlag, New York, 1975. Reprint of the 1955 edition [Van Nostrand, Toronto, Ont.], Graduate Texts in Mathematics, No. 27. [Mun84] James R. Munkres. Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984. [Rol76] Dale Rolfsen. Knots and links. Publish or Perish Inc., Berkeley, Calif., 1976. Mathematics Lecture Series, No. 7. [RS72] C. P. Rourke and B. J. Sanderson. Introduction to piecewise-linear topology. Springer- Verlag, New York, 1972. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 69. 8 72