Erdös distance problems in normed spaces
type: Item
instance of: scholarly article
title: Erdös distance problems in normed spaces
zbMATH Open document ID: 0860.52008
DOI: 10.1016/0925-7721(95)00019-4
published in: Computational Geometry
publication date: 1997-04-21T00:00:00Z
review text: The investigations trace back to an old Erdös problem [\textit{P. Erdös}, Am. Math. Mon. 53, 248-250 (1946; Zbl 0060.34805)]. The author studies the problems of the maximum of unit distances, largest distances and smallest distances among \(n\) points in a two-dimensional normed space. For each norm \(|\cdot|\) on \(\mathbb{R}^2\) let \(\lambda(|\cdot|)\) be the length of the longest line-segment contained in the boundary of the unit disc \(\{x: |x|\leq 1\}\). (It holds \(0\leq \lambda(|\cdot|\leq 2\) and \(\lambda(|\cdot|)=0\) iff the norm is strictly convex and \(\lambda(|\cdot|)=2\) iff the unit disc is a parallelogram.) The exact maximum numbers of largest and smallest distances for each normed space is determined, the maximum numbers of unit distance for each normed space in which the unit sphere is not strictly convex. Some remarkable results are: 1. Let \(u(n)\) be the maximum number of occurrences of the unit distance in a set of \(n\) points in \((\mathbb{R}^2,|\cdot |)\). For \(n\geq 11\) yields -- \(c_1n\log n\leq u(n)\leq c_2n^{3/4}\), if \(\lambda(|\cdot |)=0\), -- \(u(n)= \lfloor n^2/4\rfloor\), if \(0<\lambda(|\cdot|)\leq 1\), -- \(u(n)= \lfloor(n^2+ n)/4\rfloor\), if \(1<\lambda(|\cdot|)\leq 2\). 2. Let \(l(n)\) be the maximum number of occurrences of the largest distance in a set of \(n\) points in \((\mathbb{R}^2,|\cdot|)\). Then -- \(l(n)=n\), if \(\lambda(|\cdot|)=0\), -- \(l(n)=\lfloor n^2/4\rfloor\), if \(0<\lambda(|\cdot|)\leq 1\), -- \(l(n)=\lfloor n^2/4\rfloor+1\), if \(1<\lambda(|\cdot|)< 2\), -- \(l(n)=\lfloor n^2/4\rfloor+2\), if \(\lambda(|\cdot|)=2\). 3. Let \(S(n)\) be the maximum number of occurrences of the smallest distance in a set of \(n\) points in \((\mathbb{R}^2,|\cdot|)\). Then -- \(s(n)=\lfloor 3n-\sqrt {12n-3}\rfloor\), if \(\lambda(|\cdot|)<2\), -- \(s(n)=\lfloor 4n-\sqrt {28n-12}\rfloor\), if \(\lambda(|\cdot|)=2\). The author gives also a lot of interesting lemmas and consequences, and he includes results from other paper…
reviewed by: Erhard Quaisser
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 51M04
Mathematics Subject Classification ID: 52A40
zbMATH DE Number: 902885
zbMATH Keywords: Erdös problems
zbMATH Keywords: distance problems
zbMATH Keywords: extremal configurations of points
zbMATH Keywords: normed space
author: Peter Brass
MaRDI profile type: Publication
full work available at URL: 0925-7721(95)00019-4
OpenAlex ID: W2018107997
cites work: Unit distances
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: Unit-Distance Graphs in Minkowski metric spaces
cites work: On Sets of Distances of n Points
cites work: Q3684740
cites work: ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
cites work: On a conjecture of H. Hadwiger
cites work: Über Treffanzahlen bei translationsgleichen Eikörpern
cites work: Q4186365
cites work: Q4091941
cites work: Q5186278
description: scientific article; zbMATH DE number 902885