5
$\begingroup$

[This is much in the spirit (but different from) the questions from different posters: How many squares can be formed by using n points? and How many squares can be formed by using n points: revisited?]

Let $A$ be a set of $n$ points in the plane in general position. By general position we mean that no $3$ points are co-linear. What is the maximum number of squares that can be formed with vertices in $A$?

I note that there are trivial upper and lower bounds for this problem:

[Trivial Upper Bound] Given $n$ arbitrary points in the plane, noting that any two points determine at most $3$ squares it follows that there are at most $O(n^2)$ squares with vertices in $A$.

[Trivial Lower Bound] Place four points at the corner of a square, and repeat taking care to avoid all lines generated by pairs of points already placed in the plane until we've placed $n$ points. This clearly gives a lower bound of $\Omega(n)$.

I can improve the implied constant in both the upper and lower bound by being a bit more clever. The problem, however, is to

Improve (asymptotically) on either the upper or lower bound just given.

$\endgroup$
  • 1
    $\begingroup$ Since there can't be three co-linear points, in fact two points determine at most 1 square (either an edge or a diagonal). Since a square has 6 pairs of vertices, this gives a trivial upper bound $n(n-1)/12$. $\endgroup$ – Pietro Majer Jul 27 at 19:28
6
$\begingroup$

We can get a lower bound on the order of $n \log n$.

I'll describe how to arrange $4^n$ points in general position to get $n 4^{n-1}$ squares.

The arrangement is described recursively. For the base case $n=1$, we have $4^1 = 4$ points, and you can probably guess how we should arrange them to get $1 \cdot 4^{1-1} = 1$ squares. Now suppose we have an arrangement $A$ of $4^{n-1}$ points, in general position, giving us a total of $(n-1)4^{n-2}$ squares. Take $4$ copies of $A$ (a total of $4^n$ points). Place the $4$ copies of $A$ at the $4$ corners of a "large" square, and then rotate each copy of $A$ by a "random" angle $\theta$ (the same angle for each of our $4$ copies of $A$). This gives us our new arrangement of points.

If the square mentioned above is large enough, then no points from $3$ distinct copies of $A$ can lie on a line. And it is not hard to show that, with probability $1$, a randomly chosen $\theta$ will have the property that no two points from a given copy of $A$ will lie on a common line with a different copy of $A$. So for a "large" square and a "random" angle, we get a set of $4^n$ points in general position.

In each small copy of $A$, we get $(n-1)4^{n-2}$ small squares, for a total of $4(n-1)4^{n-2} = (n-1)4^{n-1}$ small squares in our new arrangement. In addition to these, we get $|A| = 4^{n-1}$ additional large squares, by connecting the $4$ corresponding points in each of our $4$ copies of $A$. This gives a total of $n4^{n-1}$ squares, as promised.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Because of rotational symmetry (around the center of the large square), you get at least twice that many large squares. Gerhard "Buy Four Get One Free" Paseman, 2020.07.27. $\endgroup$ – Gerhard Paseman Jul 27 at 23:02
  • $\begingroup$ @Will: Very nice. This does formally satisfy my question of improving asymptotically on the trivial estimates in some direction. However I'm going to leave the question open in hopes that someone can further close the gulf between the upper and lower bounds. $\endgroup$ – Mark Lewko Jul 28 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.