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

看板Prob_Solve作者 (喔喔)時間12年前 (2013/12/07 00:29), 編輯推噓1(1推 0噓 2→)
留言3則, 1人參與, 最新討論串1/2 (看更多)
給定在平面上n個點的集合P及一正實數x，設計一線性演算法判斷x是否大於 P中最靠近兩點之距離。 我的解法無法滿足algebraic decision tree model，不知道有沒有辦法 設計出一個滿足algebraic decision tree model的演算法。 （只能用+-*/等代數運算和比較） -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 129.170.195.150
推
12/08 15:58, , 1F
應該不行，Integer element distinctness Ω(nlogn)
12/08 15:58, 1F
→
12/08 16:00, , 2F
可以reduce到你的問題: 給n個整數a1,a2,...,an問是否皆相異
12/08 16:00, 2F
→
12/08 16:00, , 3F
=> 平面上取(a1,0),(a2,0),...,(an,0)和x=0.5
12/08 16:00, 3F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1IeVk0a_ (Prob_Solve)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1IeVk0a_ (Prob_Solve)