Point sets in Euclidean space with a small number of distinct distances - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:05:12Z http://mathoverflow.net/feeds/question/80223 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80223/point-sets-in-euclidean-space-with-a-small-number-of-distinct-distances Point sets in Euclidean space with a small number of distinct distances Edmund Harriss 2011-11-06T16:44:29Z 2012-07-28T00:12:40Z <p>It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general question is what happens when we allow more than one distance?</p> <p>On the plane it is a good exercise to show that this is the complete list of diagrams with 2 distances and 4 or 5 points:</p> <p><img src="http://www.mathematicians.org.uk/eoh/2d_2-distance.png" alt="Sets on the plane with 2 distinct distances"></p> <p>You can go further on the plane for example see:</p> <p>Harborth, H and Piepmeyer, L (1996). Three distinct distances in the plane<br> <em>Geometriae Dedicata</em> <strong>61</strong>, No. 3, 315-327<br> <a href="http://www.springerlink.com/content/u35183155g06115r/" rel="nofollow">http://www.springerlink.com/content/u35183155g06115r/</a></p> <p>Shinohara, M (2008). Uniqueness of maximum planar five-distance sets.<br> <em>Discrete Mathematics</em>, <strong>308</strong>(14), 3048-3055.<br> <a href="http://linkinghub.elsevier.com/retrieve/pii/S0012365X07006498" rel="nofollow">http://linkinghub.elsevier.com/retrieve/pii/S0012365X07006498</a></p> <p>What about higher dimensions? The cross-polytope in n-dimensions is always a 2-distance set with 2n points. Even better taking the set of mid-points of edges of the n-simplex gives a 2-distance set with n(n+1)/2 points (of course in 3d this gives the vertices of the octahedron). Are their better examples?</p> <p>My motivation for this is mainly visual, the requirements that a small set of distances places on symmetry mean that these sets should give interesting forms. It should also be noted that (perhaps unsurprisingly given the elementary nature) it was also a problem that attracted Erdös, for example see:</p> <p>Erdös, P (1970) On Sets of Distances of n Points<br> <em>The American Mathematical Monthly</em> <strong>77</strong>, No. 7, pp. 738-740 <a href="http://www.jstor.org/pss/2316209" rel="nofollow">http://www.jstor.org/pss/2316209</a></p> <p>To finish with a precise question: What is known about n-distance sets in 3 and 4 dimensions?</p> http://mathoverflow.net/questions/80223/point-sets-in-euclidean-space-with-a-small-number-of-distinct-distances/80229#80229 Answer by Joseph O'Rourke for Point sets in Euclidean space with a small number of distinct distances Joseph O'Rourke 2011-11-06T18:02:25Z 2012-07-27T21:35:23Z <p>Here I mention some asymptotic results&mdash;valid when the number of points $n$ grows large&mdash;which may not be directly relevant to your concentration on few distances.</p> <p>The 2003 paper, "<a href="http://dl.acm.org/citation.cfm?id=780621" rel="nofollow">Distinct distances in three and higher dimensions</a>," by Aronov, Pach, Sharir, Tardos, established that the number of distinct distances determined by $n$ points in $\mathbb{R}^3$ is $\Omega( n^{77/141 - \epsilon} )$ for any $\epsilon > 0$. Their result holds for points on a sphere as well. For $\mathbb{R}^d$ they achieved a lower bound of about $n^{1/(d-90/77)}$, again also for points on a $d$-sphere.</p> <p>These lower bounds can be contrasted to the number of distinct distances achieved by points in a $n^{1/d} \times ... \times n^{1/d}$ integer lattice, which is $O(n^{2/d})$. Erdős conjectured the matching lower bound $\Omega(n^{2/d})$.</p> <p>A bit later (2006), their results were improved by Solymosi and Vu in the paper, "<a href="http://www.springerlink.com/content/k37347437l4l28n3/" rel="nofollow">Near optimal bounds for the Erdős distinct distances problem in high dimensions</a>," establishing $\Omega(n^{(2/d)-2/(d(d+2))})$. </p> http://mathoverflow.net/questions/80223/point-sets-in-euclidean-space-with-a-small-number-of-distinct-distances/80248#80248 Answer by Gerry Myerson for Point sets in Euclidean space with a small number of distinct distances Gerry Myerson 2011-11-06T21:47:54Z 2012-07-28T00:12:40Z <p>There's a nice book by Garibaldi, Iosevich, and Senger, <em>The Erdos Distance Problem</em>, in the Student Mathematical Library series of the American Mathematical Society (<a href="http://www.ams.org/bookstore-getitem/item=STML-56" rel="nofollow">AMS link</a>; <a href="http://www.amazon.com/Distance-Problem-Student-Mathematical-Library/dp/0821852817" rel="nofollow">Amazon link</a>). Mostly it's about the problem in the plane, but there is some discussion of, and references to, work on higher dimensions. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/ErdosDistance.jpg" alt="book cover"></p> http://mathoverflow.net/questions/80223/point-sets-in-euclidean-space-with-a-small-number-of-distinct-distances/80250#80250 Answer by Igor Rivin for Point sets in Euclidean space with a small number of distinct distances Igor Rivin 2011-11-06T22:04:11Z 2011-11-06T22:04:11Z <p>This paper:</p> <p><a href="http://maths.ucd.ie/~osburn/lattices.pdf" rel="nofollow">http://maths.ucd.ie/~osburn/lattices.pdf</a></p> <p>Has very cool results/connections of this (essentially, the question is: if you assume that lattices are best, which lattices are best among them).</p>