看板 [ Prob_Solve ]
討論串[問題] 計算幾何 Closest Pair Decision Problem
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 計算幾何 Closest Pair Decision Problem
推噓1(1推 0噓 2→)留言3則，0人參與, 最新作者FRAXIS (喔喔)時間11年前 (2013/12/07 00:29), 編輯資訊
1
0
0
內容預覽:
給定在平面上n個點的集合P及一正實數x，設計一線性演算法判斷x是否大於. P中最靠近兩點之距離。. 我的解法無法滿足algebraic decision tree model，不知道有沒有辦法. 設計出一個滿足algebraic decision tree model的演算法。. （只能用+-*/等
#2
Re: [問題] 計算幾何 Closest Pair Decision Problem
推噓5(5推 0噓 5→)留言10則，0人參與, 最新作者DJWS (...)時間11年前 (2013/12/07 14:06), 編輯資訊
0
0
0
內容預覽:
感覺很難達成線性時間.... 我猜你的解法，應該是把平面切割成寬度為x的正方形網格. （上左邊界是閉區間、下右邊界是開區間）. 一、不相鄰的網格，距離一定超過x，沒有檢查的必要！. 二、檢查網格內部，若超過三個點，就一定有「距離小於x的點對」，演算法結束. 若不超過三個點，需要檢查的點對，頂多3對，
(還有81個字)
首頁
上一頁
1
下一頁
尾頁