algorithm - 从平面上的一组点中找到最近的点

Question

给定二维平面上的 n 个点，使到所有点的距离最小的点是什么？该点不必来自给定的点集。是质心还是其他什么？

如何用算法找到所有这样的点(如果有多个点)？

Answer 1

这被称为“距离中心”，不同于质心。

首先，您必须定义您使用的距离度量。如果我们假设您使用的是 d=sqrt( (x1-x2)^2 + (y1-y2)^2) 的标准度量，那么它不是唯一的，问题是最小化这个总和。

证明这个答案不是唯一的最简单的例子是直线例子。两点之间的任何点与所有点的总距离相等。

在 1D 中，正确答案将是左右两边点数相同的任何答案。只要这是真的，那么向左和向右的任何移动都会使左右两侧增加和减少相同的量，因此距离保持不变。这也证明质心不一定是正确答案。

如果我们扩展到 2D，情况就不再是这样了——因为 sqrt 使问题加权。令我惊讶的是，似乎没有标准算法!本页here似乎使用了蛮力方法。我从来不知道!

如果我想使用一种算法，那么我会找到 X 和 Y 中的中点作为起点，然后使用 gradient descent algorithm - 这会很快得到答案。整个方程最终是一个二次方程，所以感觉应该有一个精确解。