2D平面上の与えられた点をカバーする最小円

問題：2D平面上の与えられたN点をカバーする円の可能な最小直径はいくらですか？2D平面上の与えられた点をカバーする最小円

この問題を解決する最も効率的なアルゴリズムとはどのようなものですか？

2011-02-04 Leonid

これまでにお聞きしたことがあります。もし私がそれを見つけることができれば。 –

これは__Smallest circle problem__である必要があります。http://en.wikipedia.org/wiki/Smallest_circle_problem – Jack

ここでは "duplicate"ですが、私のようには素晴らしい答えではありません。http：// stackoverflow。 com/questions/3102547/how-can-i-find-the-minimal-circle-some-some-given-points – Benjamin

これはsmallest circle problemです。推奨されるアルゴリズムへのリンクについては、参考文献を参照してください。

E.Welzl、最小の囲むディスク（ボールと楕円体）、H.でマウラー（編）、新しい結果や新潮流コンピュータサイエンスで、コンピュータサイエンスの講義ノート、巻。 555、 Springer-Verlag、359-37（1991）

は「最速」アルゴリズムへの参照です。

出典

2011-02-04 18:29:36 Benjamin

ありがとう！私は、この答えが元の質問に含まれて重複を取り除くことができると思います。 – Leonid

の球を囲む最小のアルゴリズムと実装がいくつかあります。問題です。

2Dと3Dの場合は、おそらくGärtner's implementationが最も高速です。
Girtner、Kutz、Fischerによるアルゴリズムの実装であるhttps://github.com/hbf/miniball（高解像度の場合は、注：私は共著者の1人です）をご覧ください。
非常に非常に高い次元の場合、コアセット（近似）アルゴリズムはより高速になります。

注：あなたが球の最小囲む球を計算するためのアルゴリズムを探しているなら、あなたはComputational Geometry Algorithms Library (CGAL)でC++の実装があります。

出典

2013-02-20 13:29:57 Hbf

遠い点のボロノイ図のアプローチ

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html

は、2次元問題のために本当によく働くことが判明し、（単に必要なヘッダとソースファイルを抽出あなたはCGALのすべてを使用する必要はありません。）。それは反復ではなく、厳密に保証されています。私はそれが高次元にあまり伸びていないと思うので、文献にはそれほど注意が払われていません。

私がここでそれを説明することに興味があるならば、上記のリンクは少し難しいと思います。

別のリンクを編集：http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704

出典

2013-03-05 14:14:18 agentp

2D平面上の与えられた点をカバーする最小円

答えて

関連する問題