Apprentissage des triangles dans l'avion

J'ai assigné à mes élèves le problème de trouver un triangle cohérent avec une collection de points dans , étiqueté avec . (Un triangle est cohérent avec l'échantillon étiqueté si contient tous les points positifs et aucun des points négatifs; par hypothèse, l'échantillon admet au moins 1 triangle cohérent).$m$$\mathbb{R}^2$$\pm1$$T$$T$

Le mieux qu'ils (ou moi) pourraient faire est un algorithme qui s'exécute dans le temps , où est la taille de l'échantillon. Quelqu'un peut-il faire mieux?$O(m^6)$$m$

Comme le suggère @TsuyoshiIto, il existe un algorithme pour ce problème, dû à Edelsbrunner et Preparata. En fait, leur algorithme trouve un polygone convexe avec le nombre minimum possible d'arêtes qui sépare les deux ensembles de points. Ils prouvent également une borne inférieure Ω ( n log n ) pour le problème plus général du modèle d'arbre de décision algébrique; cependant, il n'est pas clair si cette limite inférieure s'applique au cas du triangle.$O(n\log n)$$\Omega(n\log n)$

Une description complète de l'algorithme est trop longue pour être publiée ici, mais voici l'idée de base. Soit la coque convexe des points positifs. Pour chaque point négatif q , examiner les lignes à travers q qui sont tangents à C . Ces lignes divisent l'avion en quatre coins, dont l'un contient C ; laisser W ( q ) soit le coin opposé celui qui contient C . Enfin, soit F (la "région interdite") l'union de tous les coins W ( q ) . Tout triangle de séparation doit séparer C de $C$$q$$q$$C$$C$$W(q)$$C$$F$$W(q)$$C$$F$. Les deux et F peuvent être construits en O ( n connectent n ) fois.$C$$F$$O(n\log n)$

Étiquetez les bords de alternativement dans le sens horaire et antihoraire. Edelsbrunner et Preparata en outre montrer que si un triangle de séparation existe, alors il y a un triangle de séparation dont les bords sont alignés avec des bords dans le sens horaire de F . En O ( n ) temps supplémentaire, nous pouvons trouver le bord (nécessairement dans le sens des aiguilles d'une montre) de F d' abord frappé par un rayon de chaque bord dans le sens des aiguilles d'une montre e ; appeler ce bord le «successeur» de e . Les pointeurs successeurs partitionnent les bords dans le sens horaire en cycles; s'il y a un triangle de séparation, l'un de ces cycles successeurs a une longueur 3 (et aucun n'a une longueur supérieure à 4).$F$$F$$O(n)$$F$$e$$e$

Voir le document original pour plus de détails:

• Herbert Edelsbrunner et Franco P. Preparata. Séparation polygonale minimale . Information et calcul 77 (3): 218-232, 1988.

$T$$T$

$t$$A$$B$$t$$BC$$B$$C$

$t$

1. $t$
2. $A$$B$$t'$$A$$ABC$$AB$$BC$$A$$C$
3. $t'$

$O(m^2)$