Re: Ten points in a square

On 12 Apr 2008 02:29:17 +0300, Phil Carmody
<thefatphil_demunged@xxxxxxxxxxx> wrote:

quasi <quasi@xxxxxxxx> writes:
On 11 Apr 2008 21:54:31 GMT, David W. Cantrell
<DWCantrell@xxxxxxxxxxx> wrote:

"Zdislav V. Kovarik" <kovarik@xxxxxxxxxxx> wrote:
It is a standard exercise on Pigeonhole Principle to prove:

If you place 10 distinct points in a square of side 1, then at least
two points will have distance no more than sqrt(2)/3 (about 0.4714).

My question: This number is an upper bound for the minimum
positive distance. Has anyone found the least upper bound?

(It is at least 1/3, just place the points at lattice points
with stepsize 1/3. With slightly more effort, one can replace
1/3 by sqrt(2)/(2*sqrt(2)+1), about 0.3694.)

By the way, tens of millions of pseudorandom experiments have
not exceeded 0.32.

It is 0.421..., which follows from the packing of ten unit circles, proven
optimal, shown at <http://www.stetson.edu/~efriedma/cirinsqu/>.

It's not clear to me that the 10 circle packing configuration answers
the OP's question.

There's no requirement for the placed points to be any given distance
away from the boundary of the square.

Assuming that there's one circle abutting each edge of the
square, then you can be sure that all the centres fit within
a square with width 2 less, 4.747+. Then scale that down to
be 1, and count the distance between points as that of 2
radii. If you could improve on this ratio, then by adding
the 1-unit border back round the outside you'd be able to
improve on the packing found at DC's link.

I don't see it.

If you start with a maximal 10-circle packing configuration with all
equal circles of radius r, that induces a 10-point configuration with
min distance d = 2r.

The converse doesn't seem to automatic, and may not be true.

In other words, if you start with a 10-point configuration with min
distance d, that doesn't necessarily induce a 10-circle packing
configuration with all circles of radius r, where r = d/2. The issue
is the "outer" points, which need not be d away from the boundary of
the square.

quasi
.