Near optimal bounds for the Erdos distinct distances problem in high dimensions

被引：37

作者：

Solymosi, Jozsef ^{[1
]}

Vu, Van H. ^{[2
]}

机构：

[1] Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2, Canada

[2] Dept Math, Piscataway, NJ 08854 USA

来源：

COMBINATORICA | 2008年 / 28卷 / 01期

基金：

加拿大自然科学与工程研究理事会; 美国国家科学基金会; 匈牙利科学研究基金会;

关键词：

D O I：

10.1007/s00493-008-2099-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the number of distinct distances in a set of n points in R-d is Omega(n(2/d-2/d(d+2))), d >= 3. Erdos conjecture is Omega(n(2/d)).

引用

页码：113 / 125

页数：13

共 15 条

[1]

[Anonymous], 2002, GRAD TEXT M

[2] Distinct distances in three and higher dimensions [J].

Aronov, B ;

Pach, J ;

Sharir, M ;

Tardos, G .

COMBINATORICS PROBABILITY & COMPUTING, 2004, 13 (03) :283-293

[3] A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY [J].

CHAZELLE, B ;

FRIEDMAN, J .

COMBINATORICA, 1990, 10 (03) :229-249

[4] THE NUMBER OF DIFFERENT DISTANCES DETERMINED BY A SET OF POINTS IN THE EUCLIDEAN PLANE [J].

CHUNG, FRK ;

SZEMEREDI, E ;

TROTTER, WT .

DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 7 (01) :1-11

[5] THE NUMBER OF DIFFERENT DISTANCES DETERMINED BY N-POINTS IN THE PLANE [J].

CHUNG, FRK .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1984, 36 (03) :342-354

[6] COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES [J].

CLARKSON, KL ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160

[7]

Erd??s P., 1946, AM MATH MONTHLY, V53, P248, DOI [10.1080/00029890.1946.11991674, DOI 10.1080/00029890.1946.11991674]

[8]

IOSEVICH A, IN PRESS PADOVA

[9]

MOSER L., 1952, AM MATH MONTHLY, V59, p[85, 91], DOI [10.1080/00029890.1952.11988075, 10.2307/2307105.MR, DOI 10.2307/2307105.MR]

[10]

Pach J., 1995, Wiley-Interscience Series in Discrete Mathematics and Optimization

← 1 2 →