给定一个包含 P 个点的 n*n 网格，使用必须恰好包含 K 个点的矩形覆盖 P 个点的总最小成本是多少，成本是矩形的周长。
1. 这个问题看起来类似于多边形三角剖分，但有一个额外的限制，即每个小矩形应该恰好包含 K 个点。
最佳答案
我怀疑准确地解决您的问题相当困难。 一种可能的方法是使用 quad-tree structure , 并停止 split 当下一次分割相对于 k 变得太小时。 虽然，正如 Thomas 在评论中所说，目前尚不清楚如何 在每个单元格中准确地达到 k 点。
关于algorithm - 最小成本多边形矩形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44125598/