Dreiecke in der Ebene lernen

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).$m$$\mathbb{R}^2$$\pm1$$T$$T$

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?$O(m^6)$$m$

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.$O(n\log n)$$\Omega(n\log n)$

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 trennen$C$$q$$q$$C$$C$$W(q)$$C$$F$$W(q)$$C$$F$. Sowohl als auch F können in O ( n log n ) Zeit konstruiert werden.$C$$F$$O(n\log n)$

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 $F$$F$$O(n)$$F$$e$$e$ . 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:

• Herbert Edelsbrunner und Franco P. Preparata. Minimale polygonale Trennung . Information and Computation 77 (3): 218–232, 1988.

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 $T$$T$ ).

$t$$A$$B$$t$$BC$$B$$C$ ist der Tangentenpunkt).

$t$

1. $t$ mit allen anderen Linien.
2. $A$$B$$t'$$A$$ABC$$AB$$BC$$A$$C$
3. $t'$

$O(m^2)$