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

[Peter Munn]

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.

As I mentioned in my previous post, I think this is a good approach. I now
give details of my similar method for disc-approximating configurations.

I consider each qualifying square to be represented by a pair of its
vertices: the vertex furthest from the centre of the disc and the opposite
vertex. I ignore squares that have 2 or more vertices furthest from the
centre, as such squares are 0% of the total asymptotically. I look to
establish the proportion of pairs of grid points within the disc that
represent a qualifying square.

Pairs must satisfy 2 criteria: span an even rectilinear distance, and
qualify "regionally": with one in an appropriate region of the disc
relative to the other.

For k >= 0, consider pairs whose larger distance from the disc centre is
in the interval (k^2, (k+1)^2]. I assume the proportion of regionally
qualifying pairs converges as k -> oo to the proportion of the area of a
disc that contains, for a given (vertex) point on the circumference, the
opposite vertex of a square that is contained within the disc.

For a disc radius 1 centre (0, 0) with circumferential vertex (-1, 0), the
other vertex (x, y) must satisfy abs(y) <= sqrt(2-x^2) - 1 (it lies
between 2 arcs of radius sqrt(2), centred (0, -1) and (0, 1)). As a
proportion of the disc, the relevant area is 1 - 2/pi.

So, asymptotically, (1 - 2/pi) of grid point pairs qualify regionally.
Half of these will have even rectilinear distance, giving (0.5 - 1/pi) =
A258146.
Multiplying by total pairs of grid points gives n(n-1)/2 * A258146 ~=
n^2/11.008.

For square regions it's n^2/12. This implies that disc-approximating
configurations perform better, asymptotically, than squares of points.

Best regards,

Peter