On the minimum diameter of plane integral point sets
On the minimum diameter of plane integral point sets
复制标题
关于平面积分点集的最小直径
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Wassermann
中科院分区：
文献类型：
--
作者：
Sascha Kurz;A. Wassermann
平面积分点集 P 是平面上具有成对积分距离的 n 个点的集合，其中并非所有点都共线。最大出现距离称为其直径。 d(2, n) 表示由 n 个点组成的平面积分点集的最小可能直径。我们给出了一些新的精确值并描述了获取它们的算法。事实证明，具有最小直径的平面积分点集很可能由具有许多共线点的子集组成。对于这种特殊类型的点集，我们证明 d(2, n) 的下界可以实现上限 n2 log log n 直至一个常数。相反，如果不允许 3 个点共线，我们就称之为半一般位置，并用 d(2, n) 表示相应的最小直径。我们再次给出一些新的精确值。 Erdős 的一个著名问题要求平面积分点集，直线上没有 3 个点，圆上没有 4 个点。这里我们讨论一般位置的点集，并用 ḋ(2, n) 表示相应的最小直径。不幸的是，我们将 ḋ(2, 7) 的存在性作为一个悬而未决的问题，只能提供通过穷举搜索获得的下界 ḋ(2, 7) > 15, 000。
Plane integral point sets P are sets of n points in the plane with pairwise integral distances where not all the points are collinear. The largest occurring distance is called its diameter. By d(2, n) we denote the minimum possible diameter of a plane integral point set consisting of n points. We give some new exact values and describe the algorithms to obtain them. It turns out that plane integral point sets with minimum diameter consist very likely of subsets with many collinear points. For this special kind of point sets we prove a lower bound for d(2, n) achieving the upper bound n2 log log n up to a constant. If in contrary no 3 points are allowed to be collinear we talk of semi-general position and denote the corresponding minimum diameter by d(2, n). Again we give some new exact values. A famous question of Erdős asks for plane integral point sets with no 3 points on a line and no 4 points on a circle. Here we talk of point sets in general position and denote the corresponding minimum diameter by ḋ(2, n). Unfortunately we leave the existence of ḋ(2, 7) as an open question and can only provide the lower bound ḋ(2, 7) > 15, 000 obtained by an exhaustive search.