算法以确定最小矩形数量

Question

算法以确定最小矩形数量

3

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

(a) 矩形的边要么贴着R的边，要么至少包含一个来自 P 的点；

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

我必须找到覆盖 P 中所有点的最小矩形数量。这里有一个示例：http://i5.minus.com/jC5LnVhjk6soT.png 紫色线表示错误的分割，因为上方的矩形不包含来自 P 的点。蓝色线则非常正确，因为两个矩形内都有一个来自 P 的点，因此正确输出应该是 2，因为这是最小的矩形数量。有没有人有找到最小数量的算法或方法的思路？

- user3018717

1

我会查看动态规划的解决方案。 - Jérôme Boé

有一件事对我来说不清楚：这些矩形是如何创建的？（例如，2x2 的矩形是否有效？） - artur grzesiak

如果每个矩形都必须恰好包含一个点，则需要恰好|P|个矩形。那么边缘和角落的点呢？它们被允许吗？如果是，它们是否计入所有相邻矩形，还是没有计入或者其他不同的情况？ - Daniel Brückner

1

在重新阅读问题后，我猜想边缘和角落上的点是允许的，有时甚至是必需的，但不计入任何矩形内，对吗？ - Daniel Brückner

丹尼尔，你说得对。每个矩形内必须恰好有一个点，但是边缘/角落上的点不算在内。边缘上的点可以很多。例如，您可以在P中有12个点，但只形成2个矩形，因为其中10个点在一条线上，另外两个点被计算为内部点。而且您需要这些边缘上的点来创建分割线。您不能随意穿过线 :) - user3018717

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jérôme Boé · 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_horizontal通过点p分别用垂直线和水平线分割区域R。

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

附注：请勿复制原始源代码，否则可能会遇到nil习语的问题。这只是整个过程的伪代码示例。