Suppose we are given a set of points P = {P1 , P2 , · · · , Pn }, together with a distance function d on the set P ; d is simply a function on pairs of points in P with the properties that d(pi , pj ) = d(pj , Pi ) > 0 iff i = j,and that d(pi , pi ) = 0 for each i.
We define a hierarchical metric on P to be any distance function τ that can be constructed as follows:
We build a rooted tree T with n leaves, and we associate with each node v of T (both leaves and internal nodes) a height h(v). These heights must satisfy the properties that h(v) = 0 for each leaf v, and if u is the parent of v in T , then h(u) ≥ h(v). We place each point in P at a distinct leaf in T .
Now, for any pair of points pi and pj , their distance τ (pi , pj ) is defined as follows: We determine the lowest common ancestor v in T of the leaves containing pi and pj , and define τ (pi , pj ) = h(v).
We say that a hierarchical metric τ is consistent with our distance function d if, for all pairs i, j, we have τ (pi , pj ) ≤ d(pi , pj ).
Give a polynomial-time algorithm that takes the distance function d and produces a hierarchical metric τ with the following properties.
1. τ is consistent with d, and
2. If τ is any other hierarchical metric consistent with d, then τ (pi , pj ) ≤ τ (pi , pj ) for each pair of points
pi and pj