Square with minimum area enclosing K points among given N points

Question

This question was asked to me in an online test. There are N points given in a Cartesian plane. An integer K will be given. The aim is to find the area of the square (minimum) enclosing at least K points. The sides of square should be parallel to the axis.The vertices of the square should be integers. Any points lying on the sides are not considered to be inside the square.

I could only solve it for K=N (i.e. all points will lie in the square).

My solution is -

    static int minarea(int[] x, int[] y, int k) {
    //Find max y
    int maxVal = Integer.MIN_VALUE;
    for(int i : y){
        if(i > maxVal){
            maxVal = i;
        }
    }
    //Find min y
    int minVal = Integer.MAX_VALUE;
    for(int i : x){
        if(i < minVal){
            minVal = i;
        }
    }

    int yLength = (maxVal-minVal)+2;

    //Find max x
    maxVal = Integer.MIN_VALUE;
    for(int i : x){
        if(i > maxVal){
            maxVal = i;
        }
    }
    //Find min x
    minVal = Integer.MAX_VALUE;
    for(int i : x){
        if(i < minVal){
            minVal = i;
        }
    }

    int xLength = (maxVal-minVal)+2;
    int sqSide = (yLength > xLength)?yLength:xLength;
    return sqSide*sqSide;

}

One approach for general solution would be to find all possible combination of K points among N points and applying the above method for all combinations but that is not good. Please advise.

Answer 1

It can be seen that we always can move the square so that it would have points on the left and bottom edges. We'll iterate through all combinations of left and bottom edges of the square. Then we will need to find upper or right edge of the square. For every point we can determine at what edge it would lie. For example if point.x - left > point.y - bottom then point would lie on the right edge of the square and resulting area would be ( point.x - left )^2. We'll need to sort the points by the area of squares: area = ( max( point.x - left, point.y - bottom ) )^2 and select K-th point from this sorted list. It will be the smallest square enclosing at least K points with specified left bottom corner. Complexity of this solution is O(n^3) which is not very nice, but it faster than iterating over all combinations of K points. My solution in java: https://ideone.com/139C7A

Answer 2

static void initBounds(int[] x, int[] y)
    {
        minX = x[0];
        maxX = x[0];
        minY = y[0];
        maxY = y[0];
        for(int i = 1; i < x.length; i++){
            if(x[i] > maxX)
                maxX = x[i];
            if(x[i] < minX)
                minX = x[i];
            if(y[i] > maxY)
                maxY = y[i];
            if(y[i] < minY)
                minY = y[i];
        }
    }

    static int countEnclosingPoints(int[] x, int[] y, int sx1, int sy1, int sx2, int sy2)
    {
        int count = 0;
        for(int i = 0; i < x.length; i++)
        {
            if(x[i] > sx1 && x[i] < sx2 && y[i] > sy1 && y[i] < sy2)
                count++;
        }
        return count;
    }

    static int minX;
    static int minY;
    static int maxX;
    static int maxY;

    static long minarea(int[] x, int[] y, int k) {
        long area = 0;
        initBounds(x, y);
        int xDiff = maxX - minX;
        int yDiff = maxY - minY;

        int sx1 = minX - 1;
        int sy1 = minY - 1;

        int sideDiff = Math.abs(xDiff - yDiff) + 1;

        int sx2; 
        int sy2;

        if(xDiff > yDiff){
            sx2 = maxX + 1;
            sy2 = maxY + sideDiff;
        } else {
            sx2 = maxX + sideDiff;
            sy2 = maxY + 1;
        }
        area = (sx2 - sx1) * (sx2 - sx1);

        int p, q, r, s;
        int minSize = (int) Math.sqrt(k) + 1;
        for(p = sx1; p < sx2 - minSize; p++) {
            for(q = sy1; q < sy2 - minSize; q++) {
                int xd = sx2 - p; int yd = sy2 - q;
                int sd = (xd < yd)? xd : yd;
                for(int i = sd; i >= minSize; i--){
                    int count = countEnclosingPoints(x, y, p, q, p + i, q + i);
                    if(count >= k) {
                        long currArea = i * i;
                        if(currArea < area)
                            area = currArea;
                    }
                    else
                        break;
                }
            }
        }
        return area;
    }

Generates all possible squares with area (sqrt(k)) * (sqrt(k)) to the maximum bounding square of all points. The square's bottom left point can be anywhere within the bounding square. Constraints like minimum size square required to accommodate at least k points(sqrt(k)) are considered. If a square encloses at least k points and area is lesser than current min area, then update area.

Answer 3

Looks like there's a paper by Michiel Smid about this problem:

http://pubman.mpdl.mpg.de/pubman/item/escidoc:1834660:2/component/escidoc:1857755/MPI-I-93-116.pdf

An algorithm is presented that, given a set of n points in the plane and an integer k, 2 ≤ k ≤ n, finds k points with a smallest enclosing axes-parallel square. The algorithm has a running time of O(n log n+kn log2 k) and uses O(n) space. The previously best known algorithm for this problem takes O(k 2n log n) time and uses O(kn) space