※ 引述《FRAXIS (喔喔)》之銘言:
: 給定在平面上n個點的集合P及一正實數x,設計一線性演算法判斷x是否大於
: P中最靠近兩點之距離。
: 我的解法無法滿足algebraic decision tree model,不知道有沒有辦法
: 設計出一個滿足algebraic decision tree model的演算法。
: (只能用+-*/等代數運算和比較)
感覺很難達成線性時間...
我猜你的解法,應該是把平面切割成寬度為x的正方形網格
(上左邊界是閉區間、下右邊界是開區間)
一、不相鄰的網格,距離一定超過x,沒有檢查的必要!
二、檢查網格內部,若超過三個點,就一定有「距離小於x的點對」,演算法結束
若不超過三個點,需要檢查的點對,頂多3對,是常數
三、檢查相鄰八個網格:每個網格現在頂多三個點,需要檢查的點對,頂多3*3*8對,常數
然而如何把每一個點歸類於正確的網格呢?
這件事情本質上跟排序很相像
然而排序是 omega(nlogn)
所以我覺得很難達成線性時間