最小圓覆蓋

最小圓覆蓋是數學中的一個算法問題，研究如何尋找能夠覆蓋平面上一群點的最小圓。這個問題在一般的n維空間中的推廣是最小包圍球的問題，即尋找能覆蓋n維空間中某個點集的最小球。最小圓覆蓋問題最早由十九世紀的英國數學家詹姆斯·約瑟夫·西爾維斯特在1857年提出。

最小圓覆蓋也是運籌學中設施選址問題的一種。廣義的設施選址問題研究的是當已知一些目標點（倉庫、銷售終端、供應商等等）的位置時，求滿足與這些目標點的距離相關的點的某些極值。最小圓覆蓋可以看作是研究「到一些點的距離之最大值最小的點」的問題。現有的算法可以在線性時間內計算最小圓覆蓋或最小包圍球的問題。

問題刻畫

尋找最小覆蓋圓的大部分幾何方法都是尋找給定點集中經過最小覆蓋圓的那些點。這是基於以下兩個事實：

1. 最小覆蓋圓是唯一存在的。
2. 給定的點集中，最多有三個點在最小覆蓋圓上。如果有三個點在最小覆蓋圓上，那麼最小覆蓋圓就是這三點的外接圓；如果只有兩個點在最小覆蓋圓上，那麼最小覆蓋圓就是以這兩點之間的直線段為直徑的圓。