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(lk)\), where \(l\) is the maximum number of points on a horizontal line and \(k\) is maximum number of points on a vertical line.

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 out \(O(lk)\) 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.

References

[1] M. van Kreveld, M. de Berg, Finding squares and rectangles in sets of points, in: M. Nagl (Ed.), Graph-Theoretic Concepts in Computer Science, Springer Berlin Heidelberg, 1990: pp. 341–355 10.1007/3-540-52292-1_25.

Posted by Chao Xu on 2015-02-02.
Tags: classical, algorithm, computational geometry.