Implementierung von Radial Sweep

Question

Sie haben N Punkte in 2D-Ebene gegeben, ich muss den kleinsten Radius eines Kreises herausfinden, der mindestens M Punkte enthält.

Ansatz ich verwende: -

Ich werde auf Kreisradius binäre Suche.

Wählen Sie einen beliebigen Punkt P aus der gegebenen Menge. Wir drehen einen Kreis C mit dem Radius R unter Verwendung von P als die "Rotationsachse" (durch Konvention in der Richtung gegen den Uhrzeigersinn), d. H. Wir halten C, um jedes Mal während der Rotation P zu berühren. Während C gedreht wird, behalten wir einen Zähler bei, um die Anzahl der eingeschlossenen Punkte zu zählen. Bitte beachten Sie, dass sich dieser Counter nur ändert, wenn ein Punkt Q in den Bereich des Kreises C eintritt (oder diesen verlässt). Unser Ziel ist es, einen Algorithmus zu entwickeln, der diesen Counter erhöht oder verringert, wenn ein anderer Punkt Q ≠ P tritt (oder verlässt) den Bereich von C.

Der Zustand des (rotierenden) Kreises C kann durch einen einzigen Parameter θθ beschrieben werden, wobei (r, θ) die Polarkoordinaten des Mittelpunkts des Kreises sind C, wenn wir P als Fixpunkt des Polarkoordinatensystems wählen. Bei diesem System bedeutet das Drehen von C ein Ansteigen von θ.

Für jeden anderen Punkt Q (≠ P) können wir den Bereich von θ berechnen, für den C Q abdeckt. Formal ausgedrückt, schließt C Q immer dann ein, wenn (iff) θ∈ [α, β].

Was ist ein optimaler Wert von θ, die in der größten Anzahl liegt von [α, β] Intervalle:

also bis zu diesem Punkt hat sich das ursprüngliche Problem reduziert worden?

Das reduzierte Problem kann mit einem hübschen Standard-O (NlogN) Algorithmus gelöst werden. [3] Dieses reduzierte Problem muss N-mal gelöst werden (eines für jeden Punkt P), daher die Zeitkomplexität O (N2logN).

ich in der Lage bin zu dem bekommen, wie Sie diesen Schritt tun:

Für jeden anderen Punkt Q (≠ P), können wir tatsächlich den Bereich von θ berechnen, für die C deckt Q. formelle Stoßen, C umschließt Q immer wenn (iff) θ∈ [α, β]. Bis zu diesem Punkt wurde das ursprüngliche Problem reduziert auf: Was ist ein optimaler Wert von θ, der in der größten Anzahl von [α, β] Intervallen liegt?

können Sie bitte vorschlagen, wie Sie diesen Teil implementieren.

Answer 1

Wenn Q betritt oder verlässt den Kreis C (mit Radius R):

• Der Abstand zwischen P und C Zentrum R ist (weil es immer ist); und

• Der Abstand zwischen Q und C dem Zentrum ist auch R

Also, wenn Sie einen Kreis mit Radius R um Q und einen Kreis mit dem Radius R um P. Die beiden Punkte, an denen zeichnen sie schneiden sich, wenn Q eintritt oder geht, die Zentren von C.

Sei ± θ die Winkel zwischen diesen Zentren von C und der Linie PQ. Wenn Sie es herausziehen, können Sie leicht sehen, dass | PQ |/2R = cos (θ), was es ziemlich einfach macht, die Winkel zu finden, nach denen Sie suchen.