给定二维平面上n个点，有哪个点距离所有点的距离最小？这个点不一定来自给定点集。它是重心吗？还是其他什么？
如何用算法找到所有这样的点（如果有多个）？
4个回答
7
这被称为“距离中心”，与质心不同。
首先，您必须定义使用的距离度量。如果我们假设您正在使用标准度量d = sqrt（（x1-x2）^ 2 +（y1-y2）^ 2），那么它并不唯一，问题是最小化这个总和。
最容易说明答案不唯一的例子是直线示例。两点之间的任何点都具有相等的总距离。
在1D中，正确的答案将是具有相同数量的左侧和右侧点的任何答案。只要这是真的，那么向左和向右的任何移动都会以相同的数量增加和减少左侧和右侧，并且保持距离不变。这也证明了重心不一定是正确的答案。
如果我们扩展到2D，则不再是这种情况-因为sqrt使问题加权。令我惊讶的是，似乎没有标准算法！这个页面here似乎使用蛮力方法。我从来不知道！
如果我想使用算法，那么我会找到X和Y中位数作为起始点，然后使用梯度下降算法 - 这将很快得到答案。整个方程最终成为二次方程，因此感觉应该有一个精确的解决方案。
首先，您必须定义使用的距离度量。如果我们假设您正在使用标准度量d = sqrt（（x1-x2）^ 2 +（y1-y2）^ 2），那么它并不唯一，问题是最小化这个总和。
最容易说明答案不唯一的例子是直线示例。两点之间的任何点都具有相等的总距离。
在1D中，正确的答案将是具有相同数量的左侧和右侧点的任何答案。只要这是真的，那么向左和向右的任何移动都会以相同的数量增加和减少左侧和右侧，并且保持距离不变。这也证明了重心不一定是正确的答案。
如果我们扩展到2D，则不再是这种情况-因为sqrt使问题加权。令我惊讶的是，似乎没有标准算法！这个页面here似乎使用蛮力方法。我从来不知道！
如果我想使用算法，那么我会找到X和Y中位数作为起始点，然后使用梯度下降算法 - 这将很快得到答案。整个方程最终成为二次方程，因此感觉应该有一个精确的解决方案。
- Nick Fortescue
4
你第一个链接中的暴力算法不是用于处理球面上的点吗？ - Matthijs Wessels
不，我说的是n个点的梯度下降法。编写您的评分函数，使其计算到所有n个点的总距离，然后让您的下降函数将此值最小化。如果这是一份作业，我不会添加代码，因为编写它应该很容易。 - Nick Fortescue
@Matthijs，很可能我没有仔细看。谢谢你指出来。这是一个有趣的问题，不是吗？ - Nick Fortescue
@Nick Fortescue：抱歉删除了您的评论。我在删除后看到了您对评论的回答。 - nowonder
3
可能存在多个点。考虑一个只有两个点的平面。这些点描述了一条线段。该线段上的任何点到两个端点的总距离相同。
- William Billingsley
1
事实上，答案将是一个简单的多边形。原因是凸函数之和（如距离函数）也是凸的。您可以通过从三角形开始添加点来找到其精确坐标。但是，朴素地执行会是
n^2。 - Thomas Ahle1
这个问题在这里有详细讨论 http://www.ddj.com/architect/184405252?pgno=1
- Geek
1
这很有趣，但解决的是不同的问题。提问者询问了最小化到所有点距离的点。DDJ文章找到了彼此最近的两个点。 - Nick Fortescue
0
暴力算法可能会给您最好的结果。首先，找到包围输入点的矩形/任何四边形。最后，对于矩形内的每个点，计算与其他点的距离。将该点与输入集的距离总和。称这是该点的“成本”。为每个点重复此操作，并选择具有最小成本的点。
智能也可以添加到算法中。它可以根据平均成本等消除区域...
至少这就是我处理问题的方式...希望它有所帮助。
- Jibran
2
但它的复杂度非常高。如何检查矩形内的每个点，点坐标可以是任何浮点数。 - nowonder
显然，你需要一些步长，两个连续点之间的最小距离。以下是一个使用C语言的简单示例：for (int row = minR; row < maxR; row += rStep)
for (int col = minC; col < maxC; col += cStep)
[检查距离并将成本添加到数组中] - Jibran
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接