Dies ist das sogenannte Kleinste umhüllende Ball Problem (in Ihrem Fall kleinster umschließender Kreis ), a.k.a. Miniball . Es gibt mehrere Algorithmen und Implementierungen für dieses Problem - alle folgenden sind lineare Zeitlösungen (dh gegeben n Kugeln, sie laufen in O (n) if) Sie betrachten die Dimension d fest, d = 2 in Ihrem Fall):
Für 2D und 3D ist Gärtners Implementierung wahrscheinlich die Schnellste.
Bei höheren Dimensionen (z. B. bis zu 10.000) sehen Sie sich Ссылка an, die Implementierung von ein Algorithmus von Gärtner, Kutz und Fischer (Anmerkung: Ich bin einer der Mitautoren).
Für sehr, sehr hohe Dimensionen werden Kernsatz (Approximation) Algorithmen schneller sein.
Hinweis: Wenn Sie nach einem Algorithmus suchen, um die kleinste umschließende Kugel von Kugeln zu berechnen, finden Sie eine C ++ - Implementierung im Bibliothek für die Algorithmen der Computer-Geometrie (CGAL) . (Sie müssen nicht die gesamte CGAL verwenden; extrahieren Sie einfach die erforderlichen Header- und Quelldateien.)