[seqfan] Re: How many squares can you make from n points in the plane?
Kurz, Sascha
Sascha.Kurz at uni-bayreuth.de
Tue Oct 5 09:13:01 CEST 2021
> Small disc-approximating configurations give counts from about n(n-1)/11
> to n(n-1)/12, compared with exactly n(n-1)/12 for square regions. On a
> hand count of differences from a 12X12 square, I reckon the following 164
> point region has 2469 ~= 164*163/10.83 squares. An automated recount
> appreciated!
>
>____XXXXXX____
>__XXXXXXXXXX__
>_XXXXXXXXXXXX_
>_XXXXXXXXXXXX_
>XXXXXXXXXXXXXX
>XXXXXXXXXXXXXX
>XXXXXXXXXXXXXX
>XXXXXXXXXXXXXX
>XXXXXXXXXXXXXX
>XXXXXXXXXXXXXX
>_XXXXXXXXXXXX_
>_XXXXXXXXXXXX_
>__XXXXXXXXXX__
>____XXXXXX____
I have some doubt about the precise numbers.
Let an (k,l)-octagon be arise from a kxk-grid removing triangles of length l at the 4
corners.
Example (14,4)-octagon
XXXXXX
XXXXXXXX
XXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXX
XXXXXXXX
XXXXXX
156 points spanning 2175 squares being a subset of the above.
Using integer linear programming the optimal extension on a 14x14 (or 16x16) grid
can be computed in just a few seconds. In both cases we get 164 points with just 2409
squares.
Best regards,
Sascha
More information about the SeqFan
mailing list