[seqfan] Re: How many squares can you make from n points in the plane?
Jack Grahl
jack.grahl at gmail.com
Tue Oct 5 15:22:35 CEST 2021
My instinct is that it would be surprising if circles are best — and that
some n-gon with n large will dominate over circles for large numbers of
points.
Octagons are better than squares because they allow more squares with (1,1)
sides. However they don't do well for other small squares, such as sides
(1,2), (1,3), (2,3), etc. However, there's only a limited number of angles
of such small squares that we want to cover. A configuration of points
which has 'sides' at all these basic rational angles might do well as lots
of the border could be filled with squares. While an approximate circle
will have pieces of the boundary at lots of other angles which can't be
covered by either small squares or large ones.
Of course, for smallish n the circle is very close to the (say) 48-gon with
sides of 4 small rational fundamental angles. When they start to become
different I think the latter might do better than the former.
Yours,
Jack
On Tue, 5 Oct 2021, 14:05 Kurz, Sascha, <Sascha.Kurz at uni-bayreuth.de> wrote:
>
> > 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
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list