Joshua Zucker wrote:

I got an interesting problem lately and neither I nor the proposer know the solution. Perhaps it is an open question? ... Examples (all in 2-D): ... For n points, the regular n-gon gives floor(n/2) different distances, and I conjecture that is the fewest possible distinct distances (based on not much evidence!), but in general that arrangement is not unique

For large n you can get fewer distances by using n points from the integer lattice. E.g. if n=m^2, use an m by m array of points. The number of distinct distances equals the number of distinct numbers of the form x^2+y^2 with 0 <= x < m, 0 <= y < m, and x and y not both 0. (Subtract 1 from the terms of A047800 in the OEIS.) This is less than the number of sums of 2 squares up to 2m^2, which grows like C m^2/sqrt(log(m)); see: http://mathworld.wolfram.com/Landau-RamanujanConstant.html The smallest square number n for which this construction gives fewer distances than a regular n-gon is n=144; a 12x12 grid has only 70 distinct distances. But there are probably smaller values of n for which the n-gon is not optimal; maybe taking a circular chunk of the integer lattice would work better. Or maybe a lattice made of equilateral triangles is better than the square lattice. No doubt this is well-known to someone. P.S.: According to p. 42 of "Lectures on Discrete Geometry" by Jiri Matousek, the best known upper bound on the number of distinct distances is C n/sqrt(log(n)) (as shown above) and the best known lower bound is C n^0.863. See: http://books.google.com/books?id=0N5RVe5lKQUC&printsec=frontcover Apparently Erdos offered $500 for a proof or disproof that the upper bound is best possible. See "Uniformity of distance in the plane (I)" in: http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd Dean Hickerson dean@math.ucdavis.edu