k*******r
发帖数: 355 | 1 从别处看来的，
给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈 |
w********s
发帖数: 1570 | 2 积分图像
扫一遍可以获得积分图像
S(i,j)=从(0,0)到(i,j)的点的个数
之后，对于任意的矩形(i,j),(k,l)，都可以一步求得其中包含的点的个数
S2 = S(k,l) - S(k,j) - S(i,l) + S(i,j)
O(n^2)肯定可以搞定。
点.
【在 k*******r 的大作中提到】
: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈
|
k*******r
发帖数: 355 | 3 你这个解法在O(n^2)不一定找得到最优解，因为所要找到的矩形顶点，未必就在给定点
中。
比如给定三个点(0,0), (0,4), (4,0), k=3, 那么解答应该是(0,0), (4,4). 但(4,4)
这个点不在给定点中。
这样一来，如果用你的解法，就要try out all rectangles, 你要考虑可能的顶点数就
是O(N^2)个了，那你的矩形candidate数就是O(n^4) |
k*******r
发帖数: 355 | 4 另外题目中约束条件是至少含K个点，而不是刚好含K个点， 所以题目的约束条件是一
个比较松弛的条件，按说可以用这减少时间复杂度的 |
k*******r
发帖数: 355 | 5 另外题目中约束条件是至少含K个点，而不是刚好含K个点， 所以题目的约束条件是一
个比较松弛的条件，按说可以用这减少时间复杂度的 |
f*****e
发帖数: 2992 | 6 for(int i = 0; i < rows; ++i){
for(int j = 0; j <= i; ++j){
对从j到i的rows使用蠕虫算法。
}
}
复杂度O(N^3)
【在 k*******r 的大作中提到】
: 另外题目中约束条件是至少含K个点，而不是刚好含K个点， 所以题目的约束条件是一
: 个比较松弛的条件，按说可以用这减少时间复杂度的
|
s*****g
发帖数: 39 | 7 想到一个nlogn的算法：
先按照x value对n个点排序，然后对它们按照y value建segment tree。这样的话，对
第i到i+k-1个点，只需要O(1)找出x_max和x_min，需要O(logn)找出y_max和y_min。
这个方法假设了正方形的下边沿和x轴平行。如果没有这个constraint的话，可能更复
杂了
【在 k*******r 的大作中提到】
: 另外题目中约束条件是至少含K个点，而不是刚好含K个点， 所以题目的约束条件是一
: 个比较松弛的条件，按说可以用这减少时间复杂度的
|
c******0
发帖数: 260 | 8 记得数据结构课上讲过一种结构，专门解决这个问题的…
点.
【在 k*******r 的大作中提到】
: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈
|
k*******r
发帖数: 355 | 9 shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
点，算出覆盖这k个点的矩形最小面积。
但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
的解啊。 换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊 |
f*****e
发帖数: 2992 | 10 嗯，最小长方形有可能是扁的，not bounded by ymin and ymax。
【在 k*******r 的大作中提到】
: shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
: 点，算出覆盖这k个点的矩形最小面积。
: 但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
: 的解啊。 换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊
|
|
|
w********s
发帖数: 1570 | 11 大于n^2, 小于n^3。
对从(k,j)开始的点，遍历(k+n), (j+m)，如果遇到>k的时候，可以break，对于k+n,
寻找最小的m，也可以用二分查找法。
【在 k*******r 的大作中提到】
: 你这个解法在O(n^2)不一定找得到最优解，因为所要找到的矩形顶点，未必就在给定点
: 中。
: 比如给定三个点(0,0), (0,4), (4,0), k=3, 那么解答应该是(0,0), (4,4). 但(4,4)
: 这个点不在给定点中。
: 这样一来，如果用你的解法，就要try out all rectangles, 你要考虑可能的顶点数就
: 是O(N^2)个了，那你的矩形candidate数就是O(n^4)
|
l**z
发帖数: 78 | 12 正确性好像有问题
【在 s*****g 的大作中提到】
: 想到一个nlogn的算法：
: 先按照x value对n个点排序，然后对它们按照y value建segment tree。这样的话，对
: 第i到i+k-1个点，只需要O(1)找出x_max和x_min，需要O(logn)找出y_max和y_min。
: 这个方法假设了正方形的下边沿和x轴平行。如果没有这个constraint的话，可能更复
: 杂了
|
l**z
发帖数: 78 | 13 网格边长都是2N吧，这样最终复杂度还是O(n^2)
【在 k*******r 的大作中提到】
: 你这个解法在O(n^2)不一定找得到最优解，因为所要找到的矩形顶点，未必就在给定点
: 中。
: 比如给定三个点(0,0), (0,4), (4,0), k=3, 那么解答应该是(0,0), (4,4). 但(4,4)
: 这个点不在给定点中。
: 这样一来，如果用你的解法，就要try out all rectangles, 你要考虑可能的顶点数就
: 是O(N^2)个了，那你的矩形candidate数就是O(n^4)
|
s*****g
发帖数: 39 | 14 确实考虑不周了...
【在 k*******r 的大作中提到】
: shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
: 点，算出覆盖这k个点的矩形最小面积。
: 但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
: 的解啊。 换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊
|
g******y
发帖数: 143 | 15 Can the rectangle be rotated?
点.
【在 k*******r 的大作中提到】
: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈
|
l*********8
发帖数: 4642 | 16 two-d tree吧
点.
【在 k*******r 的大作中提到】
: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈
|
s******t
发帖数: 229 | 17 二维线段树，建树O(x*y),query O(logn)
如果是rotate rectangle 或者坐标是double什么的，我就不知道了 |
i*******t
发帖数: 499 | 18 How about this?
Create a data structure like range tree to efficiently search for the needed
points.
For each point, create a rectangle of area zero.
Then for each rectangle containing one point, enlarge the rectangle to
contain one more point that increase the area the least. So now there are at
most n-1 rectangles each containing two points.
Then for each rectangle with two points, enlarge it again by adding another
point that still minimizing the area of that rectangle.
Repeat this until each rectangle contains k points.
There are at most n-k+1 such rectangles. Return the one with the smallest
area.
Looks like the complexity is O(knlogn) |
i*******t
发帖数: 499 | |
h******6
发帖数: 2697 | |
|
|
n********e
发帖数: 41 | 21 包含两个点的为啥是n-1个？
难道不是 C(n,2) 个么？
needed
at
another
【在 i*******t 的大作中提到】
: How about this?
: Create a data structure like range tree to efficiently search for the needed
: points.
: For each point, create a rectangle of area zero.
: Then for each rectangle containing one point, enlarge the rectangle to
: contain one more point that increase the area the least. So now there are at
: most n-1 rectangles each containing two points.
: Then for each rectangle with two points, enlarge it again by adding another
: point that still minimizing the area of that rectangle.
: Repeat this until each rectangle contains k points.
|
i*******t
发帖数: 499 | 22 是让面积最小的点。
每个点都可以找到另一个点让面积最小。
【在 n********e 的大作中提到】
: 包含两个点的为啥是n-1个？
: 难道不是 C(n,2) 个么？
:
: needed
: at
: another
|
i*******t
发帖数: 499 | 23 我发现这个greedy algorithm也不能保证最优解。
比如说要从下面这6个点找4点
.
..
..
.
needed
at
another
【在 i*******t 的大作中提到】
: How about this?
: Create a data structure like range tree to efficiently search for the needed
: points.
: For each point, create a rectangle of area zero.
: Then for each rectangle containing one point, enlarge the rectangle to
: contain one more point that increase the area the least. So now there are at
: most n-1 rectangles each containing two points.
: Then for each rectangle with two points, enlarge it again by adding another
: point that still minimizing the area of that rectangle.
: Repeat this until each rectangle contains k points.
|
i*******t
发帖数: 499 | 24 好像是。不过质量可能不是很好。
刚找到这篇可能好点
www.cccg.ca/proceedings/1996/cccg1996_0004.pdf
【在 h******6 的大作中提到】
: 是这个么
: http://cisjournal.org/journalofcomputing/archive/vol3no6/vol3no
|
D*********1
发帖数: 34 | 25 不好意思，刚点成回复给作者了。您能给个O(N^2)的算法吗？
点.
【在 k*******r 的大作中提到】
: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标， 要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈
|
