# 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.

## 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

## 4 thoughts on “Constructive approximation of compact hypersurfaces”

1. […] hypersurfaces. I wasn’t able to get a constructive result in time, so I left it as a draft. [I posted a much improved follow up in April.] I the document, I sketch a proof of the […]

2. […] Sunday afternoon project. The idea seems to work. I also think it is possible to get topological garanties for the reconstruction of the classification boundary, using the Nash-Tognoli theorem. […]

3. […] Constructive approximation of compact hypersurfaces […]

4. […] there is hope that we may approximate $f$ in a neighborhood of the curve. In fact, as I show in this post (a particular case of the Nash-Tognoli theorem), approximating both and its gradient in the sup […]