[seqfan] Re: How many squares can you make from n points in the plane?

[hv at crypt.org]

=?UTF-8?Q?Beno=C3=AEt_Jubin?= <benoit.jubin at gmail.com> wrote:
:Values for n > 9 are conjectural since they were obtained by
:exhaustive search for grid points within a square of side
:ceil(sqrt(n)), which is a reasonable assumption.  A proof that optimal
:configurations (with least side length equal to 1) have a diameter at
:most f(n) with f of reasonable growth would permit exact computation
:of values from exhaustive searches.
[...]
:Lower bounds
:Computer searches, using glutton algorithms starting with all grid
:points in a convex polygon and adding successive points, have given
:the following current record configurations, which thus yield lower
:bounds for a(n).  They are due mainly for n <= 36 to Sean A. Irvine
:and for 37 <= n <= 50 to Sascha Kurz, with preliminary work by Hugo
:van der Sanden.

A slight correction: I don't think I've done any preliminary work on
convex polygon-based approaches; what I've done is confirmed that the
figures Sean derived using the "exhaustive search for grid points
within a square of side ceil(sqrt(n))" are identical to those derived
by "exhaustive search of all 1- and 2-points extensions starting from
a unit square".

Are we ready to conjecture that all maximal arrangements can be
generated by such extensions? If we are, it's worth noting that this
also trivially implies a(n) = b(n).

Hugo