The Art Gallery Guardian

Rectangles in point set


Problem1

Given nn points in the plane PP, find if any 44 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 ll, and then for each (x,y)lP(x,y)\in l\cap P, we consider all the points with the same yy coordinate and to the right of xx, 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 yy coordinate if one already builds a data structure before hand. If any counter become 22, then we are done.

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

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

There is an O(n3/2)O(n^{3/2}) algorithm [1], using this O(n2)O(n^2) algorithm as subroutine.

We consider the set of vertical lines that contains at least 22 points. This give us two set of vertical lines, SS are the lines with at most n\sqrt{n} points and LL are the lines contain at least n+1\sqrt{n}+1 lines.

There are 3 possibilities. There is a rectangle with two sides contained in SS, or one side in SS one in LL, or both in LL.

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

For the second case, consider we pick one line in SS and the union of all the points in the lines in LL. For each point in SS, we will find if this point is in some line in LL, if it is, we increment a counter for that line. We would increment at most n\sqrt{n} counters. The running time is therefore lSlP(logn+n)=O(n3/2)\sum_{l\in S} |l\cap P|(\log n + \sqrt{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\sqrt{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 C4C_4 in a bipartite graph. The vertices are X={x(x,y)P}X=\set{x|(x,y)\in P} and Y={y(x,y)P}Y=\set{y|(x,y)\in P}, and the edges are PP. So this is a nice interaction with graph theory. In the same article, some stronger bounds were established. First, if the graph have degeneracy dd, the running is O(md)O(md). They used the fact and lead to finding a C4C_4 takes O(m4/3)O(m^{4/3}) time [2].

We briefly mention how this is done.

First, it is known that if mcn1/2m \geq c n^{1/2}, then there exists a C4C_4. If dcn3/2d\geq c n^{3/2}, then one can find a subgraph that has degree at least dd in O(m)O(m) time. Note this implies in the subgraph, there exists a C4C_4, which there is a particular algorithm to solve for it.

References

[1] M.J. van Kreveld, M.T. De Berg, Finding squares and rectangles in sets of points, BIT Numerical Mathematics. 31 (1991) 202–219 10.1007/BF01931281.

[2] N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles, Algorithmica. 17 (1997) 209–223 10.1007/BF02523189.

Posted by Chao Xu on .
Tags: classical, algorithm, computational geometry, graph theory.