1
$\begingroup$

Ultrametric space are spaces which satisfy following conditions:

$d(x,y) \ge 0$

$d(x,y)=0$ iff $x=y$

$d(x,y)=d(y,x)$

$d(x,y) \le max\{d(x,a), d(y,a)\}$ for all $a$

Here the triangular ineuality of metric spaces is replaced by a stronger inequality. I am trying to figure out examples of ultrametric spaces which lie in $\mathbb{R}^2$. Am not able to construct a set of more than 3 points. Is that the upper limit

Context: I was reading the paper "Admissable clustering procedures" which said : Data is said to be well structured data if it has an exact tree i.e. it is possible to construct the similarity matrix using information from hierarchical structure. In this book "Cluster analysis: Survey and evaluation of techniques" i found the statement "To obtain an exact tree one must satisfy criteria of ultrametric inequality"

$\endgroup$
1
$\begingroup$

Yes it is. I'm not sure about the easiest way to prove this but a sketch is the following: Let $M=\{x,y,w,z\}\subset\mathbb{R^2}$. Note if any point is inside the triangle formed by the other three this violates the ultrametric property. So consider $\Delta xyw$. By above $z$ can't lie on the boundary or in the interior. Also 3 points can't be colinear as this also violates the ultrametric property. That means that $xywz$ forms a convex quadrilateral (if it is not convex then one point will lie in the interior of a triangle formed by the other three.

One of these angles must be greater than or equal to $\pi/2$. Call it $\angle xyz$. Then $\Delta xyz$ gives a contradiction since all triangles in an ultrametric space must be acute.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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