Dimension reduction for ultrametrics
Yair Bartal, Manor Mendel · 2004
Abstract We prove that an ultrametric on n points can be embedded in `dp with distortion at most 1 + ", and d = O("-2 log n). This bound matches the best known bound for the special case of an equilateral space. 1 Introduction The distortion of an embedding f: X! Y between themetric spaces ( X, dX) and (Y, dY), is defined as