The Art Gallery Guardian

Rectangles in point set


Problem1

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)\in l\cap 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 \sqrt{n} points and L are the lines contain at least \sqrt{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 \sqrt{n} counters. The running time is therefore \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 \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 C_4 in a bipartite graph. The vertices are X=\set{x|(x,y)\in P} and Y=\set{y|(x,y)\in 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 \geq c n^{1/2}, then there exists a C_4. If d\geq c n^{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

[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 2015-02-02.
Tags: classical, algorithm, computational geometry, graph theory.