Constructive approximation of compact hypersurfaces

PDF text.

Let M \subset \mathbb{R}^k be a compact manifold of codimension 1. We show that M can be well approximated by a part of an algebraic manifold.

Theorem 1.
For all \varepsilon > 0, there exists c > 0 and a polynomial function P defined on \mathbb{R}^k such that N := P^{-1}(0) \cap (-c,c)^k is diffeomorphic to M and

\sup_{x \in N} \inf_{y \in M} \|x - y\| < \varepsilon.

This was proved by Seifert in a 1936 german language paper. It was later generalized to the Nash-Tognoli theorem which implies that non-singular real algebraic sets have precisely the same topological invariants as compact manifolds [1].

Here, however, our motivations are more elementary and practical. Our proof of theorem 1 points towards constructive approximation processes and shows the separability of the space of all compact hypersurfaces, under an appropriate topology. This is relevant in statistics and computer graphics, for smooth hypersurface regression and reconstruction. Growing sequences of finite dimensional search spaces of smooth manifolds are required in these applications.

In preparation for our proof, in section 2, we also discuss the Jordan-Brouwer theorem, the orientability of M and that M = f^{-1}(0) for some function f having regular value 0. We show that these three facts are essentially equivalent, in the sense that any one can be quite easily obtained from another.

Remark.
I was unable to find an elementary proof, in english or french, of theorem 1 in the litterature. The work presented here is the result of my own efforts.

1. Preliminaries

1.1 Notations and conventions

A function f between arbitrary subsets X and Y of \mathbb{R}^k is said to be smooth if it can locally be extended to a \mathcal{C}^2 map from an open domain. A diffeomorphism is an invertible smooth map f : X\rightarrow Y such that f^{-1} is also smooth. An hypersurface of \mathbb{R}^k is a subset M \subset \mathbb{R}^k such that each point x \in M has a neighborhood in M that is diffeomorphic to \mathbb{R}^{k-1}.

In the following, M is a compact and connected hypersurface of \mathbb{R}^k.

1.2 The global inverse function theorem

We need the following global variant of the inverse function theorem.

Lemma 1. (Global inverse function theorem)
Let f : X\rightarrow Y be a smooth map between manifolds of the same dimensions and let A \subset X. If f is injective on A and if its differential df_p is injective for all p\in A, then there exists a neighborhood \mathcal{U}\subset X of A such that f(\mathcal{U}) is open in Y and f|_{\mathcal{U}} : \mathcal{U} \rightarrow f(\mathcal{U}) is a diffeomorphism.

Proof.
By the usual inverse function theorem, the statements holds when A is a singleton. Thus for every point p \in A, there exists open sets p \in \mathcal{U}_p \subset X and \mathcal{V}_p\subset Y such that f|_{\mathcal{U}_p} : \mathcal{U}_p \rightarrow \mathcal{V}_p is a diffeomorphism. Now, all that is left to show is that there exists a neighborhood \mathcal{W} of A on which f is injective. Then with \mathcal{U} = \bigcup_{p\in A} (\mathcal{W} \cap \mathcal{U}_p), we will have f(\mathcal{U}) = \bigcup_{p\in A} f|_{\mathcal{U}_p}(\mathcal{W} \cap \mathcal{U}_p) open in Y and f|_{\mathcal{U}}: \mathcal{U} \rightarrow f(\mathcal{U}) a diffeomorphism.

To construct \mathcal{W}, we first let \mathcal{K} = \bigcup_{p\in A} \mathcal{U}_p and we place ourselves in \mathcal{K}^2 = \mathcal{K} \times \mathcal{K}. Consider the set F = \{(x,y) \in \mathcal{K}^2 \,|\, x \not = y, f(x) = f(y)\} of points showcasing the non-injectivity of f. Note that F is closed, since f is locally injective on \mathcal{K}^2. Thus F^c is open, both in \mathcal{K}^2 and X^2, and contains some neighborhood of \{(a,a) \,|\, a \in A\} of the form \bigcup_{i \in I}\mathcal{B}_i\times \mathcal{B}_i. Taking \mathcal{W} = \bigcup_{i\in I}\mathcal{B}_i yields the result. \Box

1.3 Remarks about the Jordan-Brouwer theorem

Recall the Jordan-Brouwer theorem: \mathbb{R}^k \backslash M is the disjoint union of two non-empty connected components, one of which is bounded. I show that it implies quite easily the following facts: (1) there exists a function f : \mathbb{R}^k \rightarrow \mathbb{R} having regular value 0 such that M = f^{-1}(0); and (2) M is orientable. Reciprocally, points (1) and (2) each imply the Jordan-Brouwer theorem.

1.3.1 (1) and (2) from Jordan-Brouwer

