Kombinacja wypukła

W geometrii afinicznej , A wypukła kombinacja pewnych punktów jest środka masy tych punktów z dodatnich współczynników. Zbiór wypukłych kombinacji tych punktów jest zatem ich wypukłą obwiednią .

Definicja

Niech E będzie się rzeczywistą afinicznej przestrzeni (to znaczy skalarne są liczbami rzeczywistymi ). Jeśli i są punktami E , wypukła kombinacja jest punktem formy $n \ in \ mathbb {N} ^ {*}$ $x_ {1}, \ ldots, x_ {n}$ $x_ {i}$ $p$

p = \ sum _ {{i = 1}} ^ {n} \ lambda _ {i} x_ {i} ~,

gdzie są dodatnie liczby rzeczywiste sumy 1. $\ lambda _ {1}, \ ldots, \ lambda _ {n}$

Problem z punktem końcowym

Problem skrajnych punktów polega na określeniu, czy punkt P 0 jest wypukłą kombinacją punktów P i , 1 ≤ i ≤ n . Dobkin Reiss i wykazały, że problem ten jest liniowy złożoności , w O ( n ) w a . Megiddo wykazały, że złożony jest liniowy w skończonym wymiarze w o skończonej d . $\ mathbb {R}$ $\ mathbb {R} ^ {2}$ ${\ mathbb {R}} ^ {d}$

Rozdzielczość sprowadza się do wiedzy, czy istnieje prosta (w ), płaszczyzna (w ) lub hiperpłaszczyzna (in , d > 3) przechodząca przez P 0 , tak że wszystkie punkty P i znajdują się po tej samej stronie prostej , samolot lub hiperpłaszczyzna. W związku z tym wraca się do problemu separacji: oddzielenia zbioru punktów hiperpłaszczyzną. $\ mathbb {R} ^ {2}$ $\ mathbb {R} ^ {3}$ ${\ mathbb {R}} ^ {d}$

W samolocie poszukiwania można przeprowadzić w następujący sposób. Przeprowadza się transformację afiniczną, tak że P 0 ma współrzędne (0; 0) i P 1 (0; 1); dlatego linia separacji, jeśli istnieje, nie może być osią y . Punkt P i ma dla współrzędnych ( x i , y i ).

Poszukiwana linia przechodzi przez P 0 , początek, i dlatego ma następujące równanie:

y = ax , co jest również zapisywane, jeśli x jest niezerowe y / x = a .

Linia ta ogranicza dwie półpłaszczyzny równania ( y < ax ) i ( y > ax ).

Jeśli P 0 nie znajduje się w wypukłej obwiedni, to wszystkie punkty znajdują się w tej samej półpłaszczyźnie, tj. Wszystkie punkty muszą znajdować się powyżej linii (ponieważ co najmniej jeden punkt, P 1 , wschód). Musimy zatem mieć dla wszystkich i

y i > ax i

jest

jeśli x i > 0, to y i / x i > a ;
jeśli x i <0, to y i / x i < a .

Mamy zatem konieczny i wystarczający warunek, aby istniał a, tj. Aby P 0 znajdował się poza wypukłą obwiednią:

{\ displaystyle \ left \ {{\ początek {wyrównane} \ max \ {y_ {i} / x_ {i} \ mid x_ {i} <0 \} i <\ min \ {y_ {i} / x_ {i } \ mid x_ {i}> 0 \} \\ y_ {i}> 0 & {\ text {si}} x_ {i} = 0. \ end {aligned}} \ right.}

Uwagi i odniesienia

Aviva Szpirglas , Algebra L3: Kompletny kurs z 400 testami i poprawionymi ćwiczeniami [ szczegóły wydania ] Definicja 4.28
(w) DP Dobkin i SP Reiss , " Złożoność programowania liniowego " , teoretyczna Computer Science , n o 11,1980
(en) Nimrod Megiddo , „ Algorytmy czasu liniowego dla programowania liniowego w problemach pokrewnych $\ mathbb {R} ^ {3}$ ” , SIAM Journal on Computing , vol. 4,1983, s. 766-769 ( DOI 10.1137 / 0212052 , Recenzje matematyczne 721011 , czytaj online )

Powiązany artykuł

Obliczanie wypukłej koperty