Dreiecke in der Ebene lernen

13

Ich habe meinen Schülern das Problem zugeteilt, ein Dreieck zu finden, das mit einer Ansammlung von Punkten in R 2 übereinstimmt , die mit ± 1 gekennzeichnet sind . (A Dreieck T ist konsistent mit der markierten Probe , wenn T alle positiven und keines der negativen Punkte enthält, durch Annahme, die Probe zugibt mindestens 1 konsistente Dreieck).mR2±1TT

Das Beste, was sie (oder ich) tun können, ist ein Algorithmus, der in der Zeit abläuft , wobei m die Stichprobengröße ist. Kann jemand es besser machen?Ö(m6)m

Aryeh
quelle
Um es klar zu sagen: Die Eckpunkte des Dreiecks müssen nicht unbedingt Punkte der Sammlung sein, oder? Und es ist akzeptabel, negative Punkte an der Grenze zu haben?
ex0du5
(1) Ich hatte dafür gestimmt, die Frage zu schließen, weil ich das Problem falsch verstanden hatte. Das System erlaubt mir nicht, meine Abstimmung abzubrechen, aber ich annulliere sie praktisch. (2) Ich glaube, es gibt einen O (m log m) -Zeitalgorithmus, aber ich habe momentan keine Zeit, ihn zu verifizieren. Die Idee besteht darin, die konvexe Hülle der positiven Beispiele zu berechnen und um diese konvexe Hülle herumzuwischen, um drei Linien zu finden, die das gewünschte Dreieck bilden.
Tsuyoshi Ito
@ ex0du5 - In der Tat müssen die Eckpunkte des Dreiecks nicht aus den Abtastpunkten bestehen. Grenzprobleme können hier ignoriert werden, da sie unwesentlich sind. [Wenn die Grenze als Teil des Dreiecks zählt, haben Sie keine negativen Punkte an der Grenze.]
Aryeh
@TsuyoshiIto: Ich dachte ähnlich, aber es gibt Fälle, in denen die Kanten des Dreiecks nicht kollinear zu den Kanten des konvexen Rumpfs sein können, aber immer noch ein Dreieck vorhanden ist. Das Dreieck enthält offensichtlich immer noch die konvexe Hülle, aber es erweitert nicht nur die Linien der Hülle und findet das Dreieck. Möglicherweise benötigen Sie Linien, die um einige Scheitelpunkte gedreht werden, um die negativen Punkte zu vermeiden. Aus diesem Grund habe ich nach Negativen an der Grenze gefragt, um einen Suchalgorithmus zu ermöglichen, der Linien von den Scheitelpunkten des Rumpfs zu Negativen auswählt, um eine diskrete Suche zu ermöglichen.
ex0du5
@ ex0du5: Nun, ich habe nicht angenommen, dass die Kanten des Dreiecks parallel zu einigen Kanten der konvexen Hülle der positiven Beispiele sind.
Tsuyoshi Ito

Antworten:

14

Wie @TsuyoshiIto vorschlägt, gibt es für dieses Problem aufgrund von Edelsbrunner und Preparata einen -Zeitalgorithmus. Tatsächlich findet der Algorithmus ein konvexes Polygon mit der minimal möglichen Anzahl von Kanten, die die beiden Punktmengen trennen. Sie beweisen auch eine Untergrenze von Ω ( n log n ) für das allgemeinere Problem im algebraischen Entscheidungsbaummodell; Es ist jedoch nicht klar, ob diese Untergrenze für den Dreiecksfall gilt.Ö(nLogn)Ω(nLogn)

Eine vollständige Beschreibung des Algorithmus ist zu lang, um hier veröffentlicht zu werden, aber hier ist die Grundidee. Sei die konvexe Hülle der positiven Punkte. Betrachten Sie für jeden negativen Punkt q die Linien durch q , die C tangieren . Diese Linien teilen die Ebene in vier Keile, von denen einer C enthält ; sei W ( q ) der Keil gegenüber demjenigen, der C enthält . Schließlich sei F (die "verbotene Region") die Vereinigung aller Keile W ( q ) . Jedes trennende Dreieck muss C von trennenCqqCCW(q)CFW(q)CF. Sowohl als auch F können in O ( n log n ) Zeit konstruiert werden.CFÖ(nLogn)

Beispiel für $ C $ und $ F $

Beschriften Sie die Kanten von abwechselnd im und gegen den Uhrzeigersinn. Edelsbrunner und Preparata beweisen ferner, dass es ein trennendes Dreieck gibt, dessen Kanten kollinear mit den Kanten von F im Uhrzeigersinn sind . In O ( n ) zusätzlicher Zeit können wir die (notwendigerweise im Uhrzeigersinn) Kante von F finden, die zuerst von einem Strahl von jeder Kante e im Uhrzeigersinn getroffen wird ; Nennen Sie diese Kante den "Nachfolger" von eFFÖ(n)Fee . Die Nachfolgezeiger unterteilen die Ränder im Uhrzeigersinn in Zyklen. Wenn es ein trennendes Dreieck gibt, hat einer dieser Nachfolgezyklen die Länge 3 (und keiner hat eine Länge von mehr als 4).

Weitere Informationen finden Sie im Originaldokument:

Jeffε
quelle
3

Es scheint mir, dass es ausreicht, Tangentenlinien von den '-1'-Punkten auf die konvexe Hülle der' +1'-Punkte als Kandidaten für die Seiten von (sagen wir, dass '+1'-Punkte innerlich sind zu TTT ).

tEINBtBCBC ist der Tangentenpunkt).

t

  1. t mit allen anderen Linien.
  2. EINBtEINEINBCEINBBCEINC
  3. t

Ö(m2)

Shalabuda
quelle