PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 計算幾何 Closest Pair Decision Problem

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間11年前 (2013/12/07 14:06), 編輯推噓5(5推 0噓 5→)
留言10則, 5人參與, 最新討論串2/2 (看更多)
※ 引述《FRAXIS (喔喔)》之銘言： : 給定在平面上n個點的集合P及一正實數x，設計一線性演算法判斷x是否大於 : P中最靠近兩點之距離。 : 我的解法無法滿足algebraic decision tree model，不知道有沒有辦法 : 設計出一個滿足algebraic decision tree model的演算法。 : （只能用+-*/等代數運算和比較） 感覺很難達成線性時間... 我猜你的解法，應該是把平面切割成寬度為x的正方形網格 （上左邊界是閉區間、下右邊界是開區間） 一、不相鄰的網格，距離一定超過x，沒有檢查的必要！ 二、檢查網格內部，若超過三個點，就一定有「距離小於x的點對」，演算法結束 　　　　　　　　　若不超過三個點，需要檢查的點對，頂多3對，是常數 三、檢查相鄰八個網格：每個網格現在頂多三個點，需要檢查的點對，頂多3*3*8對，常數 然而如何把每一個點歸類於正確的網格呢？ 這件事情本質上跟排序很相像 然而排序是 omega(nlogn) 所以我覺得很難達成線性時間 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.250.62.191 ※ 編輯: DJWS 來自: 111.250.62.191 (12/07 14:15)
推
12/07 15:00, , 1F
這就跟先找closest pair 在看是不是大於x一樣lol
12/07 15:00, 1F
推
12/07 17:42, , 2F
這就是我用的方法，所以需要用floor運算 + Hash
12/07 17:42, 2F
推
12/08 16:17, , 3F
這件事比sort簡單很多才對XD... 你只需要知道相鄰而已
12/08 16:17, 3F
→
12/08 16:20, , 4F
現在的問題是不用floor沒辦法決定是哪一格
12/08 16:20, 4F
→
12/08 16:21, , 5F
相鄰的話用hash查就夠了
12/08 16:21, 5F
→
12/08 20:43, , 6F
不用floor的話，一種方式是把網格格點上的數字，摻進去排序
12/08 20:43, 6F
→
12/08 20:43, , 7F
所以我才會覺得這跟排序差不多
12/08 20:43, 7F
推
12/09 20:11, , 8F
若不用hash, 題目改成一維, 有O(n)演算法嗎?
12/09 20:11, 8F
推
12/09 20:43, , 9F
在algebraic decision tree model下
12/09 20:43, 9F
→
12/09 20:43, , 10F
就算是一維的也是有n lg n的下限
12/09 20:43, 10F
‣ 更多 DJWS 的文章
文章代碼(AID): #1IehhfK8 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1IehhfK8 (Prob_Solve)