Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421165 | Discrete Applied Mathematics | 2014 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amit Ophir, Rom Pinchasi,