论文标题
$ l_1 $公制的飞机上的线条
Lines in the plane with the $L_1$ metric
论文作者
论文摘要
平面几何形状中著名的定理指出，飞机中的任何一组$ n $非校分点都决定至少$ n $线。 Chen和Chvátal询问是否存在类似的陈述在有限的度量空间的框架内，并使用{\ em Innessness}的概念定义了线。 在本文中，我们证明，在$ L_1 $（也称为曼哈顿）度量的飞机上，这是一组非校准$ n $点的集合，至少会诱导$ \ lceil n/2 \ rceil $ lines。这是对$ n/37 $的先前下限的改进，其证明实质上不同。结果，我们还使用$ l _ {\ infty} $ metric获得了平面中的非电线点集的相同下限。
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.
