I***A 发帖数: 6 | 1 (1)给定2D平面上N个点, 求他们之间的最短距离好像有个 O(N)的算法;
但如果是3D的空间,上面的算法是不是仍然适用呢? 有没有人考虑过这个问题?
(2)给定2D平面上N个点,求一条直线使得它经过的点最多; 好像是到老题? 不
知道最优解是什么,能不能指点一下
(3)给定2D平面上N个点 ,求最近的三个点? 这题还能用Divide and Conquer
吗? |
k****n 发帖数: 369 | 2 2d应该是nlogn吧,line sweeping,至少你得排个序
Conquer
【在 I***A 的大作中提到】 : (1)给定2D平面上N个点, 求他们之间的最短距离好像有个 O(N)的算法; : 但如果是3D的空间,上面的算法是不是仍然适用呢? 有没有人考虑过这个问题? : (2)给定2D平面上N个点,求一条直线使得它经过的点最多; 好像是到老题? 不 : 知道最优解是什么,能不能指点一下 : (3)给定2D平面上N个点 ,求最近的三个点? 这题还能用Divide and Conquer : 吗?
|
d*******l 发帖数: 338 | 3 你说的line sweeping指的是哪个?我只知道算法导论上那个nlogn的最近点对算法
【在 k****n 的大作中提到】 : 2d应该是nlogn吧,line sweeping,至少你得排个序 : : Conquer
|
I***A 发帖数: 6 | 4 写错了; 应该是O(Nlog(N));
另外的两个呢, 有没有想法?
【在 k****n 的大作中提到】 : 2d应该是nlogn吧,line sweeping,至少你得排个序 : : Conquer
|
j********x 发帖数: 2330 | 5 最近的三个点怎么定义的?
Conquer
【在 I***A 的大作中提到】 : (1)给定2D平面上N个点, 求他们之间的最短距离好像有个 O(N)的算法; : 但如果是3D的空间,上面的算法是不是仍然适用呢? 有没有人考虑过这个问题? : (2)给定2D平面上N个点,求一条直线使得它经过的点最多; 好像是到老题? 不 : 知道最优解是什么,能不能指点一下 : (3)给定2D平面上N个点 ,求最近的三个点? 这题还能用Divide and Conquer : 吗?
|