作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 用最少数量个正方形 框住所有的点
时间Thu Mar 31 13:23:51 2016
※ 引述《dominicx (on my own)》之铭言：
: 2D空间中
: 有N个已知座标(X,Y)的点
: 正方形的边长度固定为M
: 求计算出最少需要几个正方形把所有点框选进去?
先声明我没做文献调查
这个问题可以用 set cover problem 来解决（我不清楚是否有复杂度更低的方法）
问题转换方式如下
1. [duality]
正方形的范围相对收缩，点的范围相对扩张，原问题变成：
2D空间中，有N个已知中心点的正方形，求最少需要几个点(图钉)可以钉到所有正方形?
2. [discretization]
正方形有两条垂直线，N个正方形有2N条垂直线，最多切出2N+1个区域
正方形有两条水平线，N个正方形有2N条水平线，最多切出2N+1个区域
水平垂直都考虑，最多切出(2N+1)^2块区域
然後，每块区域顶多只需要一个图钉
3. [set cover problem]
依序穷举每一块区域
看看一块区域钉上图钉，可以钉到那些正方形，原问题变成：
选择其中几个区域钉图钉，可以钉到所有正方形
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.57.6
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1459401834.A.66C.html
※ 编辑: DJWS (111.250.57.6), 03/31/2016 13:26:41
1F：推 FRAXIS: 这问题也可以变成 clique cover 04/01 08:46
2F：→ DJWS: (2N+1)^2个区域当做点。若属於同一个正方形，就连一条边。 04/01 10:32
3F：→ DJWS: 接下来还可以继续推文说 这问题也可以变成3-SAT 04/01 10:40