MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
What is "polyhedral decomposition of metric space"? – Anton Petrunin Apr 26 '12 at 18:02
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|cite|improve this answer
Thanks, the edited idea with the epsilon-thickened sets is perfect! – Vidit Nanda Apr 26 '12 at 19:53

Your Answer


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.