25. Suppose we are given a set of points P- (P1,P2,... .pal, together witha distance function d on the set P; d is simply a function on pairs of points in P with the properties that d(pi, P) = d(? p) > 0 ifi 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 hy. These heights must satisfy the properties that h(v)-0 for each 202 Chapter 4 Greedy Algorithms leaf v, and if u is the parent of v in T, then h(u) 2 h(v). We place each point in P at a distinct leaf in T. Now, for any pair of points p, and p, their distance (pi,p) is defined as follows, we determine the least common ancestor v in T of the leaves containing pi and pi, and define (pi, pj) =hu we say that a hierarchical metric is consistent with our distance function d if, for all pairs i, j, we have (pi, pi) d(pi, pi). Give a polynomial-time algorithm that takes the distance function d and produces a hierarchical metric with the following properties. (i) is consistent with d, and (i) lfr, is any other hierarchical metric consistent with d, then (pi, pj) t(P,P) for each pair of points pi and pj- 25. Suppose we are given a set of points P- (P1,P2,... .pal, together witha distance function d on the set P; d is simply a function on pairs of points in P with the properties that d(pi, P) = d(? p) > 0 ifi 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 hy. These heights must satisfy the properties that h(v)-0 for each 202 Chapter 4 Greedy Algorithms leaf v, and if u is the parent of v in T, then h(u) 2 h(v). We place each point in P at a distinct leaf in T. Now, for any pair of points p, and p, their distance (pi,p) is defined as follows, we determine the least common ancestor v in T of the leaves containing pi and pi, and define (pi, pj) =hu we say that a hierarchical metric is consistent with our distance function d if, for all pairs i, j, we have (pi, pi) d(pi, pi). Give a polynomial-time algorithm that takes the distance function d and produces a hierarchical metric with the following properties. (i) is consistent with d, and (i) lfr, is any other hierarchical metric consistent with d, then (pi, pj) t(P,P) for each pair of points pi and pj