Suppose we are given a set of n points P = {p1, p2, ..., pn}, together
with 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 if
i /= j, and that d(pi, pi) = 0 for each i. We define a hierarchical
metric on P to be any distance function f that can be constructed as
follows. We build a rooted tree T on n leaves, and we associate with
each node v of T (both leaves and internal nodes) a height hv. 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 f (pi, pj) is defined as follows. We determine the
least common ancestor v in T of the leaves containing pi and pj , and
define f (pi, pj) = hv. We say that a hierarchical metric is
consistent with our distance function d if, for all pairs i, j, we
have f (pi, pj) <= d(pi.pj). Give a polynomial time algorithm that
takes the distance function d and produce a hierarchical metric with
the following properties.
(i) f is consistent with d, and
(ii) if g is any other hierarchical metric consistent with d, then
g(pi, pj) <= f (pi, pj) for each pair of points
pi and pj .
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
