[問題] 包含 k 點的最小正方形 (平行座標軸)

作者: FRAXIS (喔喔)   2015-03-12 07:06:46
輸入: 給定 平面上 n 個點和一個正整數 k < n
輸出: 包含 k 個點的正方形(平行座標軸)之中面積最小的一個。
我的想法是針對每一個點,找出 k-1 nearest neighbors,
然後計算包含這 k 個點的最小正方形。接著取其中最小的正方形。
複雜度大概是 O(n lg^2n lg RANGE),有沒有比較簡單或是更快的方法?
這是今天在Stackoverflow上面看到的一個面試問題
http://stackoverflow.com/questions/28969256/k-enclosing-minimum-area-square

Links booklink

Contact Us: admin [ a t ] ucptt.com