Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
The distinct distances conjecture of \textit{P. Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)] asserts that any \(n\) points in the plane determine \(\Omega(n /\sqrt{\log n})\) distinct distances. He showed that an \(\sqrt{n}\times \sqrt{n}\) grid has only \(\Omega(n /\sqrt{\log n})\) distinct distances. \textit{L. Guth} and \textit{N. H. Katz} [Ann. Math. (2) 181, No. 1, 155--190 (2015; Zbl 1310.52019)] essentially solved the distinct distances conjecture proving that any \(n\) points in the plane determine \(\Omega(n /{\log n})\) distinct distances. \textit{P. Erdős} and \textit{P. Fishburn} [Discrete Math. 160, No. 1--3, 115--125 (1996; Zbl 0868.52007)] investigated the ``small cases'' of the problem, as opposed to the ``big cases'': for a given \(k\), how many points in the plane can define at most \(k\) distinct distances, and what are the extremal point configurations. They found answers for \(k\leq 4\), the case \(k=5\) was resolved by \textit{M. Shinohara} [Discrete Math. 308, No. 14, 3048--3055 (2008; Zbl 1144.05025)], and the case \(k=6\) was resolved by \textit{W. Xianglin} [Electron. J. Comb. 19, No. 4, Research Paper P38, 17 p. (2012; Zbl 1270.52022)], and the cases \(k\geq 7\) are still open. \textit{J. Garibaldi} et al. [The Erdős distance problem. Providence, RI: American Mathematical Society (AMS) (2011; Zbl 1234.00002)] investigated the distinct distances problem in the \(\ell_1\)-norm instead of the \(\ell_2\)-norm of the original problem. The paper under review solves the distinct distances problem in the plane in the \(\ell_1\)-norm for any \(k\), and in the 3-space for \(k=1\). Many ideas are presented towards the solution of the distinct distances problem in any dimension in the \(\ell_1\)-norm.
scientific article