To simplify a closed subset of the plane, approximate it using a grid of squares

Quick description

Suppose you have a closed subset of the plane and you want to prove something about it that seems fairly obvious but is troublesome to demonstrate rigorously.^◊ Then it may well help to take a grid of small squares and replace your set by the union of all the squares that overlap it.

Prerequisites

The basic theory of metric spaces

This article is incomplete. This article is in the process of being written.

Example 1

Let $D$ be a domain in the complex plane: that is, a connected open subset of $\C$ . Let $X$ be a closed bounded subset of $D$ . Is it always possible to find a closed curve in $D$ that has $X$ in its interior?

An initially encouraging observation is that $X$ is compact (because it is a closed bounded subset of $\C$ , which we can identify with $\R^2$ ), that the complement $F$ of $D$ is closed, and that $X$ and $F$ are disjoint. This implies that there is some $\delta>0$ such that the distance from any point in $X$ to any point in $F$ is always at least $\delta$ . The proof is that the distance $d(x,F)$ is a continuous function of $x$ . Since $X$ is compact, it must attain its infimum. But it is never zero, since $X\cap F=\emptyset$ , so the infimum must be some $\delta>0$ , as claimed. Or to put it another way, it implies that there is some $\delta>0$ such that for every $x\in X$ the ball of radius $\delta$ about $x$ is a subset of $D$ .

This is encouraging because it tells us that we ought to have "room to get round $X$ ". But how do we turn this nice feeling into a proper argument? A very useful trick is to use a grid of squares.

What we do is write the complex plane as a union of squares of diameter less than $\delta$ . To be unnecessarily safe, let us take $n$ to be an integer such that $n^{-1}<\delta/2$ , and let us take all squares of sidelength $n^{-1}$ that have vertices with coordinates that are integer multiples of $n^{-1}$ . Thus, a typical square in this grid will be of the form $[\frac{r-1}n,\frac rn]\times[\frac{s-1}n,\frac sn]$ .

Once we've done this, we replace $X$ by the union of all the squares in the grid that have a non-empty intersection with $X$ . This will be a new closed set (since it is a union of finitely many closed squares), still contained in $D$ (since the diameter of each square is less than the distance from $X$ to $F$ ). Let us call it $Y$ . If we can find a curve that contains $Y$ in its interior, then it will obviously contain $X$ in its interior as well. In fact, one can say slightly more, and this will be useful to us. Not only is $X$ contained in $Y$ , it is actually contained in the interior of $Y$ , since if any point $x$ is on the boundary of a square in the grid, then the neighbouring square (or squares if $x$ is a vertex) will also intersect $X$ and so will also form part of $Y$ . (In other words, it is important that we have taken closed squares and taken all the ones that intersect with $X$ , even if the intersection is just on the boundary.)

This tells us that we could if we wanted form the curve we are trying to form by going round the boundary of $Y$ . And indeed, this almost works, but it leaves us with two things to do. First, we need to say what "going round the boundary of $Y$ " means, and secondly we need to take account of the fact that $X$ might not be connected.

There is a nice trick that makes it possible to split the boundary of $Y$ up into a union of closed curves. First, you take all the squares that make up $Y$ , and you orient their edges — anticlockwise, say. Then any edge that's on the boundary of two squares will be oriented in one direction for one of the squares and the other direction for the other, so you cancel them out. What you will be left with after these cancellations is just the boundary edges of $Y$ , which form a directed graph. A brief consideration of the possible cases shows that each vertex of this graph (which will be a point with coordinates that are integer multiples of $n^{-1}$ ) has the same number of edges going in as coming out. This means that the graph itself can be decomposed into directed cycles using a greedy algorithm. You just start at a vertex that has at least one edge coming out of it, follow an out-edge, and keep following out-edges. Each time you arrive at a vertex and leave it, you have used one in-edge and one out-edge, so if you delete the edges that you have used, then all vertices will have the same number of in-edges as out-edges except the vertex where you are now (which has one more out-edge than in-edges) and the vertex where you started (which has one more in-edge than out-edges). This process cannot go on for ever, so at some point you must end up at the vertex where you started. If there are any edges left, then pick a new vertex with at least one edge coming out of it and repeat the process.

