Lines, betweenness and metric spaces

Abstract

A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $\Omega (\sqrt{n})$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $\Omega (n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $\Omega (n^{4/7})$ lines, improving the previous $\Omega (n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n/5w$, where $w$ is the number of different distances in the space, and we give an $\Omega (n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from \{1, 2, 3\}.

20 pages