Now, let d be the euclidean distance and let d(x, M) = \inf_{y \in M} d(x,y). Recall that (see this previous post) M admits an \varepsilon-neighborhood N_\varepsilon = \{x \in \mathbb{R}^k \,|\, d(x, M) < \varepsilon\}, for all \varepsilon > 0 sufficiently small, such that

  • every x \in N_\varepsilon has a unique closest point \pi(x) \in M;
  • the map N_\varepsilon \ni x \mapsto \pi(x) is smooth.

Assume that the Jordan-Brouwer theorem holds. Let I be the bounded connected component of \mathbb{R}^k \backslash M and let E be the other one. At each point x \in M, we let \nu(x) be the normal unit vector to M that points towards E, the exterior region. It can be verified that \nu : M \rightarrow \mathbb{R}^k is smooth, expressing it using local parametrizations of M. It provides a practical parametrization of the \varepsilon-neighborhood and orients M, showing point (2).

Lemma 2.
For \varepsilon > 0 sufficiently small M \times (-\varepsilon, \varepsilon) is diffeomorphic to N_\varepsilon under the map \phi : (x, t) \mapsto x + t \nu(x).

Proof.
Note that \pi\circ \phi (x,t) = x so that \phi|_{M \times \{0\}} is injective. The derivative of \phi at a point (x,0)\in M\times \{0\} is d\phi_{(x,0)}: T_x M \times\mathbb{R} \rightarrow \mathbb{R}^k: (u,v) \mapsto u + v \nu(x), which is also injective. By lemma 1, it follows that there exists a neighborhood \mathcal{U}\subset M \times (-\varepsilon, \varepsilon) of M \times \{0\} such that f|_{\mathcal{U}} is a diffeomorphim onto its image. By the compacity of M\times \{0\}, there exists \alpha>0 such that M \times (-\alpha, \alpha) \subset \mathcal{U} and we obtain that \phi|_{M \times (-\alpha, \alpha)} : M \times (-\alpha, \alpha) \rightarrow N_\alpha is a diffeomorphism. \Box

We fix some \alpha < \varepsilon, where \varepsilon is such that \phi : M\times(-\varepsilon, \varepsilon) \rightarrow N_\varepsilon, defined in lemma 2, is a diffeomorphism. Using the notations of the same lemma, we let

f : N_\alpha \rightarrow \mathbb{R} : x + t \nu(x) \mapsto t.

Thus f is a signed distance function, negative in the interior I. It can be extended smoothly to all \mathbb{R}^k in such a way that f |_{I \backslash N_\alpha} = -\varepsilon and f|_{E \backslash N_\alpha} =\varepsilon. We then have f^{-1}(0) = M and 0 is easily seen to be a regular value.

1.3.2 Jordan-Brouwer from (1) or (2)

We need a first step in the proof of the Jordan-Brouwer theorem.

Lemma 3.
The set \mathbb{R}^k \backslash M has at most two connected components.

Sketch of proof.
Let A be any connected component of \mathbb{R}^k \backslash M. Then \partial A \subset M is non-empty and closed in M. Using local diffeomorphisms N_\varepsilon \rightarrow M\times (-\varepsilon, \varepsilon) around the points of \partial A (the Jordan-Brouwer theorem was only used to ensure that the diffeomorphism is global), it can be verified that \partial A is open in M. Therefore \partial A = M, from the connectedness of M. Taking any p \in M and using again a local diffeomorphism N_\varepsilon \rightarrow M\times (-\varepsilon, \varepsilon) around p, we see that any connected component A intersects one of the side of M around p and the result follows. \Box

Now, if M = f^{-1}(0) with f having regular value 0, remark that

\mathbb{R}^k\backslash M = f^{-1}(-\infty, 0) \cup f^{-1}(0,\infty),

and that both sets in the disjoint union are non-empty (because f has regular value 0). From lemma 3, it follows that \mathbb{R}^k\backslash M has precisely two connected components and it can be verified that one of them must be bounded using the compacity of M.

If otherwise M is orientable, the map \nu, such that \nu(x) is a normal unit vector to M, can be defined globally to be smooth. This implies that lemma 2 holds, which gives that M= f^{-1}(0) for some function f having regular value 0 and in turn that the Jordan-Brouwer theorem holds.

2. Proof of theorem 1

We assume that M is a compact and connected hypersurface and that \varepsilon > 0 is such that \pi: N_\varepsilon \rightarrow M defined above is smooth. In the non-connected case, M has a finite number of connected components and the method of proof is unchanged.

Let c > 0 be such that (-c, c)^k \supset \overline{N_\varepsilon}. It is well known from approximation theory that for all \alpha > 0, there exists a polynomial P_\alpha such that both \sup_{x \in (-c,c)^k} |P_\alpha(x) - f(x)| < \alpha < \varepsilon and \sup_{x \in (-c,c)^k} \|\nabla P_\alpha(x) - \nabla f(x)\| < \alpha. In particular, with \alpha and \varepsilon > 0 sufficiently small, we have M_\alpha := (-c,c)^k \cap P_\alpha^{-1}(0) \subset N_\varepsilon and \nabla P_\alpha (x) \not = 0 for all x \in N_\varepsilon. It is left to show that M_\alpha is diffeomorphic to M.

