Point sets with distinct distances
Point sets with distinct distances
复制标题
具有不同距离的点集
DOI：
10.1007/bf01299744
复制
发表时间：
1995
期刊：
影响因子：
1.1
通讯作者：
Torsten Thiele
中科院分区：
文献类型：
--
作者：
H. Lefmann;Torsten Thiele
对于正整数sd和n，letfd（n）表示第三网格{1，2，.}的子集的最大基数，n}d具有不同的相互欧几里得距离。改进了Erdens和Guy的早期结果，证明了f ~ 2（n）≥c·n ~ 2/3，福特≥3，fd（n）≥cd·n ~ 2/3 ·（lnn）~（1/3），其中c，cd>0是常数.也改进了Erdens和Alon关于{12，222，. n2}，并证明了平面上任意n个点的集合都包含一个距离为1·n1/4的子集，且对于一般位置上的点集，即一条直线上没有三个点的距离为2·n1/3的点集，常数为sc 1，c 2>0.为了做到这一点，将表明，对于具有不同距离d1，d2，.的n个点，dt，其中di有重数mi，对正常数tc有∑i= 1 tmi 2 ≤c·n 3.25.若点在一般位置，则证明了对一个正的常数c，∑i= 1 tmi 2 ≤c·n3，且此界是紧的.此外，在更一般的情况下，我们给出了一个有效的序列算法，用于寻找给定集合的子集，该子集具有所需的性质，例如具有不同的距离，其大小由概率方法保证.
For positive integersd andn letfd(n) denote the maximum cardinality of a subset of thend-gird {1,2,...,n}d with distinct mutual euclidean distances. Improving earlier results of Erdős and Guy, it will be shown thatf2(n)≥c·n2/3 and, ford≥3, thatfd(n)≥cd·n2/3 ·(lnn)1/3, wherec, cd>0 are constants. Also improvements of lower bounds of Erdős and Alon on the size of Sidon-sets in {12,222,...,n2} are given.Furthermore, it will be proven that any set ofn points in the plane contains a subset with distinct mutual distances of sizec1·n1/4, and for point sets in genral position, i.e. no three points on a line, of sizec2·n1/3 with constantsc1,c2>0. To do so, it will be shown that forn points in ℝ2 with distinct distancesd1,d2,...,dt, wheredi has multiplicitymi, one has ∑i=1tmi2≤c·n3.25 for a positive constantc. If then points are in general position, then we prove ∑i=1tmi2≤c·n3 for a positive constantc and this bound is tight.Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.