作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 計算幾何 Closest Pair Decision Problem
時間Sat Dec 7 14:06:31 2013
※ 引述《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)
1F：推 singlovesong:這就跟先找closest pair 在看是不是大於x一樣lol 12/07 15:00
2F：推 FRAXIS:這就是我用的方法，所以需要用floor運算 + Hash 12/07 17:42
3F：推 seanwu:這件事比sort簡單很多才對XD... 你只需要知道相鄰而已 12/08 16:17
4F：→ seanwu:現在的問題是不用floor沒辦法決定是哪一格 12/08 16:20
5F：→ seanwu:相鄰的話用hash查就夠了 12/08 16:21
6F：→ DJWS:不用floor的話，一種方式是把網格格點上的數字，摻進去排序 12/08 20:43
7F：→ DJWS:所以我才會覺得這跟排序差不多 12/08 20:43
8F：推 neutrino:若不用hash, 題目改成一維, 有O(n)演算法嗎? 12/09 20:11
9F：推 FRAXIS:在algebraic decision tree model下 12/09 20:43
10F：→ FRAXIS:就算是一維的也是有n lg n的下限 12/09 20:43