embedding ultrametrics into low-dimensional spaces
We study the problem of minimum-distortion embedding of ultrametrics into the plane and higher dimensional spaces. Ultrametrics are a natural class of metrics that frequently occur in applications involving hierarchical clustering. Low-distortion embeddings of ultrametrics into the plane help visualizing complex structures they often represent.Given an ultrametric, a natural question is whether we can efficiently find an optimal-distortion embedding of this ultrametric into the plane, and if not, whether we can design an efficient algorithm that produces embeddings with near-optimal distortion. We show that the problem of finding minimum-distortion embedding of ultrametrics into the plane is NP-hard, and thus approximation algorithms are called for. Given an input ultrametric M , let c denote the minimum distortion achievable by any embedding of M into the plane. Our main result is a linear-time algorithm that produces an O(c 3 )-distortion embedding. This result can be generalized to embedding ultrametrics into R d , for any d ?2, with distortion c O(d) , where c is the minimum distortion achievable for embedding the input ultrametric into R d .Additionally, we show that any ultrametric can be embedded into the plane with distortion O(?n) , and in general, into R d with distortion d O(1) n 1/ d . Combining the two results together, we obtain an O(n 1/3 )-approximation algorithm for the problem of minimum-distortion embedding of ultrametrics into the plane.
embedding ultrametrics approximation algorithms