Das finden der kleinste Kreis umfasst weitere Kreise?

Wenn ein Kreis ist definiert durch die X, Y von der Mitte und einem Radius, wie finde ich einen Kreis und umfasst eine bestimmte Anzahl von Kreisen? Ein Kreis, der die kleinste mögliche Kreis vollständig enthalten 2 oder mehr Kreise in jeder Größe und Lage.

Zuerst habe ich versucht nur umfasst 2 Kreise durch die Suche nach dem Mittelpunkt des centers und wird den Mittelpunkt des neuen Kreises, während der radius gleich der Hälfte des radius der ersten 2 Kreise und die Hälfte der Distanz zwischen Ihren mitten, aber irgendwie ist es immer wieder ein wenig aus. Das problem schien immer ein problem mit der Suche nach den radius, aber ich habe solche Kopfschmerzen, über diese ich kann nicht damit es funktioniert.

Brauche ich nicht unbedingt eine Methode für die Suche nach einem Kreis, der umfasst 3 oder mehr Kreise. Ich finde einen Kreis umfasst, 2, der Kreis und umfassen es mit einen anderen, und den anderen, und der Letzte Kreis sollte umfassen alle Kreise gegeben, überall in den Schritten.

  • Glaube nicht, dies ist eine Frage für StackOverflow. Fragen Sie Ihren Mathe-Lehrer. Ist es nicht Hausaufgaben zu machen?
  • Gehört auf mathoverflow.net
  • Kreise und Kugeln sind Häufig in Grafik und Spiele zu approximieren, werden die beweglichen Objekte' bounding box für die Kollisionserkennung und andere Zwecke.
  • Halle: mathoverflow ist für Mathe-Profis. Sie wollen nicht Fragen wie diese.
  • Wir ermöglichen "Hallo Welt!" auf SO Fragen
  • M: Auch wenn diese Metapher ist passend-wer sagt, dass der mathoverflow Jungs sollten standards identisch sind SO ist?
  • M : Aber dies ist nicht eine Hallo-Welt-Frage. Appearently er hat sich nichts getan. Der erste Schritt, den er Folgen sollte, ist eine mathematische Ableitung. Dann kann er sich bewegen SO.
  • guter Punkt, ich habe gerade überprüft Ihre FAQ und es besagt, dass der Standort für Forschung Ebene Fragen. Trotzdem, ich denke, dass diese Frage viel mehr über die Mathematik als die Programmierung an dieser Stelle. Einmal gibt es einen Algorithmus zu implementieren, ich würde sagen, es gehören könnte auf SO.
  • Du hast Recht, Sie könnte nicht. Aber der Gedanke war, dass SO einige sehr intelligente Menschen die Beantwortung ebenso einfache Programmierung Probleme.
  • Ich sehe nicht die Frage als solche ein ärgernis, und es ist wahrscheinlich, Programmierung verwandt. Die Annäherung zur Verfügung gestellt (ignorieren Sie alle anderen Kreise, zwei von Ihnen...) ist der sound aus mathematischer Sicht (zumindest für die zwei-Kreis-problem), so dass die Ergebnisse ein wenig off' könnte darauf hindeuten, eine Programmierung Problem (was-Typen verwenden Sie? sind Sie erwägen den Rundungsfehler?)
  • Ich würde sagen, dass der "computational geometry" Probleme wie diese sind für die Programmierung verwandt. Suche eine bounding-circle für 2 oder 3 Kreise ist einfache algebra, aber das finden einer für N Kreise effizienter als O(beängstigend) ist nicht. Und später ist definitiv eine Frage der Programmierung.
  • Mathematisch ist das eher ein Grenzwert und nicht der genaue Wert. (wie viele zahlen zwischen 0,1 und 0.100001 ? Antwort: auf unbestimmte Zeit!) In der Welt der Programmierung, wir haben eine begrenzte Auflösung, das dieses relevant ist.
  • Mal sehen, einige der code, beginnend mit dem code, der Ihnen Antworten, dass sind "ein wenig abseits". Dein Algorithmus scheint sinnvoll; es klingt wie das problem, das Sie haben, ist mit Debuggen. Schwer, Ratschläge zu geben, auf Debuggen, ohne dass der code.
  • Meine Heuristik für mathematische Fragen ist: wenn die Mathematik übersetzt werden oder durchgeführt in code, der es gehört. Wenn die Mathematik wird verwendet, um code, ist es vielleicht nicht. Diese Mathematik wird code, also zu den Fragen ist gut SO.
  • Sind alle Kreise den gleichen radius haben? Wenn nicht, dann ist deine Methode der Suche nach der Mitte der begrenzenden Kreis ist falsch.
  • Dies ist eine Frage der Programmierung, und schon gar nicht Hausaufgaben. @eed3si9n war auf den Punkt, mit Hilfe es für eine umgebende region. Mein plan ist, den Minimal Einschließenden Kreis, um zu bestimmen, wenn Kreise sind nahe genug, Sie zu behandeln als eine Gruppe und nicht als Individuen.

