Linia oddziela dwa zestawy punktów

Czy istnieje sposób na stwierdzenie, czy dwa zestawy punktów można oddzielić linią?

Mamy dwa zestawy punktów i jeśli istnieje linia, która oddziela i tak że wszystkie punkty i tylko po jednej stronie linii oraz wszystkie punkty i tylko po drugiej stronie.B A B A A B $A$$B$$A$$B$$A$$A$$B$$B$

Najbardziej naiwnym algorytmem, jaki wymyśliłem, jest zbudowanie wypukłego wielokąta dla i i przetestowanie go pod kątem przecięcia. Wygląda na to, że złożoność czasu dla tego powinna wynosić jak przy konstruowaniu wypukłego wielokąta. W rzeczywistości nie oczekuję poprawy złożoności czasu, nie jestem pewien, czy można to w ogóle poprawić. Ale przynajmniej powinien istnieć piękniejszy sposób ustalenia, czy istnieje taka linia.B O ( n log h $A$$B$$O(n\log h)$

Zarówno uli, jak i Dave Clarke poprawnie zauważają, że jest to problem programowania liniowego, nawet w wyższych wymiarach (czy te dwa zestawy punktów można oddzielić hiperpłaszczyzną?), A zatem można je rozwiązać w czasie wielomianowym. Ponieważ jednak punkty znajdują się w płaszczyźnie, problem można rozwiązać w czasie , gdzie$O(n)$$n$ jest całkowitą liczbą punktów.

Najprostszym rozwiązaniem jest prawdopodobnie randomizowany algorytm Seidela. Wybierz punkt wejściowy $p$ równomiernie losowo i rekurencyjnie obliczyć linię oddzielającą $\ell$ dla wszystkich punktów z wyjątkiem $p$ .

• Jeśli taka linia nie istnieje, pierwotnych punktów nie da się rozdzielić.

• Jeśli $p$ znajduje się po właściwej stronie $\ell$ , to $\ell$ oddziela oryginalne punkty.

• Jeśli $p$ znajduje się po niewłaściwej stronie $\ell$ , wówczas albo oryginalne punkty można oddzielić linią przechodzącą przez $p$ , albo oryginalnych punktów w ogóle nie da się oddzielić. Ten warunek jest łatwy do sprawdzenia w czasie $O(n)$ [ćwiczenie].

$O(n)$

Właściwością dwóch zestawów danych jest liniowa separowalność , po prostu to, że istnieje linia, która je oddziela. Wiele uczenia maszynowego jest poświęcone znajdowaniu klasyfikatorów liniowych , które są liniami, które wykonują separację, którą jesteś zainteresowany.

$w_1$$w_2$$w_3$$(a_1,a_2)$$A$$w_1 a_1+w_2a_2\ge w_3$$(b_1,b_2)$$B$$w_1 b_1+w_2b_2<w_3$$w_1 x+w_2y\ge w_3$$A$

$w_1,w_2,w_3$$A$$B$

$w_1,w_2,w_3$

$w_1 a^i_1+w_2a^i_2\ge w_3$$i=1,..,|A|$$A=\{(a^1_1,a^1_2),\ldots,(a^{|A|}_1,a^{|A|}_2)\}$

$w_1 b^j_1+w_2b^j_2< w_3$$j=1,..,|B|$$B=\{(b^1_1,b^1_2),\ldots,(b^{|B|}_1,b^{|B|}_2)\}$

Jeśli ograniczenia te są spójne, wówczas istnieje linia.

$2$