# [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

```