[问题] 包含 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