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

Peter Munn techsubs at pearceneptune.co.uk
Mon Oct 4 12:55:18 CEST 2021


On Fri, October 1, 2021 11:27 pm, Alex Meiburg wrote:
> I ran the computation for what happens if you take a circular region of
> points in a grid. It's fairly straightforward in the asymptotic case,
> because it all just comes down to computing (and integrating) areas, and
> we
> don't have to actually worry about the integrality of points; and a result
> it becomes rotationally invariant.

I think this is a good approach. I have done something similar, but
looking at the valid points for the opposite vertex of a square, one of
whose vertices is on the circumference. To keep posts more manageable, I
will give more detail of my method in another post, but I get a value
exactly 4/3 larger, and it would help to get our results to agree.

> It comes out to 3(1/16 - 1/8pi)n^2
> ~=  0.0681338 n^2  ~=  n^2 / 14.677, assuming I didn't make a mistake.
> But,
> this sounds pretty reasonable, given that for squares it's n^2/12. This
> means that it performs worse, asymptotically, than a square of points.

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 struggle to see a reason why results for disc-approximating
configurations would migrate to the opposite side of the results for
square regions, especially to the extent corresponding to the ~14.677
value.

> In case anyone wants to check the work, I got that for a square with
> sidelength r0 in a circle of radius r, there is a region of area
>   A  -(1/2) r0 (-r0/2 + sqrt(r^2 - r0^2/4)) + r^2 (pi/2 - 2 arcsin(r0/2r))
> where the center of the square can be.

Setting r0 = 0, I reckon this gives r^2 * pi/2, when I would expect the
full area of the disc, r^2 * pi. There might be a non-ASCII character I'm
not seeing.

> Then the full number of
> possibilities is integral( A * (pi/2)r0,  for r0 from 0 to r).

Should this be for r0 from 0 to sqrt(2)*r?

Best regards,

Peter
>
> It seems natural to think about symmetric convex shapes (squircles and
> friends?) in the plane, and then optimize over the shape to find the one
> that produces the largest number of squares inside. In theory, probably
> possible to derive a diff eq for the ideal shape of the curve. In my
> opinion, that would have a very high chance of being asymptotically
> optimal
> for the sequence. (Although probably quite hard to prove!)
>
> -- Alexander Meiburg





More information about the SeqFan mailing list