Algorithm to dins minimal number of rectangles

Question

I have a rectangular area R in the coordinate system and a set of points P lying inside R. All sides are parallel to the axes and all points are integers. I want to divide R into smaller rectangles in such a way that

(a) the sides of the rectangles either stick to the sides of R or include at least one point from P and

(b) within each rectangle there is exactly one point from P

I have to find the smallest amount of rectangles which would cover all points from P. An example is drawn here: http://i5.minus.com/jC5LnVhjk6soT.png The purple line would indicate an incorrect division because the upper rectangle does not include a point from P. The blue line, however, is quite alright, because both rectangles have a point from P within, so the correct output would be: 2, because this is the minimum amount of rectangles.

Does anyone have an idea of an algorithm/method to find the smallest number?

I one thing is for me unclear: how those rectangles can be created? (e.g. is 2x2 rectangle a valid one?) — artur grzesiak
If every rectangle has to include exactly one point then you need exactly |P| rectangles. What about points on edges and corners? Are they allowed? If yes, do they count for all adjacent rectangles, for none of them or something different? — Daniel Brückner
After rereading the question I guess points on edges and corners are allowed and sometimes even required but do not count as being within any rectangle, right? — Daniel Brückner
Daniel, that is right. There has to be exactly one point within each rectangle, but these on edges/corners do NOT count as such. The points on edges can be numerous. So e.g. you could have 12 points in P, but form just 2 rectangles, because 10 of them were in line and the other two counted as the points within. And you need these points on edges to create division lines as such. You can't just cross a line wherever you want :) — user3018717

Jérôme Boé Jérôme Boé · Accepted Answer · 2013-11-21T19:23:29

According to your specifications, I end up with this recursive algorithm : (pseudocode~ruby implementation)

def resolve R, P
    if P.empty?
        return nil
    elsif P.size == 1
        return 1
    end

    results = []

    P.each do |p|
        rect1, rect2 = split_vertical(R, P, p)
        s1 = split_resolve(rect1, rect2)

        rect1, rect2 = split_horizontal(R, P, p)
        s2 = split_resolve(rect1, rect2)

        results.push [s1, s2].min
    end

    return results.min
end


def split_resolve rect1, rect2
    sum1 = resolve(rect1.R, rect1.P)
    sum2 = resolve(rect2.R, rect2.P)

    if !sum1.nil? and !sum2.nil?
        return sum1 + sum2
    else
        return nil
    end
end

Functions split_vertical and split_horizontal split the area R with a vertical and an horizontal line passing through the point p.

You can also optimize this algorithm using dynamic programming. You can store the results of sub-rectangles without computing it an other time. This happend when severals points stands on the same line.

ps : Don't copy the raw source code, you may have some problems with the nil idiom. It's just a pseudocode example for the whole process.

Algorithm to dins minimal number of rectangles

1 Answers