InformationsquelleAutor Corey Ogburn | 2010-01-18
  1. 5

    Seine als Minimal Einschließenden Kreis ("MEC"), oder manchmal auch "kleinsten umschließenden Kreis".

    Eine nette Seite: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

    • Ich denke, es ist nicht genau das, was er sucht: MEC sieht für den kleinsten Kreis enthält eine (endliche) Menge von Punkten. Er sieht für einen Kreis mit anderen Kreisen. Es ist wahrscheinlich ein guter Ausgangspunkt, wenn.
    • Ich bin mir nicht sicher, die Arbeit hier? Der OP will umschließen die Kreise, die im Gegensatz zu "big points", könnte jeder einen anderen radius.
    • Ich habe umgesetzt MEC für azspcs.net/Contest/PointPacking so sagen kann, es ist definitiv übersetzbar zu diesem problem; der Programmierer muss acount für Verschieden große Kreise, offensichtlich
    • Ich bin neugierig: Finden Sie ein Kreis durch 3 Punkte ist ziemlich einfach, aber die Suche nach einem Kreis berührt, die 3 anderen Kreisen ergibt sich ein system aus 3 quadratischen Gleichungen, und meine computer-algebra-system kann nicht finden eine Lösung für Sie. Was macht Sie so sicher MEC kann einfach übersetzt zu diesem problem? Auch, wenn ich mich Recht erinnere MEC kann vereinfacht werden, indem nur anhand der Punkte auf der konvexen Hülle. Das wird nicht funktionieren mit Kreisen.
    • Die MEC-algorithmen arbeiten, indem Sie eine große umgebende Kreis und schrumpft es. Sie können die Kreise und nicht als Punkte darstellen, deren Zentren, sondern als Punkte auf Ihren Umfang; Sie könnten einfach verwenden Punkte bei ausreichend kleinen Abständen auseinander, oder Sie tun können, die Mathematik zu setzen den Punkt auf dem äußersten Punkt der perimeter vom Zentrum der bounding-circle, etc.
    InformationsquelleAutor Will
  2. 11

    Gegeben zwei Kreise mit Zentren [x1,y1], [x2,y2], und die Radien R1 und R2. Was ist die Mitte des umschließenden Kreis?

    Davon ausgehen, dass R1 nicht größer als R2. Wenn der zweite Kreis ist kleiner, dann nur tauschen.

    1. Berechnen Sie den Abstand zwischen den Mittelpunkten der Kreise.

      D = sqrt((x1-x2)^2 + (y1-y2)^2)

    2. Übernimmt den ersten Kreis liegen vollständig im inneren des zweiten Kreis? Wenn also (D + R1) <= R2, dann sind wir fertig. Zurück den größeren Kreis als den umschließenden Kreis mit Mittelpunkt [x1,x2], mit radius R2.

    3. Wenn (D+R1) > R2, dann den umschließenden Kreis hat einen radius von (D+R1+R2)/2

    In diesem letzteren Fall, der Mitte der einschließenden Kreis liegen muss entlang der Verbindungslinie zwischen den beiden Zentren. Also wir schreiben können das neue Zentrum

    center = (1-theta)*[x1,y1] + theta*[x2,y2]

    wo theta ist gegeben durch

    theta = 1/2 + (R2 - R1)/(2*D)

    Beachten Sie, dass theta immer eine positive Zahl sein, da wir versichert haben, dass (D+R1) > R2. Ebenso sollten wir in der Lage sein, um sicherzustellen, dass theta ist nie größer als 1. Diese zwei Bedingungen stellen sicher, dass die umschließenden center liegt genau zwischen den zwei ursprünglichen Kreis-Zentren.

    • während die beiden Kreis-Fall ist trivial, ist es nicht extrapolieren, um effizient zu finden, das Zentrum von N Kreisen.
    • Ich bin damit einverstanden, dass dieser Algorithmus muss nicht verlängern, um n Kreise. Aber die direkte Frage war für einen minimalen Kreis, umschließt zwei Kreise.
    • Vereinbart, es war der OP, der war, sich eine 2-Kreis-Lösung einfach effizient erweitert zu N 🙂
    InformationsquelleAutor
  3. 4

    Da meine ungenaue Lösung war nicht beliebt. Hier ist ein Weg, um die exakte Lösung. Aber seine langsam ( O(N^4)? ) und sehr böse. (Im Gegensatz zu den ungenauen Methode)

    Zuerst müssen Sie wissen, dass die drei Kreise finden wir einen Kreis tangential zu dem Sie alle als enthält alle drei. Dies ist einer der Kreise des Apollonius. Sie können den Algorithmus von mathworld.

    Weiter können Sie zeigen, dass die kleinsten einschließenden Kreis von N Kreisen tangential an mindestens 3 der N Kreise.

    Zu finden, dieser Kreis, den wir tun, die folgenden

    1. Schleife durch alle Tripel von Kreisen - O(N^3)
    2. finden Sie die umschließenden Apollonius Kreis der 3 Kreise - rechnerisch böse
    3. wenn es umschließt alle Kreise hinzufügen, um eine Liste der Potenziale - check ist O(N)
    4. - Lösung ist das potential mit dem kleinsten radius

    Kann es einige tricks, um diese Fahrt, aber es sollte Ihnen genau die passende Lösung.
    Einige der "tricks" für immer Kleinsten Umschließenden Kreis algorithmen zur linearen Zeit anwendbar sein kann hier, aber ich vermute, Sie würde nicht trivial sein Anpassungen.

    • Oops ein Fehler unterlaufen ist, hier, zum kleinsten Kreis umschließt drei Kreise ist entweder, einen der Kreise (wenn die anderen sind in Ihr enthalten ist), einen Kreis tangential zu zwei von Ihnen (wenn die anderen enthalten ist, und innerhalb dieses Kreises) oder einen Kreis tangential an alle drei (eines Apollonius-Kreis). Beachten Sie, dass dies hat keinen Einfluss auf die Laufzeit, aber nicht ändern, Schritt 2 etwas.
    • +1 für die mathworld-link.
    InformationsquelleAutor Michael Anderson
  4. 4

    Gibt es problem Sie bei der hand haben, heißt Kleinsten umschließenden Sphäre der Sphären. Ich habe geschrieben, meine Diplomarbeit über es, sehen "Kleinsten umschließenden ball der Bälle", ETH Zürich.

    Finden Sie eine sehr effiziente C++ Umsetzung in der Computational Geometry Algorithmen Library (CGAL) im Paket Bounding Volumes. (Es gibt keine Notwendigkeit, alle von CGAL; nur extrahieren Sie die gewünschten Quell-und-header-Dateien, und Sie sind in Betrieb.)

    Hinweis: Wenn Sie auf der Suche für einen Algorithmus zur Berechnung der kleinsten einschließenden Kugel der Punkte nur, es gibt auch andere Implementierungen gibt, sehen dieser Beitrag.

    • +1 Dieses post klar sollte viel mehr upvotes seit Ihrer Dissertation beschäftigt sich genau mit der Frage, problem!!!
    InformationsquelleAutor Hbf
  5. 3

    Ich werde empfehlen, gegen diesen nun

    Siehe die Diskussion weiter unten.

    Ursprünglichen Gedanken

    Ich würde einen iterativen push-pull-Methode.

    1. Erraten, wo setzen Sie den center (einfachste wäre die mittlere position aller Zentren)
    2. Berechnen Sie die Vektoren zu den entferntesten Punkt auf jeden Kreis. Diese sind immer in die Richtung, in der Mitte von diesem Kreis und haben die Länge distance_to_center_of_circle[i]+radius_of_circle[i] und bilden die Vektor-Summe, wie Sie gehen. Beachten Sie auch, dass die nötigen radius an der aktuellen Lage ist das maximum dieser Längen.
    3. Schlagen vor, ein Schritt (sagen) 1/5 oder 1/10 der vektorielle Summe aus 2, und wiederholen Sie die Berechnungen aus 2 für den neuen Punkt
    4. Wenn der neue Punkt muss von einem kleineren Kreis als die alten, machen den neuen Punkt der aktuelle Punkt, ansonsten split den Unterschied, verringern Sie die Größe der vorgeschlagene Schritt (sagen wir mal zur Hälfte).
    5. goto 3

    Du fertig bist, wenn es nicht mehr[+] konvergieren.

    Nikie stieß auf ihn, bis...

    Angeforderte Klärung der Schritt zwei. Rufen Sie die position getestet werden \vec{P} (ein Vektor Menge).[++] Rufen Sie die Zentren jedes Kreises \vec{p}_i (auch Vektor-Mengen) und dem radius des jeweiligen Kreises ist r_i. Bilden Sie die Summe \sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i).[+++] Jedes element der Summe weist in die Richtung, aus der aktuellen Evaluierung Punkt in Richtung der Mitte des Kreises in Frage, aber länger durch r_i. Die Summe selbst ist es ein Vektor der Menge.

    Den radius R mitschicken der ganze Kreis von P ist die max(|p_i-P|_r_i).

    Pathologischen Fall

    Ich glaube nicht, dass dem besonderen Fall nikie ' s gebracht, ist ein problem, aber es hat mich auf einen Fall, wo dieser Algorithmus schlägt fehl. Das scheitern ist ein scheitern an der Verbesserung Lösung, eher als eine abweichende, aber immer noch...

    Betrachten vier Kreise, die alle den radius 1 positioniert

    (-4, 1)
