





















A well-known theorem in plane geometry 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 in the plane with the $L_1$ (also called Manhattan) metric, a non-collinear set of $n$ points induces at least $\lceil n/2\rceil$ lines. This is an improvement of the previous lower bound of $n/37$, with substantially different proof. As a consequence, we also get the same lower bound for non-collinear point sets in the plane with the $L_{\infty}$ metric.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。