6
$\begingroup$

I have been studying Viro's textbook "Elementary Topology" and in the process of solving it I came across the following problem (in the textbook itself it has the number $4.Px$): Prove that on the set of convex polygons the metric $d_\triangle$ is equivalent to the Hausdorff metric.

The metric $d_\triangle$ is defined on the set of bounded polygons in the plane and maps a pair of elements of this set to the area of their symmetric difference. The Hausdorff metric is defined on the set of bounded closed subsets of an arbitrary metric space and looks like this: $d_\rho(A,B)=\max \lbrace \underset{a\in A}{\sup}\rho(a,B), \underset{b\in B}{\sup}\rho(b,A) \rbrace $ for bounded closed subsets $A,B$ of the metric space $(X,\rho)$.

To be honest, I don't have any ideas for a solution. The mechanism of applying the classical approach of proving the equivalence of two metrics (namely, demonstrating the inclusion of the first topology in the other and of the second topology in the first) seems unclear to me here, for it is not even fully visual or at least intuitive to see what the open ball represents on each of these metrics.

$\endgroup$
4
  • 1
    $\begingroup$ OK, I see. The statement is 4.Ex in the version I found. Right the next line. I was trying to prove they are not equivalent, so I got on that line quickly. You are right, what I am using for the equivalence is the version for a norm on vector spaces. $\endgroup$ Commented Jan 30 at 17:23
  • $\begingroup$ Linked. $\endgroup$ Commented Jan 30 at 19:33
  • $\begingroup$ To be clear, equivalent does not mean equal, right? We just want them to generate the same topology. $\endgroup$ Commented Jan 31 at 6:01
  • $\begingroup$ Exactly, we just want them to generate the same topology! $\endgroup$ Commented Jan 31 at 7:14

2 Answers 2

3
+50
$\begingroup$

This question turns out to be very hard. The above link by @AlexRavsky confirms this feeling. The nice answer by @Kusma explains all the key ideas, except the last part, which he said that he "can't give an even semi-formal proof". Let me give a stab.

So we want to show this. Suppose $P$ and $Q_n$ are convex polygons such that $d_\Delta(P,Q_n)\to 0$ but $d_\rho(P,Q_n)\geq \epsilon_0>0$, then we have a contradiction.

My argument now depends on how $d_\rho(P,Q_n)=\max\{\sup_{p\in P}\rho(p, Q_n), \sup_{q_n\in Q_n}\rho(q_n, P)\}$ is achieved, that is, whether there are points in $P\backslash Q_n$ or $Q_n\backslash P$. Since there are only two cases, taking a subsequence puts us in one of the two situations.

  1. $d_\rho(P,Q_n)=\sup_{p\in P}\rho(p, Q_n)\geq \epsilon_0$. That is, there is some point in $P$ that has a fixed distance from $Q_n$. Then this $p$ is a vertex of $P$, and the circular sector in $P$ with vertex $p$ and radius $\epsilon_0$ doesn't intersect $Q_n$, which is convex. If $\alpha$ is the smallest angle of $P$ (in radian), then $$ d_\Delta(P, Q_n)\geq \frac{1}{2}\alpha \epsilon_0^2, $$ and this contradicts $d_\Delta(P,Q_n)\to 0$.

  2. $d_\rho(P,Q_n)=\sup_{q_n\in Q_n}\rho(q_n, P)\geq \epsilon_0$. That is, there is some point $q_n\in Q_n$ that has a fixed distance from $P$. Then by projection, $\exists p_n\in P$ such that $\rho(p_n, q_n)=\rho(P, q_n)\geq \epsilon_0$. Then $p_n\in \partial P$. Suppose first $p_n$ is not a vertex, and so lies on the inside of an edge. Then $\overline{q_np_n}$ is perpendicular to this edge. Let $\ell$ be the smallest side-length of $P$. Since $d_\Delta(P,Q_n)\to 0$, there exists two points $r_n, s_n$ on the edge that belongs to $Q_n$ with $\rho(r_n, s_n)\geq \frac{\ell}{2}$. (The disks around the vertices of this edge must contain points in $Q_n$, since otherwise the $d_\Delta(P,Q_n)$ is big.) Then $Q_n$ would have a triangle $\Delta(q_n,r_n,s_n)$ (again since it is convex) whose area is $$ \geq \frac{1}{2}\frac{\ell}2 \epsilon_0. $$ This is a fixed number, so contradicts that $d_\Delta(P,Q_n)\to 0$. If the projection $p_n$ is a vertex of $P_n$, by arguing with the angles of $P$, we can still argue that there exists an edge of $P$ such that the height of $q_n$ above this edge is a positive fixed number in terms of $\epsilon_0$ and $P$. Concretely, there exists one edge of $P$ such that the height of $q_n$ above it is $$\geq \epsilon_0\min_{\beta}\sin\frac{\beta}{2},$$ where the minimum is taken over all interior angles $\beta$ of $P$. Then the above argument of a triangle with its base on this edge again applies.

$\endgroup$
2
$\begingroup$