(-5, 0)
(-4, 1)
( 5, 0)

    ist und eine Ausgangsposition von (-1, 0). Symmetrische, durch design, so dass alle Entfernungen liegen entlang der x-Achse.

    Die richtige Lösung ist (0, 0) mit radius 6, wobei der Vektor berechnet, der in Schritt 2 werden über ::berechnet wütend:: (-.63, 0), zeigt in die falsche Richtung, wodurch nie zu finden die eine Verbesserung gegenüber der Herkunft.

    Nun, der obige Algorithmus würde die eigentliche pick (-2, 0) für den Startpunkt, die einen ersten Vektor-Summe:berechnet wütend:: über +1.1. So, eine schlechte Wahl der Schrittweite auf (3) resultiert in einer weniger als optimale Lösung. ::seufz::

    Mögliche Lösung:

    • In (3) werfen Sie einen zufälligen Bruch zwischen (sagen wir +1/5 -1/5) ggf. gewichteten in Richtung auf die positive Größe.
    • In (4) wenn der Schritt abgelehnt, Sie einfach zurück zu Schritt drei, ohne dabei die Schrittweite Grenzen.

    Jedoch, an diesem Punkt ist es nicht viel besser als ein reiner random walk, und Sie nicht haben, eine einfache Bedingung für wissen wenn es ist angenähert. Meh.

    [+] Oder die Leistung zu Ihrer Zufriedenheit sein, natürlich.
    [ ++ ], Mit latex-notation.
    [+++] Hier \hat{} bedeutet, dass der normalisierte Vektor zeigt in die gleiche Richtung wie das argument.

    • +1 für eine konkrete und lebendige Anregung. Ich denke, es gibt Fälle, wo es möglicherweise nicht konvergieren, um die optimale Lösung, denn 2 Kreise sind gleich weit von der aktuellen Mitte, und bewegen Sie die center-entweder man erhöht den radius. (Man Stelle sich finden, den Kreis für die 3 center-Punkte, die form einer stumpfen, isocles Dreieck)
    • Ich habe eine harte Zeit, die überzeugen mich so oder so. Wenn Sie kann stecken, nehmen Sie sich ein Monte-Carlo-Ansatz zu schütteln es Locker. Ob das lohnt oder nicht, hängt davon ab, wie schlecht Sie wirklich brauchen, das minimum.
    • Überzeugen Sie sich selbst, zeichne zwei Punkte A und B, 3 Einheiten auseinander. Dann zeichnen Sie einen Kreis mit einem radius von 2 Einheiten um jeden Punkt. Rufen Sie eine der circle-circle intersection Punkte C. stellen Sie sich A und B sind gegeben Eingabe Punkte und C ist die aktuell geschätzten center. Offensichtlich C ist nicht optimal. Aber alle Punkte zwischen C und A sind außerhalb des Kreises um B, also in Richtung A verschieben Sie den center weiter Weg von B, so wäre es erhöhen Sie den radius. (und Umgekehrt für B). So würde der Algorithmus beendet.
    • Ich glaube nicht, dass dies der Fall ist ein problem. Die Vektor-Summe der in Schritt 2 zeigt nun in die Richtung des D in der Mitte AB, also ich glaube es hält sich die Arbeit in die richtige Richtung. Der Ort, wo es stecken könnte, ist, wenn es zwei nicht-äquivalenten lokalen minima. (Der Algorithmus, den ich angepasst diese aus ist ziemlich robust (obwohl wir es verwenden, auf das Rauschen der Daten, die nicht zugeben pathologischen Fällen).)
    • Ich glaube, ich missverstanden, Ihre Algorithmus. Könnte Sie klären, Schritt (2)? Wenn Sie fügen Sie einfach bis alle Vektoren aus der aktuellen center-Position, um die input-center-Punkte, wie würde das überhaupt konvergieren? (Nehmen wir beispielsweise an, alle Radien 0 sind. Beginnen Sie mit der mittleren position. Wenn man die vektorielle Summe aus der mittleren position, um jede der Eingabe-Punkte, erhalten Sie immer 0.)
    • Zunächst in Reaktion auf Ihre Klärung: nehmen Sie \sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i). Wenn r_i=0, dann wird der Ausdruck reduziert zu \sum_i=1^n (p_i - P). Konvergenz ist erreicht, wenn dieser Ausdruck 0 ist. Dies ist der Fall, wenn P ist der Mittelwert über p_i.
    • Aber Sie können leicht beheben diese. Grob gesprochen: Starten Sie auf eine beliebige Position, und bewegen sich in Richtung der Tangente Punkt, der die maximale Entfernung. (So habe ich das falsch verstanden, Ihren Algorithmus auf den ersten). Sie müssen einige spezielle Behandlung, wenn es mehr als nur einen Punkt mit maximalen Abstand.
    • Schön. Das handling ist möglicherweise die Verwendung der Vektor-Summe der betreffenden Richtung.

    InformationsquelleAutor dmckee
  6. 2

    Habe ich genommen, was Sie zu sagen hatte, und hier ist die Lösung, die ich entdeckt:

    public static Circle MinimalEnclosingCircle(Circle A, Circle B) {
            double angle = Math.Atan2(B.Y - A.Y, B.X - A.X);
            Point a = new Point((int)(B.X + Math.Cos(angle) * B.Radius), (int)(B.Y + Math.Sin(angle) * B.Radius));
            angle += Math.PI;
            Point b = new Point((int)(A.X + Math.Cos(angle) * A.Radius), (int)(A.Y + Math.Sin(angle) * A.Radius));
            int rad = (int)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2)) / 2;
            if (rad < A.Radius) {
                return A;
            } else if (rad < B.Radius) {
                return B;
            } else {
                return new Circle((int)((a.X + b.X) / 2), (int)((a.Y + b.Y) / 2), rad);
            }
        }

    Kreis ist definiert durch die X, Y von der Mitte und einem Radius, alle sind int-Werte. Es gibt einen Konstruktor, der Kreis(int X, int Y, int Radius). Nach dem Ausbruch aus einigen alten trig Konzepte, ich dachte, der beste Weg war, die 2 Punkte auf den Kreisen, die am weitesten auseinander. Einmal habe ich, dass der Mittelpunkt der Mittelpunkt wäre und die Hälfte der Strecke wäre, den radius und damit habe ich genug zu definieren, wird ein neuer Kreis. Wenn ich will, zu umfassen 3 oder mehr Kreise, die ich zunächst führen Sie diese auf 2 Kreise, dann habe ich führen dies auf die daraus resultierenden umfassenden Kreis und noch ein Kreis und so weiter, bis der Letzte Kreis umgeben ist. Es kann ein effizienter Weg, dies zu tun, aber jetzt funktioniert es und ich bin glücklich damit.

    Ich das Gefühl, seltsam Antwort auf meine eigene Frage, aber ich konnte nicht kommen, um diese Lösung, ohne alle Ideen und links. Vielen Dank an alle.

    • Eigentlich habe ich getestet für: Kreis(25,30,20) und Kreis(45,30,40) und es gibt den zweiten Kreis (was falsch ist).
    • Ich bin mir nicht sicher, wie Sie kamen, um zu, dass, ich habe diese 2 Kreise und der Kreis, das zurückgegeben wird, für mich ist ein Kreis(45, 29, 40). Es ist integer Mathematik, die erklärt, warum es leicht aus, aber das ist richtig. Bitte werfen Sie einen Blick auf mein Projekt unter coreyogburn.com/page/Circle-Library.aspx, um die Umsetzung sehen, ich Teste mit. Wenn Sie immer noch ein problem, bitte lassen Sie mich wissen, dort oder hier.
    • Nie Verstand. Das problem war das Zeichenprogramm ich war mit. Es war eine Halbierung der Radien der Kreise. Kreis(45, 30, 40) ist in der Tat ein richtiger Kreis. Sorry für die Verwirrung.
    • Ich Schätze die Doppel-check.
    • Hey Corey - ich versuche, herauszufinden, wie zu lösen genau dieses problem. Habe ich noch nicht getestet dieser Algorithmus aber ich denke, es gibt ein problem mit der Idee, dass man es testen kann, auf die zwei ersten, und verwenden Sie dann das Ergebnis mit dem nächsten Kreis und so weiter. Zum Beispiel, wenn Sie zeichnen ein gleichseitiges Dreieck, und Platz 3 kleinen Kreise, jeder mit seinem Zentrum an jeder Ecke, fast die Hälfte der kleinste Kreis umfasst die beiden ersten überlauf aus dem kleinsten Kreis umfasst die drei Kreise.
    • Für zukünftige Leser-werfen Sie einen Blick auf die Seite : en.wikipedia.org/wiki/Problem_of_Apollonius bietet eine algebraische Lösung für einen Kreis tangential an 3 Kreise. Verwenden Sie einfach -1 als das Zeichen zu finden, den Kreis, das am weitesten entfernt. 2 Kreise ist die Lösung nur, wenn Sie in genau entgegengesetzte Richtungen.

    InformationsquelleAutor Corey Ogburn
  7. 0

    Nur verstehen die Gleichungen der Kreis und daraus eine Gleichung (oder eine Serie) für die Antwort finden, die dann mit der Umsetzung beginnen. Vielleicht werden wir in der Lage sein, um Ihnen zu helfen, die Euch etwas getan haben.

    InformationsquelleAutor Chathuranga Chandrasekara
  8. 0

    Also, wenn Sie brauchen nicht die exakten Kreis um diese Näherung machen könnte.

    1. Nehmen den Durchschnitt aller Zentren der Kreise nennen dies
      Punkt X
    2. Seien R1 die maximale Distanz von X zu einem Mittelpunkt des Kreises.
    3. Sei R2 der maximale radius der Kreise

    Alle Kreise müssen fallen in den Kreis zentriert auf X mit radius R1+R2

    • -1: nicht die kleinste möglich, Kreis.
    • In der Tat ist es nicht, aber es ist wahrscheinlich zu geben, ein besseres Ergebnis als die iterative Methode beschrieben im letzten Absatz des OP. Daher meine Annahme, dass eine einfache, aber ungenaue Methode akzeptabel wäre.
    InformationsquelleAutor Michael Anderson
  9. 0

    Dies ist kein triviales problem. Ich habe nicht Lesen Sie alle der oben genannten Antworten, so, wenn ich wiederhole, was jemand schon gesagt hat, die Schuld ist mein.

    Jeder Kreis c_i ist bestimmt durch 3 Parameter x_i,y_i,r_i

    3 Parameter gefunden werden müssen x*,y*,r* für den optimalen Kreis C*

    C* ist, so dass es enthält c_i für alles, was ich

    Lassen d_i = ||(x,y)-(x_i,y_i)|| + r_i

    Dann, wenn r den radius des Kreises, enthält alle c_i, dann r >= d_i für alles, was ich

    Wollen wir r so klein wie möglich

    So, r* = max(d_i)

    Somit möchten wir minimieren das max von d_i

    Also (x*,y*) sind gegeben durch die arg min max(d_i). Und einmal (x*,y*) gefunden werden, r* kann leicht berechnet und wird gleich max(d_i). Dies ist ein minimax-problem.

    Dinge einfacher zu machen zu verstehen, betrachten Sie nur 2 Kreise, wie finden wir (x*,y*)?

    (x*,y*) kann gefunden werden, indem die (x,y) zu minimieren, dass (d_1 - d_2)^2. Im Allgemeinen Fall

    lassen e_ij = (d_i - d_j)^2

    Dann definieren e = \sum e_ij für i != j (n 2 Wählen Sie Begriffe, die in dieser Summe)

    (x*,y*) = arg min e

    Und das ist, was gelöst werden muss für.

    Tipp: wenn r_i = 0 für alle i, dann ist dieser reduziert sich auf die traditionelle minimalen einschließenden Kreises problem, wenn die Eingabe eine Reihe von Punkten, und wir wollen finden, Mindest-Kreis, umfaßt alle von Ihnen.

    InformationsquelleAutor morpheus
Schreibe einen Kommentar