Consider the smooth map

\pi : M_\alpha \rightarrow M: x + t\nu(x) \mapsto x

defined using the notations of lemma 2.

To see that it is injective, suppose that there are two points x + t\nu(x), x + t'\nu(x) \in M_\alpha. Then P_\alpha(x + t\nu(x)) = P_\alpha(x + t'\nu(x)) = 0. If x + t\nu(x) \not = x + t'\nu(x), then by the mean value theorem there exists a point x + t_0 \nu(x), with t_0 in between t and t', such that \nabla P_\alpha(x+t_0\nu(x)) = 0. This is impossible. Hence t = t' and \pi is injective.

For surjectivity, let x \in M and recall that f can be chosen so that f(x + \varepsilon \nu(x) )= \varepsilon and f(x -\varepsilon \nu(x)) = -\varepsilon. Since \alpha < \varepsilon and \sup_{x \in N_\varepsilon} |f(x) - P_\alpha(x)| < \alpha, we have P_\alpha(x - \varepsilon \nu(x)) < 0 and P_\alpha(x + \varepsilon \nu(x)) > 0. It follows from the intermediate value theorem that there exists t_1 \in (-\varepsilon, \varepsilon) such that P_\alpha(x + t_1 \nu(x)) = 0.

Finally, we show that d\pi_p is injective, for all p \in M_\alpha. It will follows from lemma 1 that \pi is a diffeomorphism. Recall that d\nu_x, for x \in M, can be seen as an endomorphism of T_xM.

Lemma 4.
For x\in M, let \pi_x: \mathbb{R}^k = T_xM \oplus \mathbb{R}\nu(x) \rightarrow T_x M be defined as \pi_x(u + v \nu(x)) = u. Then for \alpha > 0 sufficiently small and any x + t \nu(x) \in M_\alpha, we have that \text{Id}_{T_xM} + t d\nu_x is invertible and

d\pi_{x +t\nu(x)} = \left(\text{Id}_{T_xM} + t d\nu_x\right)^{-1}\circ \pi_x.

Proof.
The invertibility of \text{Id}_{T_xM} + t d\nu_x follows from |t| < \alpha and the uniform boundedness of d\nu_x on x \in M.

For the actual calculation of d\pi, let \tilde \pi_x : \mathbb{R}^k \times \mathbb{R} \rightarrow \mathbb{R}^k \times \mathbb{R} : (u,v) \mapsto (u,0) and notice that with \phi as in lemma 2, we have \phi^{-1} \circ \pi \circ \phi = \tilde \pi|_{M \times (-\varepsilon, \varepsilon)}. Since \tilde \pi is linear, we have d (\tilde \pi|_{M \times (-\varepsilon, \varepsilon)}) = \tilde \pi|_{T_x M \times \mathbb{R}} and

d\pi_{x + t \nu(x)} = d\phi_{(x,0)} \circ \tilde \pi \circ (d\phi_{(x,t)})^{-1}.

A straightforward calculation yields

d\phi_{(x,t)}(a,b) = (Id_{T_xM} + t d\nu_x) (a) + b \nu(x)

and we find that d\pi_{x + t \nu(x)}(u + v \nu(x)) = (Id_{T_xM} + t d\nu_x)^{-1}(u). \Box

Hence by lemma 4 and with p = x + t \nu(x) \in M_\alpha, d\pi_p is injective if T_p M_\alpha does not contain \mathbb{R} \nu(\pi(p)). This follows from T_p M_\alpha = \{\nabla P_\alpha (p)\}^{\perp}, \mathbb{R} \nu(\pi(p)) = \mathbb{R} \nabla f(\pi(p)) and \langle \nabla P_\alpha (p), \nabla f(\pi(p)) \rangle > 0 when \alpha > 0 is again sufficiently small.

3. Constructive approximation

To be continued… (some problems have yet to be solved).

Figure 1. Approximation of M = \phi^{-1}(0), where \phi(x, y) = \text{sign}((x^2 +y-1)^2 + (x + y^2 - 7)^2 - 105), using Bernstein polynomials of degrees 10, 20 and 40.  This figure is recuperated from a previous post.

fig.png

References

[1] Akbulut, S. and King, H. (1990). Some new results on the topology of nonsingular real algebraic sets. Bull. Amer. Math. Soc. (N.S.), 23(2), 441–446. http://projecteuclid.org/euclid.bams/1183555896.

[2] Nash, J. (1952). Real Algebraic Manifolds. Annals of Mathematics, 56(3), second series, 405–421. doi:10.2307/1969649

[3] Wallace, A. H. (1957). Algebraic Approximation of Manifolds. Proc. London Math. Soc. s3-7, 196–210

One thought on “Constructive approximation of compact hypersurfaces

  1. Pingback: Constructive approximation on compact manifolds | Math. Stat. Notes

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s