To be frank, the Three aggies answer doesn't seem very clear or intuitive to me. However, as far as I can tell, the fairness of the evidence is there, so the bounty goes to him. The answer to my question, on the other hand, will be a proof that I have formulated myself:

Let us denote the set of convex polygons by $M$. First, we show the equivalence of the metric $d_\triangle$ and the metric $d_a(A,B)=\max(area(A\setminus B), area(B\setminus A))$. To do this, we show the inclusions $\Omega_\triangle\subset \Omega_a, \Omega_a\subset \Omega_\triangle$. Taking an arbitrary open set $U_\triangle$ of $\Omega_\triangle$, by the openness criterion, every point (in this case a convex polygon) $A$ of this set is in this open set with some open ball $B^\triangle_\varepsilon(A)=\lbrace X\in M\mid d_\triangle (A, X)=area(A\triangle X)< \varepsilon \rbrace$, but it is quite obvious that $B^a_{\varepsilon/2}(A)=\lbrace X\in M \mid d_a(A,X)=\max (area(A\setminus X), area(X\setminus A))<\varepsilon/2\rbrace$ is contained in $B_\varepsilon^\triangle$, since for $X\in B^a_{\varepsilon/2}(A)$ there will be $ area(A\triangle X)=area(A\setminus X)+area(X\setminus A )$$<2max(area(A\setminus X),area(X\setminus A))<\varepsilon $. We have shown the inclusion of $\Omega_\triangle\subset \Omega_a$. It's just as easy to show in the reverse direction that $B_\varepsilon^\triangle(A)\subset B_\varepsilon^a(A)$, since $area(A\setminus X)+area(X\setminus A)<\varepsilon \implies$$ \max(area(A\setminus X),area(X\setminus A))<\varepsilon$, so $\Omega_a\subset \Omega_\triangle$. We have then shown that $\Omega_\triangle=\Omega_a$, that is, the two metrics are equivalent.

Now let's notice a small detail that will come in handy later. Let's look at the set $A_C=\lbrace x\mid \rho(x,A)\leq C\rbrace$. It is not hard to see that if $A$ is bounded, $A_C$will be too. Moreover, if $A$ is a convex polygon, it is not hard to give an estimate of the area of the set $A_C$. Having drawn some examples for simple $A$ like equilateral triangles and squares, it becomes clear: $area(A_C)=\pi C^2+area(A)+Cp(A)$, where $p(A)$ is the perimeter of $A$. Why is this so? On each side of our given polygon we construct a rectangle of height $C$, and then at each vertex of our polygon we construct circles of radius $C$. Clearly, only points belonging to these sets will be in $A_C$. As an example, for the square $ABCD$, the set $A_C$ is bounded by the curve $EFGHIJKL$:

enter image description here

Let us also note another fact that will be useful to us: if we fix $A$ and $\varepsilon>0$, then there exists $\delta>0$ such that if $sup_{a\in A}\rho(a,B)\leq \delta$, then $B$ contains the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$. Such a set is a polygon, when $\varepsilon$ is small, of area at least $area(A)-\varepsilon p(A)$ (visually it is just a reduced version of $A$ inside $A$ itself). How to prove this? Suppose it is not true, that is, for all $\delta>0$, if $sup_{a\in A}\rho(a,B)\leq \delta$, then there still exists some point $x$ of the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$ such that it is not included in $B$. We find the side of $B$ nearest to this point and draw a perpendicular to it, denote the point of intersection with $B$ by the letter $b$, and the point of intersection with the boundary of $A$ such that $x$ is between $b$ and this boundary point by the letter $a$. In this case, $\rho(a,B)$ will be just the length of the segment $ab$ (this follows from the convexity of $B$). In turn, $\rho(a,b)\geq\rho(a,x) \geq \varepsilon$, since $x\in \lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$, so just take $\delta=\varepsilon$ and we get a contradiction.

Let us prove the same statement for areas: if we fix $A$ and $\varepsilon>0$, then there exists $\delta>0$ such that if $area(A\setminus B)\leq \delta$, then $B$ contains the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$. How to prove this? Suppose it is not true, that is, for all $\delta>0$, if $area(A\setminus B)\leq \delta$, then there still exists some point $x$ of the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$ such that it is not included in $B$. Find the side of $B$ nearest to this point and draw a perpendicular to it, denote the point of intersection with $B$ by the letter $b$, and the point of intersection with the boundary of $A$ such that $x$ is between $b$ and this point by the letter $a$. Let us draw a line through point $x$ parallel to the side of $B$ that is nearest to point $x$, and denote its intersection points with the boundary of $A$ as $a_1,a_2$. In this case, triangle $a_1aa_2$ will not be contained in $B$ but will be in $A$, and its area is ${1\over 2}\cdot (\rho(a_1,x)+\rho(x,a_2))\cdot \rho(a,x) \geq \varepsilon^2$, so $area(A\setminus B) \geq \varepsilon^2$ and we get a contradiction.