The above argument is slightly unsatisfactory for two reasons. First, we are trying to find one closed curve rather than several, and secondly the closed curves we have found can touch themselves, whereas we would prefer to find a simple closed curve. We shall deal with both these problems at once, again using the grid-of-squares trick.

We haven't quite stated it abstractly, but we have been using the following trivial observation: if $Z$ is any closed bounded subset of $D$ that contains $X$ , and if we can find a closed curve in $D$ that contains $Z$ in its interior, then we can find a closed curve in $D$ that contains $X$ in its interior. We attempted to use $Y$ for the purpose, but there are two inconvenient properties that $Y$ can have: it may be disconnected, in which case we will get more than one closed curve if we follow the boundary of $Y$ , or it may have two parts that touch each other just at a shared vertex, in which case we may get a closed curve that is not simple, or two simple closed curves that touch (depending on whether we go round the whole of a figure of eight or round each half separately).

How could we make $X$ connected? Well, $D$ is connected, so every point in $X$ can be joined to every other point by a path in $D$ . So couldn't we just add some connecting paths to $X$ ? We could try, but it isn't quite clear how to do that and keep $X$ compact, since we might have to add infinitely many paths. (For example, $X$ might be some highly disconnected set like a Cantor set.) However, we shouldn't forget what we have already noticed: that we can contain $X$ inside a closed bounded union $Y$ of squares that is still a subset of $D$ . And we can turn $Y$ into a connected set by adding finitely many paths: at most one path for each pair of squares in the union that forms $Y$ . Each path is compact, so adding the paths results in a compact set $W$ . We can now pick a new grid of squares, and if it is sufficiently fine, then the union $Z$ of all squares that have non-empty intersection with $W$ will be a subset of $D$ . What is more, it will be connected.

We are now ready to define the curve we were looking for. There is nothing in our discussion so far to stop $Z$ being a set with holes, such as an annulus. So we would like to find an external boundary point of $Z$ . This we can do by looking at the components of $\C\setminus Z$ , of which only one is unbounded. Call this set $U$ . Then let $V$ be the complement of $U$ . The set $V$ is closed and bounded, and it contains $Z$ . It is not necessarily contained in $D$ (because $D$ could have holes) but the boundary of $V$ is contained in the boundary of $Z$ , so the boundary of $V$ is contained in $D$ . Moreover, $V$ is a union of squares from our new grid.

To finish off the proof, let us do a little trick. We shall expand all the squares of $V$ very slightly, so that they are still contained in $D$ , but now you never have two squares intersecting in just a vertex. We then pick a boundary edge of $V$ and follow it for as long as possible. (Remember that each edge has a direction associated with it.) Each time we arrive at a vertex (or rather, very close to a vertex), we do not have any choice about what to do, since no two of the expanded squares intersect in exactly a vertex. So we just follow round until we get back to our starting point, which must eventually happen as there are only finitely many edges.

I'm slightly struggling here. I want to get away without proving (or assuming) the Jordan curve theorem, or doing something equivalent like defining winding number, but I'm not quite sure whether I can.

Comments

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

view commented text

The Case

Fri, 30/07/2010 - 19:31 — Sergio965

Isn't that always the case?

The answer to Example 1 is yes

Thu, 19/08/2010 - 09:30 — FelixKlein

Suppose first that X is semialgebraic. Consider the function f :C—> R defined by

f(z)= dist(z, X)

Then for all but finitely many positive numbers t the level set C_t={ f=t} is a smooth curve. For t sufficiently small C_t will be a curve that contains X in its interior {f< t}. As an aside, for t small, the set {f\leq t} is homotopy equivalent to X.

If X is not semialgebraic, then the pixellation Y that you constructed is compact, semialgebraic, contains X and is contained in D if the size of the squares is small enough. Now apply the previous construction to Y.

PS My PhD student has been investigating approximations of planar sets by grids of squares (or pixellations). He has obtained quite interesting results. If P_r if the pixellation of a semialgebraic set with squares of size r then one can algorithmically associate to P_r a PL set S_r that in a rather strong sense to X as r–>0. In particular, many geometric invariants of S_r (such as area, perimeter, curvature measures, Betti numbers) converge to the corresponding invariants of X.