# Metric on the set of Polyhedral Decompositions of a Compact Metric Space

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?

• What is "polyhedral decomposition of metric space"? – Anton Petrunin Apr 26 '12 at 18:02

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$.