Lines, Betweenness and Metric Spaces

Pierre Aboulker, Xiaomin Chen, Guangda Huzhang, Rohan Kapadia, Cathryn Supko

Resultado de la investigación: Article

2 Citas (Scopus)

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 Ω (n2 / 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 Ω (n4 / 7) lines, improving the previous Ω (n2 / 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 Ω (n4 / 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 originalEnglish
Páginas (desde-hasta)427-448
Número de páginas22
PublicaciónDiscrete and Computational Geometry
Volumen56
N.º2
DOI
EstadoPublished - 1 sep 2016
Publicado de forma externa

Huella dactilar

Betweenness
Metric space
Geometry
Line
Lower bound
Euclidean geometry
Pseudometric
Connected graph
Distinct

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Citar esto

Aboulker, P., Chen, X., Huzhang, G., Kapadia, R., & Supko, C. (2016). Lines, Betweenness and Metric Spaces. Discrete and Computational Geometry, 56(2), 427-448. https://doi.org/10.1007/s00454-016-9806-2
Aboulker, Pierre ; Chen, Xiaomin ; Huzhang, Guangda ; Kapadia, Rohan ; Supko, Cathryn. / Lines, Betweenness and Metric Spaces. En: Discrete and Computational Geometry. 2016 ; Vol. 56, N.º 2. pp. 427-448.
@article{0968e445d84d4310877434ea4558e826,
title = "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{\'a}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 Ω (n2 / 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 Ω (n4 / 7) lines, improving the previous Ω (n2 / 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 Ω (n4 / 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}.",
keywords = "Chen–Chv{\'a}tal Conjecture, Graph metric, Lines, Metric spaces",
author = "Pierre Aboulker and Xiaomin Chen and Guangda Huzhang and Rohan Kapadia and Cathryn Supko",
year = "2016",
month = "9",
day = "1",
doi = "10.1007/s00454-016-9806-2",
language = "English",
volume = "56",
pages = "427--448",
journal = "Discrete and Computational Geometry",
issn = "0179-5376",
publisher = "Springer New York",
number = "2",

}

Aboulker, P, Chen, X, Huzhang, G, Kapadia, R & Supko, C 2016, 'Lines, Betweenness and Metric Spaces', Discrete and Computational Geometry, vol. 56, n.º 2, pp. 427-448. https://doi.org/10.1007/s00454-016-9806-2

Lines, Betweenness and Metric Spaces. / Aboulker, Pierre; Chen, Xiaomin; Huzhang, Guangda; Kapadia, Rohan; Supko, Cathryn.

En: Discrete and Computational Geometry, Vol. 56, N.º 2, 01.09.2016, p. 427-448.

Resultado de la investigación: Article

TY - JOUR

T1 - Lines, Betweenness and Metric Spaces

AU - Aboulker, Pierre

AU - Chen, Xiaomin

AU - Huzhang, Guangda

AU - Kapadia, Rohan

AU - Supko, Cathryn

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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 Ω (n2 / 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 Ω (n4 / 7) lines, improving the previous Ω (n2 / 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 Ω (n4 / 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}.

AB - 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 Ω (n2 / 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 Ω (n4 / 7) lines, improving the previous Ω (n2 / 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 Ω (n4 / 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}.

KW - Chen–Chvátal Conjecture

KW - Graph metric

KW - Lines

KW - Metric spaces

UR - http://www.scopus.com/inward/record.url?scp=84978877439&partnerID=8YFLogxK

U2 - 10.1007/s00454-016-9806-2

DO - 10.1007/s00454-016-9806-2

M3 - Article

AN - SCOPUS:84978877439

VL - 56

SP - 427

EP - 448

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 2

ER -

Aboulker P, Chen X, Huzhang G, Kapadia R, Supko C. Lines, Betweenness and Metric Spaces. Discrete and Computational Geometry. 2016 sep 1;56(2):427-448. https://doi.org/10.1007/s00454-016-9806-2