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

[Kurz, Sascha]

> 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