Stimmt, das ist vermutlich besser, als die Methode von Seth die ich momentan für den 'lazy mode' verwende.
Ich bin aber von meinem eigentlichen Problem mal absichtlich abgekommen, weil ich es interessant fand einen exakten Algorithmus zu schreiben.


Habe ich auch zuerst gedacht, aber Fehlanzeige: (Bild 1)
Die am weitesten von einander entfernten Punkte sind in diesem Beispiel nicht auf der Umkugel! Die Grauzone zeigt, wo sich Punkte verstecken können, die eine kleinere Entfernung besitzen (innerhalb beider großer Kreise) und trotzdem außerhalb der Kugel zwischen beiden Punkten.


Nicht schlecht vom Gedanken her, aber als ich das probiert habe ist folgendes passiert: Wärend ich die Kugel in die eine Richtung ausgeweitet habe um einen dritten Punkt aufzunehmen, ist sie auf der gegenüberliegenden Seite abgeflacht und dadurch ein Punkt, der bereits ok war wieder rausgefallen!
(Bild 2)


Dein Algorithmus würde auch zu dem Beispiel im zweiten Bild führen. Den Brute-Force-Algorithmus habe ich auch implementiert und ich muss sagen, n^4 macht keinen - wirklich garkeinen - Spass. ...Aber er lief völlig bugfrei ^^.
Ich kann dir aber versichern, dass O(n^4) nicht das Minimum ist. Ich bin kein Mathematiker, aber O(n^2) geht 100% weil ich in meinem Algorithmus nur 2 Schleifen verwende.


Gegenbeweis:
(Bild 3)


Unwichtige Punkte im Vorhinein zu eliminieren wird sehr unwichtig, wenn man sich O(n) nähert und nur vier Punkte bestimmen muss. Das beste was ich dazu hatte war Punkte zu löschen, die innerhalb des Tetraeders lagen, dass ich aus meinen bisher gefundenen 4 Punkten aufgespannt habe. Und das war im Brute-Force-Algorithmus, also hilfreich aber nur ein Tropfen auf den heißen Stein.
Was O(n^4) angeht kann ich nur wieder sagen: Ich habe nur zwei Schleifen in einem Algorithmus der das Problem lößt!
Jetzt könnten die Grafiken oben natürlich gefaked sein. Sind sie aber nicht.

Zu Bild 1: die Zwei Punkte die vom innerem Kreis berüher werden, sind nicht die die am weitesten von einander entfernt sind: Es wäre der untere und einer von den beiden oberen. Der 2. oberen Punkte würden dann spätestens beide beim Suchen nach dem 3. Punkt erkant werden.

zu Bild 3: Die neue Boundingsphere muss alle Vertices umschließen.

Der Schlechteste brutforce Algoritmus müsste so ungefähr auf O(!n /!(n-4)) kommen. Bei 49 Vertices entsricht das der Warscheinlichkeit von 4 Richtigen im mit den ersten 4 gezogenen Zahlen im Lotto...

Wie ich das sehe, ist der schwierigste Teil, den Mittelpunkt der Umkugel zu finden. mein Vorschlag hierzu wäre: Reduziere das Problem auf ein kleineres und löse dieses.
Im konkreten Fall: Bilde 4er Gruppen und berechne deren Mittelpunkt (ist rel. einfach: Mittelpunkt eines unregelmäßigen Tetraeders). Hast Du eine Anzahl <>n*4 werden die verbliebenen Punkte ähnlich behandelt: bei 3 Mittelpunkt eines Dreiecks, bei 2 linie, bei 1 isses klar.
Das wiederholst Du für die erhaltenen Mittelpunkte solange, bis Du einen Punkt übrig hast. Dieser sollte dem Mittelpunkt der Umkugel doch ziemlich nahe kommen.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

@oc2k1: Bild 1 - Nein, die oberen Punkte sind nicht weiter weg. Die Bemaßung ist am falschen Punkt! Eigentlich wollte ich zum einem der oberen Punkte verbinden, um zu zeigen, dass die entfernung < 140 mm ist.
Bild 3 - Ja, aber woher soll ich beim Ausweiten der Kugel wissen, dass jetzt irgendwo in der Mitte ein Punkt rausfällt? Der rote Punkt wird ja 'urplötzlich' zu einem Punkt auf der Hülle.

@Sidorion: Divide&Conquer? Immer gerne, aber wie du schon sagtest, das ist eine Näherungslösung und da gefällt mir die von dj3hut1 doch besser, weil einfacher ^^.

Mein Algorithmus braucht immer einen Ausgangpunkt. Dafür verwende ich den Punkt, der am weitesten vom Ursprung weg liegt. Also der bei dem Sqrt(x²+y²+z²) am größten ist. Ein solcher Punkt liegt auf jeden Fall 'außen' muss aber nicht zu den Punkten gehören, die die Bounding-Sphere bilden. Daher wird er später eventuell ausgetauscht.
An diesem 1. Punkt mache ich die Hülle der Umkugel fest und lasst selbige in Richtung (0,0,0) ausdehnen. Die Umkugel wird dann solange verkleinert, bis sie auf einen Punkt trifft -> Punkt 2. (Der Algorithmus bestimmt den Punkt über eine Formel mit den Koordinaten jedes Punktes. Eine Rechung pro Punkt.)
Punkt 1 und 2 haben die gleiche Entfernung zum vorläufigen Mittelpunkt. Diese stellt den vorläufigen Radius dar.
Nun wird die Umkugel an den 2 Punkten fixiert und in ihre Richtung reduziert. Sobalt die Umkugel anstößt habe ich Punkt 3 usw.
Im ungünstigen Fall kann es passieren, dass die Umkugel durch einen neuen Fund von 1 oder 2 der vorherigen Umkugel-Punkte 'abhebt'. Diese werden dann gelöscht und die Suche muss wieder eine Stufe tiefer weiter machen. (Das ist die zweite Schleife, die im ungünstigsten Fall - alle Punkte AUF der Umkugel - für n²-Laufzeit sorgt.)
Sobald ich 4 Punkte gefunden habe (oder weniger zur Bestimmung der Umkugel gereicht haben) wird der Algorithmus beendet. Die gefundenen Punkte bilden die Umkugel.