Nearly equal distances and Szemerédi's regularity lemma

DOI10.1016/J.COMGEO.2005.06.002MaRDI QIDQ2489544zbMATH OpenOpenAlexWikidataFDO

Authors János Pach, Radoš Radoičić, Jan Vondrák

Publication date 28 April 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.06.002

zbMATH Keywords

Erdős problemsrepeated distancesseparated sets

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Review text

An aim of this note is the following theorem: Let \(\varepsilon >0\) be fixed and let \(P\) be a separated set of \(n\) points in \(\mathbb{R}^3\) containing at least \(\varepsilon n^2\) pairs \((u,v)\), \(u,v\in P\), with \(\|u-v\|\in[t,t+1]\) for some fixed real number \(t>0\). Then the diameter of \(P\) is at least constant times \(n\) \((\text{diam}(P)=\Omega(n))\). At this a point set is called separated if the minimum distance between two elements is one. This result proves a conjecture by \textit{P. Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)] and \textit{P. Erdős}, \textit{E. Makai} and \textit{J. Pach} [Comb. Probab. Comput. 2, No. 4, 401--408 (1993; Zbl 0798.52017)]. In the proof the Szemerédi's regularity lemma and a Ramsey-type result for dot products of vectors are used.

Recommendations

• On the diameter of separated point sets with many nearly equal distances
• Nearly Equal Distances in the Plane
• Popular distances in 3-space
• Two and a half billion years of distance research
• A Problem of Leo Moser About Repeated Distances on the Sphere

Cites work

• Combinatorial complexity bounds for arrangements of curves and spheres
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing patterns of semi-algebraic sets
• Cutting circles into pseudo-segments and improved bounds for incidences
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 17642 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1943971 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• Nearly Equal Distances in the Plane
• On Sets of Distances of n Points
• Research Problems in Discrete Geometry

Cited in

(3)

• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Nearly equal distances in metric spaces
• On the diameter of separated point sets with many nearly equal distances

This page was built for publication: Nearly equal distances and Szemerédi's regularity lemma

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