有 N 個二維點，如何求能夠將這些點全部覆蓋的面積最小的橢圓的長軸與短軸？

03-19

有 N 個二維點，求能夠將這些點全部覆蓋的面積最小的橢圓的長軸與短軸。

設N個點 $oldsymbol{x}_i$ , i=1,2,...,N，那麼一個橢圓能覆蓋住意味著

$(oldsymbol{x}_i-oldsymbol{x}_0)^Toldsymbol{Sigma}^{-1}(oldsymbol{x}_i-oldsymbol{x}_0)le1$

其中 $oldsymbol{Sigma}$ 是一個對稱正定矩陣，在這裡是 2*2 的矩陣，實際上這就是在 $oldsymbol{Sigma}$ 下的 Mahalanobis 距離，可以簡單寫作 $|oldsymbol{x}_i-oldsymbol{x}_0|^2_{oldsymbol{Sigma}}le1$

這個橢圓的體積是 $det(oldsymbol{Sigma})$

所以這個問題可以寫成如下的優化問題：

$min_{oldsymbol{Sigma},,oldsymbol{x}_0}quaddet(oldsymbol{Sigma})$

$ext{s.t.}quad |oldsymbol{x}_i-oldsymbol{x}_0|^2_{oldsymbol{Sigma}}le1$

這是個凸優化問題，最簡單粗暴可以用梯度下降來求解，很快能得到結果。當然既然是凸優化問題，就存在高效的求解方式，比如牛頓法等等。

第一步，找出這堆點的凸包。第二步，用章佳傑的答案求覆蓋這個凸包所有頂點的橢圓。最核心就是求這個凸規劃問題。

support vector?

橢圓不能乘旋轉矩陣的話不難，能的話。。。。這個計算有點蛋碎關鍵數學推導很複雜，我確實見過但我的水平和智商無力。。。

弱智演算法拋個磚。

先取n個點的凸包，得到k個點。

五個點確定一個橢圓，就是k個點中取5個點構成一個橢圓，其餘點檢測是否在橢圓內部。

找到滿足條件的最小面積的橢圓。