tangente an polygon
-
Wie kann man in O(log n = Anzahl Punkte, die das Poylgon bestimmen) die Tangenten an ein konvexes Polygon für einen vorgegebenen Punkt außerhalb des Polygons finden?
-
log n? Das riecht nach Intervallschachtelung. Wir fangen an einem Punkt und seinem "Gegenüber" an, d.h. dem Punkt, der in der Liste der Eckpunkte gerade N/2 Plätze weg ist. Zu diesen zwei Punkten bestimmen wir irgendein Maß, wie weit sie "außen" liegen, aus Sicht des Stützpunktes. Wie genau dieses Maß lauten könnte, weiß ich gerade nicht. Es könnte so etwas wie der Winkel zwischen den beiden Strahlen sein, die man vom Stützpunkt aus auf die beiden Punkte fällen kann.
Dann machen wir Intervallschachtelung und gucken die um jeweils N/4 versetzten Punkte an und so weiter. Wenn wir einen weiter "außen" liegenden Punkt gefunden haben, dann nehmen wir fortan diesen als Referenz. So fahren wir fort, bis unsere Intervallschachtelung bei einer Schrittweite von 1 angekommen ist. Da das Polynom konvex ist, sollte das gegen die beiden "äußersten" Punkte konvergieren (Beweis dazu mache ich mal nicht. Aber nachdem ich ein paar Skizzen auf Papier gemalt habe und diese Behauptung nicht widerlegen konnte, stelle ich sie mal als Fakt hin
). Da es ein Intervallschachtelungsalgorithmus ist, der in jedem Einzelschritt konstante Laufzeit benötigt (das Maß, wie weit ein Punkt "außen" liegt, kümmert sich nur um den Vergleich zum vorherigen Kandidaten, der Rest der Punkte ist egal) sollte die Laufzeit O(log N) sein.PS: Bei genauerem darüber Nachdenken, komme ich zu dem Schluss, dass die beiden Behauptungen stimmen. Der Winkel zwischen den beiden Strahlen ist das Maß, dass es zu maximieren gilt. Und die Konvexität ist der Grund, warum das Verfahren funktioniert. Beweise sind recht trivial:
1. Wenn es einen Tangentenpunkt mit einem kleineren Zwischenwinkel gäbe, dann muss die Tangente die Verbindung zwischen den beiden Punkten schneiden, die einen größeren Zwischenwinkel haben, denn die Menge der Eckpunkte ist zusammenhängend über ihre Kanten. Das würde aber bedeuten, dass diese Tangente keine Tangente wäre. Der Beweis ist durch Widerspruch erbracht.
2. Das Verfahren muss konvergieren, denn es gibt keine lokalen Maxima des Winkelkriteriums. Wenn es ein solches lokales Maximum gäbe, dann müsste eine Tangente durch dieses Maximum einerseits lokal das Polynom nur berühren, andererseits später wieder das Polynom schneiden. Dies steht aber im Widerspruch zur Konvexität, die genau die Existenz solcher Verbindungen verbietet.
-
SeppJ schrieb:
log n? Das riecht nach Intervallschachtelung.
In der Informatik übrigens besser bekannt unter dem Namen "binäre Suche".
-
Jester schrieb:
SeppJ schrieb:
log n? Das riecht nach Intervallschachtelung.
In der Informatik übrigens besser bekannt unter dem Namen "binäre Suche".
Sei froh, dass du die erste Version des Beitrags nicht gesehen hast, wo ich das, unter Bemühung all meiner Informatikkenntnisse, noch "Divide & Conquer" genannt habe. Immerhin kann ich mich rausreden, dass ich selbstverständlich ein dichotomes D&C gemeint habe und nicht einfach nur unwissend einen Begriff falsch benutzt habe
.
-
Hier wird aber in der Liste der Eckpunkte eine Art Sortierung erwartet?
Ich habe keine Angabe darüber, wie mein POlygon abgespeichert ist
-
Du kommst nicht darum herum eine Annahme zu treffen wie Deine Eingabe aussieht -- wie sollst Du sonst einen Algorithmus bauen? Das ist im Prinzip Teil der Aufgabenstellung. Allerdings wird es natürlich oft weggelassen und eine Art Standardrepräsentation angenommen. In diesem Fall handelt es sich um ein Polygon und es ist natürlich anzunehmen, dass das als Liste der Punkte in der Reihenfolge des Polygons gegeben ist.
Um dieses Problem ein bisschen loszuwerden formuliert man sowas häufig auch als Datenstruktur mit Vorverarbeitung und sagt: baue eine Datenstruktur, die nach linearer Vorberechnung solche Anfragen in O(log n) Zeit verarbeiten kann. Dann wird man das Problem ein bisschen los, weil sich so ziemlich alle halbwegs nützlichen Repräsentationen in linearer Zeit ineinander überführen lassen.
