I didn't use the hint, so my solution looks different. I also don't get how the intended solution works -- you can't choose the cubes in small enough to make sure that is constant on each cube , so may not be convex. This seems to kill the straight-line solution, and I didn't see a way to salvage it.
Here's what I did in one paragraph. Divide both and into cubes. For any horizontal edge in , make sure hits the centers of all cubes that touches on points within distance of (where is at least the diameter of a cube in ), while moving around only within those cubes. Extend to without wandering off too far, and voilà.
- Embed and into unit cubes
- Cut the unit cubes into small cubes
- Prove a bunch of helpful Lemmas
- Define on some subset of the unit cube containing
- Argue that this approximates on
(1) Since and are compact and hence bounded, we can scale them down such that we can consider them subspaces of the unit cubes, i.e., and , where we choose as small as possible. (This is the abbreviated version of working with embedding functions.)
(2) By cutting each interval into pieces, i.e., , we obtain small cubes in of the form
where . Enumerate these cubes as . An analogous construction for yields .
Given any set , we define the operator to 'expand' to all the cubes that it touches, i.e.,
(3) We do most work via paths. This requires a bunch of Lemmas.
Lemma 1. For any connected set , the set is connected.
Proof. Let be a separation into two closed sets. Suppose first there is a point not entirely contained in or . Then, and is a separation of , contradicting the fact that is convex (and hence (path)-connected.) Thus, each either lies entirely in or entirely in .
Since is closed, so is and (where is the graph of ), which is simply . (The preimage function is well-defined for and due to the result from the previous paragraph, and the projection is closed because is compact.) Analogously, is closed. Then, is a separation of , implying that (because is connected), one of them is the empty set. Since , this implies that or .
This is only needed to prove Lemma 2.
Lemma 2. For any connected set , the set is path-connected.
Proof. The set consists of cubes in . Consider the graph where all cubes in are nodes, and there is an edge between two nodes iff the cubes share at least a point. If this graph were disconnected, then there would be a minimal distance between the sets of cubes corresponding to two disconnected parts of the graph. This yields a separation of , which is also a separation of , contradicting the previous lemma. (The distance can, in fact, be lower-bounded, but it suffices to use the fact that two closed disjoint sets in a metric space have non-zero distance.) Thus, is connected. This allows us to construct a path between the center points of two arbitrary cubes in (since there is a corresponding path in and the straight-line connection between the centers of two cubes that share at least one vertex yields a continuous path). Now, given two points and two cubes such that and , we can construct a path from to via
Lemma 3. Given and any path-connected space , all functions from to are homotopic.
Proof. Let . Define a homotopy by the rule . Then, is , and is a constant map, proving that is null-homotopic. Since being homotopic is an equivalence relation (and any two constant maps are trivially homotopic in a path connected space), it follows that all maps are homotopic to each other.
(4) Let be a parameter that depends on . We will specify how is chosen in the last part of the proof. It will have the properties that it's at least as large as the diameter of a cube and that it converges to as grows.
Let be connected. We define two operators on . The first is the set of points in that wish for to hit on points near it. We set
where . The second is a sufficiently small subspace of that is guaranteed to contain all points that touches on . We set . Note that this set is identical to , which makes it path-connected by Lemma 2.
We now want to define a partial function . We begin by defining it on vertices, then generalize it to specific edges, then specific faces, and so on, until we define it on all cubes that intersect .
A vertex is defined to be a point of the form
for some . The set may be empty if is too far outside , in which case we leave undefined on . If it is not empty, choose arbitrarily and set .
We now turn to edges. However, we only consider 'horizontal' edges, that is, subspaces of the form
for some . Let and be the two vertices of . If is undefined on either, we leave it undefined on . If not, we define it in the following. Note that this is the step where we guarantee that hits all points in the target set.
We know from Lemma 3 that there is a path from to . Since is homeomorphic to , it's easy to transform into a 'path' . But we can do even better and construct a path that starts at , ends at , and hits all points in on the way. (All trivial since is path-connected.) Now we simply set .
We next consider all 'horizontal-vertical' faces, that is, all sets of the form
for some . Let and be the two horizontal edges of . If is undefined on either, we leave it undefined on . If not, we have two paths and which implement on and , respectively. Using Lemma 3, we obtain a homotopy that continuously deforms into . Since our face is homeomorphic to , it's easy to transform into a function . Now we simply set .
Now we do the same for 3-dimensional subspaces of the form
where has been defined on the two horizontal-vertical faces, and so on. This way, every -dimensional subspace of this kind contains precisely two -dimensional subspaces of this kind, and if we have defined on both, we can apply a construction analogous to the above to define on the -dimensional subspace. Eventually, we define on -dimensional subspaces, which are precisely our cubes. (In the case of -dimensional subspaces, the definition above doesn't pose any restriction; it coincides with the definition of a cube ). Importantly, this defines on any cube that intersects . (This is so because any vertex of this cube is within of , which means that it has non-empty area. This implies that we have defined on any edge, face, and so on, of .) Thus, we end up having defined on some subspace of that includes all cubes that intersect .
The advantage of this construction is that, for any , we know that is contained in , which is the same as the union of all cubes in that touches on points near . If we had used the homomorphic extension of instead (i.e., connecting via straight lines), we could merely guarantee that is contained in the convex hull of certain points in , which may be much larger.
(5) Having defined on a subset of that contains , we take a projection , and define by the rule . It remains to show that our construction is such that the Hausdorff distance between and converges to 0 as , then the distance between and converges to as well. (To see this, note that, if is within of (which lies in ), then can move it by at most , which means that is within of .)
To do this, we now explain how is chosen, and then argue that the Hausdorff distance can be upper-bounded by some constant times .
The issue we have to deal with is that, by default, a point on the boundary of may not have any edge close to it that is contained in . (In fact, it may not even have an edge close to it that intersects .) Thus, we would like to be so large that any -ball around a point in must contain a -ball entirely contained in , where is larger than the diameter of a cube. In that case, any is within of a cube entirely contained in and thus also within of an edge entirely contained in .
It remains to show that we can choose such that it (a) has this property and (b) converges to as a function of . To show this, we consider fixed, and show that eventually grows large enough for that to suffice.
For every point , there exists some such that contains some -ball entirely contained in . Define a function that each point to the supremum of such 's. Then, is a continuous function from a compact set to , which means it takes on a minimum value. It now suffices to choose large enough that the diameter of a cube is smaller than this minimum. (To verify that is continuous, take a sequence of points in , assuming that doesn't converge, and derive a contradiction.)
With this out the way, we return to the proof that is the Haudorff limit of the . This consists of showing two parts:
- for any point on (the graph of ), there exists a close point on (i.e., comes sufficiently close to all points on ); and
- for any point on , there exists a close point on (i.e., has no points too far away from ).
Both are now easy:
- Let , and let be a cube that contains . Let be an edge with distance at most to . By construction, we have , which means that there is a point such that . Since and , the distance between and converges to as .
- Let , and let be a cube containing . Since , it follows that , which means there exists a point such that , which is to say, such that there is a for which . Now and , and thus the distance between and again converges to as .