K-enclosing Minimum Area Square

Question

Asked during an interview. We are given N points on a 2-D plane x[0],y[0].......x[n-1],y[n-1] and an integer K.

We need to find the minimum area Square,having integer coordinates as vertices with sides parallel to coordinate axis. enclosing atleast K of the given N points, with no point lying on the boundary of the square, i.e all K points should be strictly inside the square.

I thought of classical minimum enclosing-rectangle problem, but couldn't derive the case for at least K points. How to approach this? Thanks in advance.

Answer 1

Since the side length of the smallest square is upper-bounded by the difference between the min/max x/y-coordinate, we can use binary search on the side length. So we only need to consider the decision problem: for a given length L, testing whether there exists a square with side length L containing at least K points.

This decision problem is equal to put n squares with side length L centered at each point and determine whether the maximum number of overlapping (depth of an arrangement of boxes). By using plane-sweep technique, the decision problem can be solved in O(n lg n) time and hence the optimization problem can be solved in O(n lg n lg U), where U is the upper bound of the side length.