我在坐标系中有一个矩形区域R和一组点P位于R内部。所有边都平行于坐标轴,所有点都是整数。我想以这样的方式将R划分为更小的矩形:
(a) 矩形的边要么贴着R的边,要么至少包含一个来自 P 的点;
(b) 在每个矩形内,恰好有一个点来自 P。
我必须找到覆盖 P 中所有点的最小矩形数量。这里有一个示例:http://i5.minus.com/jC5LnVhjk6soT.png 紫色线表示错误的分割,因为上方的矩形不包含来自 P 的点。蓝色线则非常正确,因为两个矩形内都有一个来自 P 的点,因此正确输出应该是 2,因为这是最小的矩形数量。有没有人有找到最小数量的算法或方法的思路?
(a) 矩形的边要么贴着R的边,要么至少包含一个来自 P 的点;
(b) 在每个矩形内,恰好有一个点来自 P。
我必须找到覆盖 P 中所有点的最小矩形数量。这里有一个示例:http://i5.minus.com/jC5LnVhjk6soT.png 紫色线表示错误的分割,因为上方的矩形不包含来自 P 的点。蓝色线则非常正确,因为两个矩形内都有一个来自 P 的点,因此正确输出应该是 2,因为这是最小的矩形数量。有没有人有找到最小数量的算法或方法的思路?
2x2
的矩形是否有效?) - artur grzesiak