找到最小矩形数的算法

Question

我在坐标系中有一个矩形区域 R 和一组位于 R 内的点 P。所有边都平行于轴，所有点都是整数。我想以这样的方式将 R 分成更小的矩形

(a) 矩形的边要么粘在 R 的边上，要么包括 P 和中的至少一个点

(b) 在每个矩形内，恰好有一个点来自 P

我必须找到最小数量的矩形来覆盖 P 中的所有点。这里画了一个例子:http://i5.minus.com/jC5LnVhjk6soT.png紫色线表示不正确的划分，因为上面的矩形不包含来自 P 的点。但是，蓝色线很好，因为两个矩形都有来自 P 的点，所以正确的输出将是:2，因为这是矩形的最小数量。

有没有人知道找到最小数字的算法/方法？

Answer 1

根据您的规范，我最终得到了这个递归算法:(伪代码~ruby 实现)

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

函数 split_vertical 和 split_horizo​​ntal 用穿过点 p 的垂直线和水平线分割区域 R >.

您还可以使用动态规划优化此算法。您可以存储子矩形的结果而无需再次计算。当多个点位于同一条线上时会发生这种情况。

ps : 不要复制原始源代码，你可能对 nil 习惯用法有一些问题。这只是整个过程的伪代码示例。