c - 实现几何中位数

Question

当我用谷歌搜索几何中位数时，我得到了这个链接 Geometric median 但我不知道如何在 C 中实现它。我不太擅长理解这个数学解释。假设我有 11 对坐标，我将如何计算它们的几何中值。

我正在尝试解决这个问题Grid CIty .我得到一个提示，几何中位数将帮助我实现它。我不是在寻找最终解决方案。如果有人可以引导我走上正确的道路，那将会有所帮助。

感谢是提前

下面是坐标列表a(测试用例)。结果:3 4

1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5

Answer 1

如果没有迭代算法，我认为这是无法解决的。

这是一个类似于爬山版本的伪代码解决方案，不同之处在于它适用于任意精度，并且适用于更高的维度。

CurrentPoint = Mean(Points)
While (CurrentPoint - PreviousPoint) Length > 0.01 Do
    For Each Point in Points Do
        Vector = CurrentPoint - Point
        Vector Length = Vector Length - 1.0
        Point2 = Point + Vector
        Add Point2 To Points2
    Loop
    PreviousPoint = CurrentPoint
    CurrentPoint = Mean(Points2)
Loop

注意事项:

常数 0.01 不保证结果在真值的 0.01 以内。使用较小的值以获得更高的精度。

常量 1.0 应该调整为(我猜)最远点之间距离的大约 1/5。值太小会减慢算法速度，但值太大会导致不准确，可能导致无限循环。