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