Lines in the plane with the \(L_1\) metric (Q6050233)

A classical result in plane geometry states that \(n\) points in the plane are either collinear or they induce at least \(n\) lines. Such a result is a consequence of the Sylvester-Gallai theorem as noticed by Erdős and it is also a special case of a theorem of de Bruijn and Erdős about incidence structure. In [Discrete Appl. Math. 156, No. 11, 2101--2108 (2008; Zbl 1157.05019)], \textit{X. Chen} and \textit{V. Chvátal} asked when an analogous statement holds in the framework of finite metric spaces, with lines defined using betweenness. This question is still open, although a number of results related to it have been proved. In the paper under review, the author considers such a question for the plane equipped with the so-called Manhattan metric \(L_1\), and she proves the following result. Theorem. Let \(X\) be a set of \(n\) points in the plane with the \(L_1\) metric. If there is no universal line, then \(X\) induces at least \(\lceil n/2\rceil\) lines. Here, a \textit{universal} line of a set \(X\) is a line which contains all the points of \(X\). This theorem improves a previous result of the author and \textit{B. Patkós} [Discrete Comput. Geom. 49, No. 3, 659--670 (2013; Zbl 1410.51011)] and it is proved using a different method. In the last section, as a consequence of the case of the \(L_1\) metric, the author gets the same lower bound for non-collinear point sets in the plane with the \(L_\infty\) metric.