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

[Kurz, Sascha]

> Sascha: what are you run-times ? How far can you compute these
> configurations ? Can you compute one around n = 140 ? This could
> probably tell circles and octagons appart (my bet is now on circles).

Prescribing a (12,3)-octagon

120 points generate 1286 squares; contained in a 12x12-grid.
___XXXXXX___
__XXXXXXXX__
_XXXXXXXXXX_
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
_XXXXXXXXXX_
__XXXXXXXX__
___XXXXXX___

it took 4.32 seconds to compute the optimal extension by 20 points on the
surrounding 14x14-grid. (I stopped the extension to an 16x16 grid after
30 minutes, where the LP bounds where between 1752 and 1789.)

140 points generate 1752 squares.
contained in a 13x13-grid.

___XXXXXXX___
__XXXXXXXXX__
_XXXXXXXXXXX_
_XXXXXXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXX
_XXXXXXXXXXX_
_XXXXXXXXXXX_
__XXXXXXXXX__
____XXXXX____



Prescribing a circle with radius  6.0828

121 points generate 1298 squares; contained in a 13x13-grid.

_____XXX_____
___XXXXXXX___
__XXXXXXXXX__
_XXXXXXXXXXX_
_XXXXXXXXXXX_
XXXXXXXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXX
_XXXXXXXXXXX_
_XXXXXXXXXXX_
__XXXXXXXXX__
___XXXXXXX___
_____XXX_____

it took 155.42 seconds to compute the optimal extension by 19 points on the
surrounding 15x15-grid. The very same solution was computed


My bet is now on circles too. However, for small numbers of points (k,l)-octagons perfom pretty well:
k      l     n          m        n(n-1)/m    comment
2      0    4          1        12.000    optimal
3      0    9          6        12.000    optimal
4      1    12        11      12.000    optimal
4      0    16        20      12.000    best known
5      1    21        37      11.351    best known
6      1    32        88      11.273    best known
7      2    37        117    11.385    best known
7      1    45        175    11.314    best known
8      2    52        237    11.190    best known
9      2    69        421    11.145    best known
10    3    76        507    11.243    best known
10    2    88        686    11.160
11    3    97        836    11.139
12    3    120     1286    11.104
13    3    145     1880    11.106
14    4    156     2175    11.117
14    3    172     2643    11.128
15    4    185     3070    11.088
16    5    196     3425    11.159
15    3    201     3602    11.160
16    4    216     4190    11.084

Circles seem to perform better if the number of points gets larger
radius     n    m    n(n-1)/m    comment
1.4143    9    6    12.000    optimal
2.0001    13    11    14.182    2 off opimal
2.2361    21    37    11.351    best known
2.8285    25    50    12.000    1 off best known
3.0000    29    67    12.119
3.1623    37    117    11.385    best known
3.6056    45    175    11.314    best known
4.0000    49    204    11.529
4.1232    57    278    11.482
4.2427    61    323    11.331
4.4722    69    421    11.145    best known
5.0000    81    568    11.408
5.0991    89    698    11.221
5.3852    97    836    11.139    octagon
5.6569    101    905    11.160
5.8310    109    1051    11.201    octagon
6.0001    113    1128    11.220
6.0828    121    1298    11.186
6.3246    129    1476    11.187    octagon
6.4032    137    1678    11.104
6.7083    145    1880    11.106    octagon
7.0001    149    1977    11.154
7.0711    161    2304    11.181
7.2112    169    2546    11.152
7.2802    177    2812    11.078
7.6158    185    3070    11.088    octagon
7.8103    193    3336    11.108
8.0001    197    3469    11.131
8.0623    213    4065    11.108
8.2463    221    4387    11.083
8.4853    225    4544    11.092
8.5441    233    4874    11.091
8.6024    241    5228    11.064
8.9443    249    5566    11.095    octagon
9.0001    253    5743    11.102
9.0554    261    6113    11.101
9.2196    277    6901    11.078    better than octagon
9.4340    285    7311    11.071
9.4869    293    7745    11.047
9.8489    301    8155    11.073    octagon
9.8995    305    8368    11.080
10.0001    317    9031    11.092
10.0499    325    9505    11.078
10.1981    333    9987    11.070
10.2957    341    10485    11.058
10.4404    349    10991    11.050
10.6302    357    11497    11.054    better than octagon

However, we will really need quite some points to see the asymptotical fraction 11.008 (and to see differences between
circles and octagons).

I have no glue whether choosing a different grid in a small circle inside another circle, as in Theorem 4 in the paper on
isoclees right triangles, may get us below 11.008.

Is it worth to collect "best known" lower bounds for all numbers of points? Up to which n?

Best regards,
Sascha