我讲个思路哈，不一定合适。
先用 N 个面积为 0 的矩形把所有点覆盖。
然后争取合并，直到合并成 M 个矩形。
每次合并都尽量争取增加的覆盖面积最小。


【 在 garland 的大作中提到: 】
: 研究中遇到一个算法问题，描述如下：
: 二维空间中分布M个点，求N个矩形（其中N是人为设定的数），使得：（1）这N个矩形覆盖所有M个点；（2）这N个矩形面积之和最小。
: 不知这样的问题是否有非暴力算法给出最优解？如果没有，能否有算法给出近似解？
--
FROM 220.181.102.*

只有heuristic的算法吧，和R* tree很相像。

https://en.wikipedia.org/wiki/R-tree

R* tree topological split.[13]
The pages overlap much less since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications.

【 在 garland 的大作中提到: 】
: 研究中遇到一个算法问题，描述如下：
: 二维空间中分布M个点，求N个矩形（其中N是人为设定的数），使得：（1）这N个矩形覆盖所有M个点；（2）这N个矩形面积之和最小。
: 不知这样的问题是否有非暴力算法给出最优解？如果没有，能否有算法给出近似解？
--
FROM 50.125.86.*