2012/07/16 by Ida Kantor, Balázs Patkós, Kantor, Ida +1
Mathematics · Physics and Astronomy · #Advanced Differential Geometry Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric Analysis and Curvature Flows #Geometry and complex manifolds
paper · pdf · doi:10.48550/arxiv.1207.3688
openalex publication_date 2012/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A well-known theorem of de Bruijn and Erdős states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of \em betweenness. In this paper, we prove that the answer is affirmative for sets of n points in the plane with the L1 metric, provided that no two points share their x- or y-coordinate. In this case, either there is a line that contains all n points, or X induces at least n distinct lines. If points of X are allowed to share their coordinates, then either there is a line that contains all n points, or X induces at least n/37 distinct lines.