Es gibt n Punkte auf der Ebene, wie kann man ungefähr den minimalen Radius eines Kreises finden, der einige k aus diesen Punkten abdeckt? Nummer n soll weniger als 10^4 sein.Minimaler Abdeckkreis
Es gibt lots of information auf den Fall k == n in Wikipedia, aber ich fand nichts im allgemeinen Fall.
Ein Gedanke ist, dass Sie den Durchschnitt aller Punkte als Mittelpunkt nehmen und dann den Radius vergrößern können, bis Sie k Punkte abgedeckt haben. Unter ziemlich gleichmäßigen Verteilungen würde dies wahrscheinlich eine ziemlich gute Arbeit machen, würde aber für "klumpige" Daten versagen. Zum Beispiel, wenn die Punkte in zwei engen Clustern weit voneinander entfernt wären und k klein genug wäre, um nur einen von ihnen zu benötigen, würde dies spektakulär scheitern. Wenn die Möglichkeit besteht, dass diese Clusterbildung auftritt, sollten Sie einen Clusteralgorithmus verwenden, um lokale Cluster zu identifizieren. Wenn einer der Cluster genügend Punkte enthält, verwenden Sie den Algorithmus nur für diesen Cluster.
Dies wird nicht funktionieren. Das Zentrum ändert sich, wenn Sie verschiedene Sätze von k Punkten betrachten. Siehe meinen Kommentar zum obigen OP. –
OP sagte auch "ungefähr", was ich meine, eine gute Antwort zu finden, aber nicht unbedingt die optimale Antwort. – MattPutnam
@ se0808, was meinst du mit "ungefähr" in deinem ursprünglichen Beitrag? Wie ungefähr? Innerhalb von 10% des Minimums? 50%? –
ein Kandidat Radius r gegeben, können Sie die maximale Anzahl an Punkten finden, die von einem Kreis mit dem Radius enthalten sein können r durch jedes Paar (p1, p2) Punkte zu nehmen und sehen, wie viele Punkte von jedem der beiden Kreise mit einem Radius enthalten sind r mit p1 und p2 an der Grenze.
Wissen, können Sie Binär für die kleinste r so suchen, dass ein Kreis von Radius r enthält k oder mehr Punkte.
Ja, aber leider ist die Zeitkomplexität O (n^3) mit n = 10^4. – se0808
Es ist nicht. Repariere 'p1'. Es gibt "n-1" Punkte außer "p1". Schrauben Sie einen Radius-r-Kreis auf 'p1' und drehen Sie ihn herum; jeder andere Punkt als "p1" wird den Kreis höchstens einmal pro Umdrehung betreten und verlassen. – tmyklebu
Nun, dann 'O (Iterationen * n^2 log n)' mit 'O (n log n)' von sort - aber es scheint sowieso zu langsam zu sein. – se0808
Hier ist ein Algorithmus, der einen Radius gegeben r > 0 und eine Annäherung konstant c > 0, entweder gibt einen Kreis mit dem Radius (1+c) r mindestens k Punkte oder erklärt umschließt, dass es keinen Kreis mit dem Radius ist r streng mindestens k Punkte umschließt. Die Laufzeit ist O(n (1 + k^-1 c^-2 log c^-1)), die, wenn sie in Verbindung mit der binären Suche verwendet wird, um eine ausreichend grobe Schätzung zu erhalten, schneller als tmyklebus Algorithmus sein sollte. (Um die Suche zu initialisieren, ist es möglich, in der Zeit O(n^2) eine 2 -Anpassung für r zu erhalten, indem über die Punkte Looping und lief Quick den k th engsten anderen Punkt zu finden.)
Partition die Punkte für Punkt platzieren (x, y) in einem quadratischer Behälter mit der Bezeichnung (floor(x/(2r)), floor(y/(2r))). Jeder Kreis des Radius r hat einen Innenraum, der höchstens vier Behälter überlappt. Wenn es einen Kreis mit dem Radius r gibt, der mindestens k Punkte enthält, dann gibt es i, j, so dass die Fächer (i, j), (i, j+1), (i+1, j), (i+1, j+1) zusammen mindestens k Punkte halten.
Für jedes dieser Teilprobleme platzieren Sie jeden beteiligten Punkt (x, y) in einem kleineren quadratischen Fach, (floor(x/w), floor(y/w)), wobei w = cr/(3sqrt(1/2)) eine ausreichend kleine Breite ist. Bereiten Sie jetzt eine O(c^-1) by O(c^-1) Matrix vor, in der jeder Eintrag angibt, wie viele Punkte in der entsprechenden Bin enthalten sind. Diese Matrix wird in zwei Dimensionen mit einer Null-Eins-Matrix gewandelt, die die vollständig in einem Radius enthaltenen Kisten anzeigt. Letztere Matrix aussehen könnte
01110
11111
11111
11111
01110.
Jetzt wissen wir, für jedes Zentrum auf dem Gitter eine Zahl, die r durch, wie viele Punkte ein Kreis mit dem Radius lowerbounded ist enthalten und upperbounded würde, um wie viele Punkte ein Kreis mit dem Radius (1+c) r würde enthalten.
Wenn Ihre Punkte Integer- oder Fließkomma-Koordinaten haben, ist der 2-Approximationsschritt nicht erforderlich, da die binäre Suche auf Ganzzahlen und Gleitkommazahlen ordnungsgemäß funktioniert. Wenn dies nicht der Fall ist und Sie mit reellen Zahlen arbeiten, müssen Sie nur n/k Kreise aufblasen, um eine 3- oder 4-Annäherung zu erhalten. – tmyklebu
Dies ist nicht wirklich eine Programmierfrage, würde besser passen auf https://cs.stackexchange.com/. – kebs
Sie müssen sich durch diesen einen brutalen Weg durchkämpfen. Wenn, sagen wir, n == 100 und k == 3, müssen Sie nur durch jede Kombination von 3 Punkten gehen, um diejenige zu finden, die den kleinsten Kreis hat. Sie können einige Kombinationen schnell eliminieren, indem Sie prüfen, ob der Abstand zwischen zwei Punkten größer ist als der kleinste bisher gefundene Durchmesser. –
Diese Frage scheint off-topic zu sein, weil es um das Design von Algorithmen geht und nicht um die Implementierung. Es wurde [in Informatik veröffentlicht] (http://cs.stackexchange.com/questions/31960/minimal-covering-circle) wo es direkt am Thema ist. – Gilles