Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
type: Item
instance of: scholarly article
title: Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
zbMATH Open document ID: 1446.52012
author: Vajresh Balaji
author: Olivia Edwards
author: Anne Marie Loftin
author: Solomon Mcharo
author: Lo Phillips
author: Alex Rice
author: Bineyam Tsegaye
published in: Involve
publication date: 2020-08-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/1911.08067
review text: 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.
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 51K05
zbMATH DE Number: 7235830
zbMATH Keywords: Erdős distance problem
zbMATH Keywords: \(\ell_1\) metric
zbMATH Keywords: discrete geometry
zbMATH Keywords: geometric combinatorics
reviewed by: László A. Székely
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2990431409
arXiv ID: 1911.08067
cites work: Embedding into rectilinear spaces
cites work: On Sets of Distances of n Points
cites work: Maximum planar sets that determine \(k\) distances
cites work: Q3066502
cites work: On the Erdős distinct distances problem in the plane
cites work: Equilateral dimension of the rectilinear space
cites work: Uniqueness of maximum planar five-distance sets
cites work: A proof of Erdős-Fishburn's conjecture for \(g(6)=13\)
DOI: 10.2140/INVOLVE.2020.13.487
description: scientific article