Sets in R^d determining k taxicab distances

DOI10.2140/INVOLVE.2020.13.487MaRDI QIDQ2192425zbMATH OpenOpenAlexFDO

Authors Vajresh Balaji, Olivia Edwards, Anne Marie Loftin, Solomon Mcharo, Lo Phillips, Alex Rice, Bineyam Tsegaye

Publication date 17 August 2020

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.08067

zbMATH Keywords

\(\ell_1\) metricdiscrete geometryErdős distance problemgeometric combinatorics

Mathematics Subject Classification ID

General theory of distance geometry (51K05) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: We address an analog of a problem introduced by ErdH{o}s and Fishburn, itself an inverse formulation of the famous ErdH{o}s distance problem, in which the usual Euclidean distance is replaced with the metric induced by the $el{l}^1$-norm, commonly referred to as the $extittaxicabmetric$. Specifically, we investigate the following question: given $d,kinmathbbN$, what is the maximum size of a subset of $mathbb{R}^d$ that determines at most $k$ distinct taxicab distances, and can all such optimal arrangements be classified? We completely resolve the question in dimension $d=2$, as well as the $k=1$ case in dimension $d=3$, and we also provide a full resolution in the general case under an additional hypothesis.

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.

Recommendations

• Distinct distances with \(\ell_p\) metrics
• Nearly k-distance sets
• Classification of three-distance sets in two dimensional Euclidean space
• On the distance formulae in the generalized taxicab geometry
• Two and a half billion years of distance research

Cites work

• A proof of Erdős-Fishburn's conjecture for \(g(6)=13\)
• Embedding into rectilinear spaces
• Equilateral dimension of the rectilinear space
• Maximum planar sets that determine k distances
• On Sets of Distances of n Points
• On the Erdős distinct distances problem in the plane
• The Erdős distance problem
• Uniqueness of maximum planar five-distance sets

Cited in

(7)

• The additive structure of Cartesian products spanning few distinct distances
• A reduction for the distinct distances problem in \(\mathbb{R}^d\)
• Distinct distances in homogeneous sets in Euclidean space
• Distinct Distances in Three and Higher Dimensions
• On the Erdős distinct distances problem in the plane
• A note on distinct distances in rectangular lattices
• Distinct distances with \(\ell_p\) metrics

This page was built for publication: Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192425)