u****h
发帖数: 2193 | 1 N个圆, 给出坐标和半径, 半径各自不同. 最小16, 最大128. 问其中有多少对相交?
另外, 地图长宽都是400 * sqrt(n)
一对圆相交iff半径和大于圆心距离. | u****h
发帖数: 2193 | | s*****g
发帖数: 5159 | 3 你要多少复杂度？N^2很容易，
counter =0;
For i =1 to n
for j = 1 to n and j!=i
if i intersect j
counter++;
end for
end for
return counter/2.
【在 u****h 的大作中提到】
: N个圆, 给出坐标和半径, 半径各自不同. 最小16, 最大128. 问其中有多少对相交?
: 另外, 地图长宽都是400 * sqrt(n)
: 一对圆相交iff半径和大于圆心距离.
| s*****g
发帖数: 5159 | 4 我觉得这个像vector classification的问题，如果想知道精确的数目（而不是大致数
目），我觉得还得N^2，容我再想想。
【在 u****h 的大作中提到】
: 当然, 我们expect
| s*****g
发帖数: 5159 | 5 可以用类似k-dimensional tree的方法。
1. Randomly select a point (a center of a circle).
2. Draw a line in throw the point, and divide the circles into to partitons,
one at a side and one at the other size, the those circles crossed by the
line, they belongs to neither (counter saparately).
3. The above two disjoint circle sets will not intersect either other at all
since they are separated by the line.
4. recursively do the same thing on the subset.
5. When return from the recursion, count those circles
【在 u****h 的大作中提到】
: 当然, 我们expect
| c****r
发帖数: 185 | 6 Build a spatial index and then do range queries.
1. Find the bounding box of all points
2. Split the bounding box into 4 sub-boxes.You can split either on the
middle point (kd-tree) or median point (R-tree). Do this recursively.
3. For each point, do a range query where the range is the radius.
The time complexity is O(n*logn). | s*****n
发帖数: 5488 | 7 such thing is called q-tree. so you can google.
【在 c****r 的大作中提到】
: Build a spatial index and then do range queries.
: 1. Find the bounding box of all points
: 2. Split the bounding box into 4 sub-boxes.You can split either on the
: middle point (kd-tree) or median point (R-tree). Do this recursively.
: 3. For each point, do a range query where the range is the radius.
: The time complexity is O(n*logn).
| s*****g
发帖数: 5159 | 8
When does the recursion stop?
What's the query in a binary answer question?
【在 c****r 的大作中提到】
: Build a spatial index and then do range queries.
: 1. Find the bounding box of all points
: 2. Split the bounding box into 4 sub-boxes.You can split either on the
: middle point (kd-tree) or median point (R-tree). Do this recursively.
: 3. For each point, do a range query where the range is the radius.
: The time complexity is O(n*logn).
| u****h
发帖数: 2193 | 9 不好意思没理解, 最后一步, do the range query where the range is the radius,
是怎么通过这一步来计算相交园个数的阿?
不知道跟这个有没有关系, 不过半径可能不同...
不过半径的range是给出来的, 最小16, 最大128
【在 c****r 的大作中提到】
: Build a spatial index and then do range queries.
: 1. Find the bounding box of all points
: 2. Split the bounding box into 4 sub-boxes.You can split either on the
: middle point (kd-tree) or median point (R-tree). Do this recursively.
: 3. For each point, do a range query where the range is the radius.
: The time complexity is O(n*logn).
| c****r
发帖数: 185 | 10 quad-tree?
【在 s*****n 的大作中提到】
: such thing is called q-tree. so you can google.
| | | c****r
发帖数: 185 | 11 Range query:
For each MBR (minimum bounding box), you can compute the minimum and maximum
distance from a given point P.
1. If max_distance <= P.radius, then all points inside MBR are answers
2. If min_distance > P.radius, then the MBR can be pruned
3. If min < P.radius <= max, then trace down to sub-MBRs.
Do this recursively then you can get all answers of a given point, O(logN).
Do it for every point, O(NlogN)
,
【在 u****h 的大作中提到】
: 不好意思没理解, 最后一步, do the range query where the range is the radius,
: 是怎么通过这一步来计算相交园个数的阿?
: 不知道跟这个有没有关系, 不过半径可能不同...
: 不过半径的range是给出来的, 最小16, 最大128
| u****h
发帖数: 2193 | 12 我觉得这个算法做的只是多少个点落在圆内, 并不是真正的相交园. 圆心可能在外面,
但是相交了 .
当然, 因为半径的最大范围是给出来的, 所以可以把当前园的半径virtually增大, 但
是即使如此, 还是要检查每个园是否真正相交. 这个复杂度似乎就不能保证nlogn了
不过, 这个算法还是in a very good shape....
或者我还有地方没理解, 您能仔细讲讲?
maximum
【在 c****r 的大作中提到】
: Range query:
: For each MBR (minimum bounding box), you can compute the minimum and maximum
: distance from a given point P.
: 1. If max_distance <= P.radius, then all points inside MBR are answers
: 2. If min_distance > P.radius, then the MBR can be pruned
: 3. If min < P.radius <= max, then trace down to sub-MBRs.
: Do this recursively then you can get all answers of a given point, O(logN).
: Do it for every point, O(NlogN)
:
: ,
| c****r
发帖数: 185 | 13 Oops, I forgot that you are finding intersecting circles.
Well, you can represent each point as a single MBR from the beginning.
When you build the spatial index, the leaf nodes are no longer points, but
their MBRs.
The max/min conditions still hold.
【在 u****h 的大作中提到】
: 我觉得这个算法做的只是多少个点落在圆内, 并不是真正的相交园. 圆心可能在外面,
: 但是相交了 .
: 当然, 因为半径的最大范围是给出来的, 所以可以把当前园的半径virtually增大, 但
: 是即使如此, 还是要检查每个园是否真正相交. 这个复杂度似乎就不能保证nlogn了
: 不过, 这个算法还是in a very good shape....
: 或者我还有地方没理解, 您能仔细讲讲?
:
: maximum
| u****h
发帖数: 2193 | 14 我还是没有理解, 外切正方形相交不一定保证园相交把...
【在 c****r 的大作中提到】
: Oops, I forgot that you are finding intersecting circles.
: Well, you can represent each point as a single MBR from the beginning.
: When you build the spatial index, the leaf nodes are no longer points, but
: their MBRs.
: The max/min conditions still hold.
| y***u
发帖数: 101 | 15
maximum
This is not O(log n).
【在 c****r 的大作中提到】
: Range query:
: For each MBR (minimum bounding box), you can compute the minimum and maximum
: distance from a given point P.
: 1. If max_distance <= P.radius, then all points inside MBR are answers
: 2. If min_distance > P.radius, then the MBR can be pruned
: 3. If min < P.radius <= max, then trace down to sub-MBRs.
: Do this recursively then you can get all answers of a given point, O(logN).
: Do it for every point, O(NlogN)
:
: ,
|
|
