y******s
发帖数: 92 | 1 每个点都有对应的(x, y)坐标，中心点的定义为到其他N-1个点的距离之和最小。只能
想到brute force方法，要o(n^2)。有什么好方法吗？
多谢~
补充：距离欧拉距离，不是曼哈顿距离 |
h**6
发帖数: 4160 | |
b******d
发帖数: 794 | 3 1.求中心点
2.求到中心点最近的点
【在 y******s 的大作中提到】
: 每个点都有对应的(x, y)坐标，中心点的定义为到其他N-1个点的距离之和最小。只能
: 想到brute force方法，要o(n^2)。有什么好方法吗？
: 多谢~
: 补充：距离欧拉距离，不是曼哈顿距离
|
y******s
发帖数: 92 | 4 中心点如何高效找到？复杂度为多少呢？
【在 b******d 的大作中提到】
: 1.求中心点
: 2.求到中心点最近的点
|
b******d
发帖数: 794 | 5 center of mass, O(n)
【在 y******s 的大作中提到】
: 中心点如何高效找到？复杂度为多少呢？
|
l*********o
发帖数: 736 | 6 所有点x,y坐标的平均值
这个可以数学证明 中心坐标(x,y) 距离是平方和，convex function，
对x,y分别求偏导 导数为零时等于平均值
【在 y******s 的大作中提到】
: 中心点如何高效找到？复杂度为多少呢？
|
y*******4
发帖数: 53 | 7 这个点似乎要求是这些点的其中一个。
【在 l*********o 的大作中提到】
: 所有点x,y坐标的平均值
: 这个可以数学证明 中心坐标(x,y) 距离是平方和，convex function，
: 对x,y分别求偏导 导数为零时等于平均值
|
c*******t
发帖数: 123 | 8 r=\sum_i m_i (x_i-x_0)^2
minimize r, => x_0=\frac{\sum_i m_i x_i }{\sum_i m_i }. |
