Number of rectangles generated by $n$ points in the plane

Question

This sounds like a problem that would have been definitely studied by some paper, and to defend myself I have searched using various tools for some time to no avail.

What is the configuration of $n$ points in the plane that creates the maximum number of rectangles having them as vertexes, and what is the (asymptotic) maximum number?

To be clear, a rotated rectangle, such as $(-1, 0), (1, 0), (0, -1), (0, 1)$ is also treated as a rectangle. The points do not have be in the lattice. Any references to the literature, or related results will be appreciated!

Edit - I do not expect a closed form formula for all $n$, even a result on the lines of $O(n^2)$ will be very useful.

Answer 1

Step by step ...

With $n= p \times q$ points in $B_{p,q}=\{(a,b), a \in \mathbb{N}, b \in \mathbb{N}, 1\le a \le p, 1\le b\le q \}$, we can search how many rectangles we can build. We search for an asymptotic estimation. (asymptotic is important !)

Question 1 : how many rectangles with sides parallel to the grid : easy, $p \times (p-1) \times q \times (q-1) /4$

Question 2 : how many rectangles parallel to this specific direction (2,1) (means that 1 side is parallel to the vector AB, with A(0,0) and B(2,1) ?
Probably we need to decompose this question into more detailed questions. For a rectangle not parallel to the grid, I define the 1st corner as : the corner with minimum y.

So this question 2 can be detailed :

• how many rectangles with one side parallel to vector (2,1), and first corner in the 1st row of the grid ?
• how many rectangles with one side parallel to vector (2,1), and first corner in the row $y_0$ of the grid ?
• Estimate the sum of all values, for $y_0=1$ to $q-1$

Question 3 : generalisation, same question with any direction $(a,b)$ with $gcd(a,b)=1$ ; I filter with this restriction $gcd(a,b)=1$, to avoid duplicates.

Question 4 : When we have a general formula to estimate the number of rectangles with a specific direction, we need to sum all values, for all valid directions.

Each question is challenging, but step by step, it seems to be reachable.

Answer 2

I have been notified by one of my friends this paper: https://pure.tue.nl/ws/files/4288742/369233.pdf . It gives a lower bound of $\Omega(n^2)$ and an upper bound of $O(n^{2.5})$. However there may be better results and I will keep the question open.