線段集合的最佳交集？

Question

我有一些二維線段應該都在一點相交，但不是因爲在計算中不能減小的噪音。

是否有算法來計算所有線段交點的最佳近似值。像所有線段的平均距離最小的點不一定位於任何線段上？

Answer 1

如果我們有選擇度量的自由度，平方和距離可以給出一個簡單的算法。

我們可以代表距離的平方的線I路爲座標點的功能，我們將得到(A[i]x,x)+(b[i],x)+c[i]，A[i]是一個3×3矩陣，b[i] - 載體，c[i] - 數（A，B） - 標量乘法。

他們的總和將是(A[sum]x,x)+(b[sum],x)+c[sum]。

這種功能的最低限度是x=-inverse(A[sum])b[sum]/2。

Answer 2

Amit的第一條評論就是你的答案。我會解釋爲什麼。

讓p_i成爲您的交點並且c = 1/n sum(p_i)。讓我們表明c的平均距離，d(a)的p_i和任意點a之間最小化：

d(a) = 1/n sum(|a-p_i|^2) 

什麼是d(a)被平均化，採用內積符號，

|a-p_i|^2 = <a-p_i, a-p_i> = |a|^2 + |p_i|^2 - 2<a,p_i>` 

的<a,p_i>平均只是使用點乘積的雙線性屬性<a,c>。所以，

d(a) = |a|^2 - 2<a,c> + 1/n sum(|p_i|^2) 

所以同樣

d(c) = |c|^2 - 2<c,c> + 1/n sum(|p_i|^2) = -|c|^2 + 1/n sum(|p_i|^2) 

減去兩個

d(a) - d(c) = |a|^2 - 2<a,c> + |c|^2 = |a-c|^2 

因此，增加d(c)雙方，到任意點a的平均距離是

d(a) = d(c) + |a-c|^2 

當 |a-c|^2爲零時，換句話說，當 a = c時，因爲所有項都是正的，所以其最小化爲

。