Rectangles in point set
Given points in the plane , find if any 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 , and then for each , we consider all the points with the same coordinate and to the right of , 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 coordinate if one already builds a data structure before hand. If any counter become , then we are done.
It is a time algorithm, since the time it takes is at most to guess each left vertical segment. One could, however analyze this algorithm better, and realize the time is actually , where is the maximum number of points on a horizontal line. Indeed, we look at a horizontal line that contain points, and realize for each point on the horizontal line, we need to increment a counter at most times.
We can also solve the problem in time, where is the number of vertical lines. Note since we can stop as soon as a counter become . The number of counter we will increase is at most . Indeed, the counter depend only one two vertical lines.
There is an algorithm , using this algorithm as subroutine.
We consider the set of vertical lines that contains at least points. This give us two set of vertical lines, are the lines with at most points and are the lines contain at least lines.
There are 3 possibilities. There is a rectangle with two sides contained in , or one side in one in , or both in .
For the first case, just use our algorithm, which gives us time.
For the second case, consider we pick one line in and the union of all the points in the lines in . For each point in , we will find if this point is in some line in , if it is, we increment a counter for that line. We would increment at most counters. The running time is therefore .
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 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 , rectangle finding problem can be reduced to finding a in a bipartite graph. The vertices are and , and the edges are . So this is a nice interaction with graph theory. In the same article, some stronger bounds were established. First, if the graph have degeneracy , the running is . They used the fact and lead to finding a takes time .
We briefly mention how this is done.
First, it is known that if , then there exists a . If , then one can find a subgraph that has degree at least in time. Note this implies in the subgraph, there exists a , which there is a particular algorithm to solve for it.