Publication at Faculty of Mathematics and Physics |
2013
Abstract
A well-known theorem of de Bruijn and Erdos states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvatal 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.