看板 [ Prob_Solve ]
討論串[問題] 用最少數量個正方形 框住所有的點
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 用最少數量個正方形 框住所有的點
推噓5(5推 0噓 1→)留言6則，0人參與, 最新作者dominicx (on my own)時間8年前 (2016/03/23 17:43), 編輯資訊
1
0
0
內容預覽:
2D空間中. 有N個已知座標(X,Y)的點. 正方形的邊長度固定為M. 求計算出最少需要幾個正方形把所有點框選進去?. --. ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.21.59. ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.
#2
Re: [問題] 用最少數量個正方形 框住所有的點
推噓1(1推 0噓 2→)留言3則，0人參與, 最新作者DJWS (...)時間8年前 (2016/03/31 13:23), 8年前編輯資訊
0
0
0
內容預覽:
先聲明我沒做文獻調查. 這個問題可以用 set cover problem 來解決（我不清楚是否有複雜度更低的方法）. 問題轉換方式如下. 1. [duality]. 正方形的範圍相對收縮，點的範圍相對擴張，原問題變成：. 2D空間中，有N個已知中心點的正方形，求最少需要幾個點(圖釘)可以釘到所有正
(還有231個字)
首頁
上一頁
1
下一頁
尾頁