Towards a de Bruijn–Erdős Theorem in the L1 -Metric

Ida, Kantor and Patkós, Balázs (2013) Towards a de Bruijn–Erdős Theorem in the L1 -Metric. DISCRETE AND COMPUTATIONAL GEOMETRY, 49 (3). pp. 659-670. ISSN 0179-5376

Preview

Text 1207.3688v1.pdf Available under License Creative Commons Attribution. Download (170kB) | Preview

Abstract

A well-known theorem of de Bruijn and Erd˝os states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chv´atal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of 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.

Actions (login required)

Edit Item