Article ID Journal Published Year Pages File Type
421165 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract

Let (X,d)(X,d) be any finite metric space with nn elements. We show that there are two pairs of distinct elements in XX that determine two nearly equal distances in the sense that their ratio differs from 1 by at most 9lognn2. This bound (apart for the multiplicative constant) is best possible and we construct a metric space that attains this bound.We discuss related questions and consider in particular the Euclidean metric space.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,