# Rectangles in point set

Given $n$ points in the plane $P$, find if any $4$ of them are the vertices of some axis-aligned rectangle.

The idea is we guess the left vertical segment of the rectangle, and see what would be the right vertical segment. If we pick an left vertical line $l$, and then for each $(x,y)∈l∩P$, we consider all the points with the same $y$ coordinate and to the right of $x$, and add a counter to the vertical lines that contains it. This can be done in linear time with respect to number of vertices with the same $y$ coordinate if one already builds a data structure before hand. If any counter become $2$, then we are done.

It is a $O(n_{2})$ time algorithm, since the time it takes is at most $O(n)$ to guess each left vertical segment. One could, however analyze this algorithm better, and realize the time is actually $O(ln)$, where $l$ is the maximum number of points on a horizontal line. Indeed, we look at a horizontal line that contain $l$ points, and realize for each point on the horizontal line, we need to increment a counter at most $l$ times.

We can also solve the problem in $O(t_{2}+n)$ time, where $t$ is the number of vertical lines. Note since we can stop as soon as a counter become $2$. The number of counter we will increase is at most $t_{2}$. Indeed, the counter depend only one two vertical lines.

There is an $O(n_{3/2})$ algorithm [1], using this $O(n_{2})$ algorithm as subroutine.

We consider the set of vertical lines that contains at least $2$ points. This give us two set of vertical lines, $S$ are the lines with at most $n $ points and $L$ are the lines contain at least $n +1$ lines.

There are 3 possibilities. There is a rectangle with two sides contained in $S$, or one side in $S$ one in $L$, or both in $L$.

For the first case, just use our $O(ln)$ algorithm, which gives us $O(n_{3/2})$ time.

For the second case, consider we pick one line in $S$ and the union of all the points in the lines in $L$. For each point in $S$, we will find if this point is in some line in $L$, if it is, we increment a counter for that line. We would increment at most $n $ counters. The running time is therefore $∑_{l∈S}∣l∩P∣(gn+n )=O(n_{3/2})$.

Once we are done with the first two case, consider remove all the points lying on the small lines. Now we only have large lines. Since there are at most $n $ large lines, we can rotate the plane and run the algorithm again, but this time, we know all the lines are small.

As noted in [2], rectangle finding problem can be reduced to finding a $C_{4}$ in a bipartite graph. The vertices are $X={x∣(x,y)∈P}$ and $Y={y∣(x,y)∈P}$, and the edges are $P$. So this is a nice interaction with graph theory. In the same article, some stronger bounds were established. First, if the graph have degeneracy $d$, the running is $O(md)$. They used the fact and lead to finding a $C_{4}$ takes $O(m_{4/3})$ time [2].

We briefly mention how this is done.

First, it is known that if $m≥cn_{1/2}$, then there exists a $C_{4}$. If $d≥cn_{3/2}$, then one can find a subgraph that has degree at least $d$ in $O(m)$ time. Note this implies in the subgraph, there exists a $C_{4}$, which there is a particular algorithm to solve for it.

# References

**Finding squares and rectangles in sets of points**, BIT Numerical Mathematics. 31 (1991) 202–219 10.1007/BF01931281.

**Finding and counting given length cycles**, Algorithmica. 17 (1997) 209–223 10.1007/BF02523189.