Knowing this, let us try to prove the equivalence of the metrics $d_a,d_\rho$. To do this, we will show the inclusions $\Omega_\rho\subset \Omega_a, \Omega_a\subset \Omega_\rho$.

  1. We first show the inclusion of $\Omega_\rho\subset \Omega_a$. Let's take an arbitrary open set $U_a$ of $\Omega_a$, by the openness criterion, every point (in this case a convex polygon) $A$ of this set enters it with some ball $B_\varepsilon^a(A)=\lbrace X\in M\mid d_a(A,X)=\max (area(A\setminus X), area(X\setminus A))<\varepsilon \rbrace$. We want to find such a number $\delta$ that $B_\delta ^\rho(A)\subset B_\varepsilon^a(A)$, that is, we actually want to prove that $\forall A\forall \varepsilon \exists \delta_1\forall X(sup_{x\in X}\rho(x, A)\leq \delta_1\implies area(X\setminus A) \leq \varepsilon)$ and that $\forall A\forall \varepsilon \exists \delta_2\forall X(sup_{a\in A}\rho(a,X)\leq \delta_2\implies area( A\setminus X)\leq \varepsilon)$, in which case we just take the minimum of $\delta_1,\delta_2$ as $\delta$ and we get what we need. The first of these conditions is not hard to prove: let us use the[detail noted earlier and say that if $sup_{x\in X}\rho(x,A)\leq \delta_1$, then $X\subset A_{\delta_1}$, so $area(X)\leq area(A_{\delta_1})$. Now we only need to solve the equation $area(X\setminus A)=area(X)-area(A)\leq area(A_{\delta_1})-area(A)=\pi\delta_1^2+$$\delta_1 p(A) \leq \varepsilon$ with respect to $\delta_1$ (why does $area(A)$ not appear here? The point is that we are considering the area $X\setminus A$, i.e. we have already taken away the area $A$). It is enough in this case to take $\delta_1=\min({\varepsilon \over 2p(A)},\sqrt{\varepsilon \over2\pi})$. To show that $\forall A\forall \varepsilon \exists \delta_2\forall X(sup_{a\in A}\rho(a,X)\leq \delta_2\implies area( A\setminus X)\leq \varepsilon)$ we use the previously proved fact and for a given $\varepsilon$ and a given polygon $A$ take $\varepsilon'=\varepsilon/p(A)$ and for $\varepsilon'$ find such a $\delta_2$, that if $sup_{a\in A}\rho(a,X)\leq \delta_2$, then $X$ contains $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon' \rbrace$. Since the area of $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon' \rbrace$ is not less than $area(A)-\varepsilon 'p(A)=area(A)-\varepsilon$, then $area(A\setminus X)$ is at most $area(A)-(area(A)-\varepsilon)=\varepsilon$ for such $\delta_2$ and there we have it. It remains to take $\delta=min(\delta_1,\delta_2)$ and for it we get the validity of both statements, and so we have shown the inclusion of $\Omega_\rho\subset \Omega_a$.
  2. Now let's show the inclusion of $\Omega_a\subset \Omega_\rho$. Cam we prove, for example, two statements, one of which is $\forall A \forall \varepsilon \exists \delta \forall X ( \mathrm{area}(X \setminus A) \leq \delta \Rightarrow \sup_{x \in X} \rho(x, A) \leq \varepsilon)$ as we did with the previous inclusion? We cannot, since it may happen that $X$ is very small and however far from $A$. So we have to prove the statement $\forall A \forall \varepsilon \exists \delta \forall X (\mathrm{area}(X \setminus A), \mathrm{area}(A \setminus X) \leq \delta \Rightarrow \sup_{x \in X} \rho(x, A), \sup_{a \in A} \rho(a, X) \leq \varepsilon)$ and perform similar reasoning to show inclusion. To prove this statement, we will also use one of the previously stated facts. First find $\delta_1>0$ for a fixed $\varepsilon$ such that if $area(A\setminus X)\leq \delta_1$, then $X$ contains the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus A)\geq \varepsilon \rbrace$. For such a $\delta_1$, we obviously have $\sup_{a \in A} \rho(a, X) \leq \varepsilon$. Then we find $\delta_2>0$ for a fixed $\varepsilon$ such that if $area(X\setminus A)\leq \delta_2$, then $A$ contains the set $\lbrace x\mid \rho(x,\mathbb R^2\setminus X)\geq \varepsilon \rbrace$. For such a $\delta_2$, we obviously have $\sup_{x \in X} \rho(x, A)\leq \varepsilon$, so for $\delta=min(\delta_1,\delta_2)$ we have $\mathrm{area}(X \setminus A), \mathrm{area}(A \setminus X) \leq \delta \Rightarrow$$ \sup_{x \in X} \rho(x, A), \sup_{a \in A} \rho(a, X) \leq \varepsilon$ and we've shown the second inclusion.
$\endgroup$
1
  • $\begingroup$ I apologize for the occasional messy formulas, I tried a lot of things, but apparently the math stack exchange itself displays formulas like that when they are too long. Maybe people with more experience can help. $\endgroup$ Commented Feb 6 at 10:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .