Re: [問題] 用最少數量個正方形 框住所有的點
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間8年前 (2016/03/31 13:23)推噓1(1推 0噓 2→)留言3則, 2人參與討論串2/2 (看更多)
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1459401834.A.66C.html
※ 編輯: DJWS (111.250.57.6), 03/31/2016 13:26:41
推
04/01 08:46, , 1F
04/01 08:46, 1F
→
04/01 10:32, , 2F
04/01 10:32, 2F
→
04/01 10:40, , 3F
04/01 10:40, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
