Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $(X,d)$ be a compact metric space of finite diameter. Recall that we can always compute the Hausdorff distance between subsets $A, B \subset X$ via $$ d_H(A,B) = \max\left[\sup_{a\in A}\inf_{b\in B}d(a,b), \sup_{b\in B}\inf_{a\in A}d(a,b)\right]$$

Here is a simple question:

Is there a nice (pseudo-)metric structure on the set of all finite polyhedral decompositions of $X$?

For instance, if two such decompositions $P_1$ and $P_2$ had the same number of polyhedra, one could always use the infimum over all bijections $\phi: P_1 \to P_2$ of the largest Hausdorff distance between polyhedra $p \in P_1$ and $\phi(p) \in P_2$. But in general there is no reason to assume that $|P_1| = |P_2|$. Is there a standard way to deal with this general case?

share|improve this question
3  
What is "polyhedral decomposition of metric space"? –  Anton Petrunin Apr 26 '12 at 18:02
add comment

1 Answer

up vote 2 down vote accepted

How about we look at the set $S$ of pairs of points $(x,y)$ that are in the same cell of $P_1$ but in different cells in $P_2$ or vice-versa. Then the volume of this set might work as a metric if you have a measure on $X\times X$.

Edit. On second thought, this might be more the kind of idea you're looking for: for any set $A$ let $A_\epsilon = \{x:d(x,A)\le\epsilon\}$ be its $\epsilon$-parallel body. The Hausdorff distance $d(A,B)$ is minimum value of $\epsilon$ such that $B\subseteq A_\epsilon$ and $A\subseteq B_\epsilon$. Therefore, for decompositions $P$ and $Q$ let $d(P,Q)$ be the minimum value of epsilon such that for each $A\in P$ there is a $B\in Q$ such that $A\subseteq B_\epsilon$ and for each $A\in Q$ there is a $B\in P$ such that $A\subseteq B_\epsilon$.

share|improve this answer
    
Thanks, the edited idea with the epsilon-thickened sets is perfect! –  Vidit Nanda Apr 26 '12 at 19:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.