### Resumen

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 Ω(n) lines. This is the first lower bound on the number of lines in general finite metric spaces that grows faster than logarithmically in the number of points. In the more general setting of pseudometric betweenness, we prove a corresponding bound of Ω (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 Ω (n^{4 / 7}) lines, improving the previous Ω (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 Ω (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}.

Idioma original | Inglés |
---|---|

Páginas (desde-hasta) | 427-448 |

Número de páginas | 22 |

Publicación | Discrete and Computational Geometry |

Volumen | 56 |

N.º | 2 |

DOI | |

Estado | Publicada - 1 sep 2016 |

Publicado de forma externa | Sí |

### Áreas temáticas de ASJC Scopus

- Ciencia computacional teórica
- Geometría y topología
- Matemáticas discretas y combinatorias
- Teoría computacional y matemáticas

## Huella Profundice en los temas de investigación de 'Lines, Betweenness and Metric Spaces'. En conjunto forman una huella única.

## Citar esto

*Discrete and Computational Geometry*,

*56*(2), 427-448. https://doi.org/10.1007/s00454-016-9806-2