Minimum dimension embedding of finite metric spaces

AbstractGiven a set of n points with a table of distances, i.e., a finite metric space, can one realize these distances by appropriately chosen points in a metric space of a given type? The answer to this “isometric embedding problem” has long been known for the case of Lp embedding with p = 1,2 or ∞. In this paper we ask, given that a finite metric space is embeddable, what is the minimum dimension required and what is its maximum for fixed n and p? The answer is trivial only for p = 2. We develop methods and bounds for p = 1 and ∞