Plic convex

Stânga: setul albastru nu este convex, setul albastru este plicul său convex. Dreapta: ansamblul verde este convex, deci învelișul său convex este el însuși.

În matematică se numește plic convex (sau uneori plic convex ) al oricărui subset $THE$ ${\ displaystyle I}$ $THE$ a unui spațiu vectorial real , intersecția tuturor seturilor convexe pe care le conțin $THE$ ${\ displaystyle I}$ $THE$ .

Deoarece intersecția seturilor convexe este ea însăși convexă, o definiție alternativă a unui plic convex este „ cel mai mic set convex care conține $THE$ ${\ displaystyle I}$ $THE$ ".

Intuitiv, învelișul convex al unui set de puncte este forma pe care o elastică a extins-o pentru a conține toate punctele și apoi lăsată liberă să se micșoreze: un poligon care are unele dintre aceste puncte ca vârfuri și le conține pe toate.

Plicul convex poate fi construit ca ansamblul tuturor combinațiilor convexe de puncte ale $THE$ ${\ displaystyle I}$ $THE$ , adică toate punctele de tip $\sum _{j=1}^{n}\lambda _{j}x_{j}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} \ lambda _ {j} x_ {j}}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} \ lambda _ {j} x_ {j}}$ , unde $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ sunt puncte de $THE$ ${\ displaystyle I}$ $THE$ Și $\lambda _{j}$ ${\ displaystyle \ lambda _ {j}}$ $\ lambda _ {j}$ sunt numere reale non-negative cu suma 1, adică $\sum _{j=1}^{n}\lambda _{j}=1$ ${\ displaystyle \ sum _ {j = 1} ^ {n} \ lambda _ {j} = 1}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} \ lambda _ {j} = 1}$ .

Evident, dacă $THE$ ${\ displaystyle I}$ $THE$ este convex, învelișul său convex este $THE$ ${\ displaystyle I}$ $THE$ la fel.

Unirea plicurilor convexe

Având două seturi $THE, J$ ${\ displaystyle I, J}$ ${\ displaystyle I, J}$ , dacă sunăm respectiv $C_{I},C_{J},C_{I\cup J}$ ${\ displaystyle C_ {I}, C_ {J}, C_ {I \ cup J}}$ ${\ displaystyle C_ {I}, C_ {J}, C_ {I \ cup J}}$ plicurile convexe ale $I,J,I\cup J$ ${\ displaystyle I, J, I \ cup J}$ ${\ displaystyle I, J, I \ cup J}$ , următoarea relație este adevărată: $C_{I}\cup C_{J}\subset C_{I\cup J}$ ${\ displaystyle C_ {I} \ cup C_ {J} \ subset C_ {I \ cup J}}$ ${\ displaystyle C_ {I} \ cup C_ {J} \ subset C_ {I \ cup J}}$ .

De fapt, am spus că dacă un set convex conține $THE$ ${\ displaystyle I}$ $THE$ , apoi conține și $C_{I}$ ${\ displaystyle C_ {I}}$ ${\ displaystyle C_ {I}}$ , și dacă conține $J$ ${\ displaystyle J}$ $J$ conține și $C_{J}$ ${\ displaystyle C_ {J}}$ $C_ {J}$ . De cand $C_{I\cup J}$ ${\ displaystyle C_ {I \ cup J}}$ ${\ displaystyle C_ {I \ cup J}}$ este convex și conține ambele $THE$ ${\ displaystyle I}$ $THE$ acea $J$ ${\ displaystyle J}$ $J$ (deoarece conține $I\cup J$ ${\ displaystyle I \ cup J}$ ${\ displaystyle I \ cup J}$ ), va conține ambele $C_{I}$ ${\ displaystyle C_ {I}}$ ${\ displaystyle C_ {I}}$ acea $C_{J}$ ${\ displaystyle C_ {J}}$ $C_ {J}$ (și, prin urmare, desigur, $C_{I}\cup C_{J}$ ${\ displaystyle C_ {I} \ cup C_ {J}}$ ${\ displaystyle C_ {I} \ cup C_ {J}}$ ).

În general, inversul nu este adevărat și este un contraexemplu foarte simplu $THE$ ${\ displaystyle I}$ $THE$ Și $J$ ${\ displaystyle J}$ $J$ sunt două puncte distincte în plan . Se observă cu ușurință că un punct este prin definiție convex și, prin urmare, învelișurile lor sunt convexe $THE$ ${\ displaystyle I}$ $THE$ Și $J$ ${\ displaystyle J}$ $J$ înșiși. Dar plicul convex al $I\cup J$ ${\ displaystyle I \ cup J}$ ${\ displaystyle I \ cup J}$ va fi un segment, adică va conține strict $I\cup J=C_{I}\cup C_{J}$ ${\ displaystyle I \ cup J = C_ {I} \ cup C_ {J}}$ ${\ displaystyle I \ cup J = C_ {I} \ cup C_ {J}}$ .

O abordare de calcul

O problemă de calcul interesantă este, având în vedere un set finit ^[1] de puncte $I={p_{1}\cdots p_{n}}$ ${\ displaystyle I = {p_ {1} \ cdots p_ {n}}}$ ${\ displaystyle I = {p_ {1} \ cdots p_ {n}}}$ în plan , găsiți $C_{I}$ ${\ displaystyle C_ {I}}$ ${\ displaystyle C_ {I}}$ , plicul convex al $THE$ ${\ displaystyle I}$ $THE$ . S-au găsit diferiți algoritmi care rezolvă această problemă.

Unul dintre cele mai faimoase este așa-numitul Graham Scan : să căutăm punctul cel mai de jos (în caz de egalitate, cel mai îndepărtat în stânga celui mai jos) și să-l numim $q_{1}$ ${\ displaystyle q_ {1}}$ $q_ {1}$ ; sunt acum $q_{2}\cdots q_{n}$ ${\ displaystyle q_ {2} \ cdots q_ {n}}$ ${\ displaystyle q_ {2} \ cdots q_ {n}}$ punctele rămase, ordonate în așa fel încât $i>j\Leftrightarrow \theta _{i}>\theta _{j}$ ${\ displaystyle i> j \ Leftrightarrow \ theta _ {i}> \ theta _ {j}}$ ${\ displaystyle i> j \ Leftrightarrow \ theta _ {i}> \ theta _ {j}}$ , unde este $(\rho _{i},\theta _{i})$ ${\ displaystyle (\ rho _ {i}, \ theta _ {i})}$ ${\ displaystyle (\ rho _ {i}, \ theta _ {i})}$ sunt coordonatele polare ale $q_{i}$ ${\ displaystyle q_ {i}}$ $q_ {i}$ . În acest moment, să trecem prin puncte $q_{i}$ ${\ displaystyle q_ {i}}$ $q_ {i}$ : ori de câte ori intră $q_{i}$ ${\ displaystyle q_ {i}}$ $q_ {i}$ există un „viraj la stânga”, dar nu în $q_{i-1}$ ${\ displaystyle q_ {i-1}}$ ${\ displaystyle q_ {i-1}}$ , noi stim aia $q_{i}$ ${\ displaystyle q_ {i}}$ $q_ {i}$ este un vârf al plicului convex; de fiecare dată în loc în $q_{j}$ ${\ displaystyle q_ {j}}$ $q_ {j}$ există un „viraj la dreapta”, știm că acest punct nu este un vârf al plicului convex. Acest algoritm are un cost $O(n\,\log(n))$ ${\ displaystyle O (n \, \ log (n))}$ ${\ displaystyle O (n \, \ log (n))}$ .

Un algoritm eficient pentru aceeași problemă se bazează pe recursivitate, exploatând cazul de bază în care $n=2$ ${\ displaystyle n = 2}$ $n = 2$ (iar anvelopa convexă a două puncte este în mod evident segmentul care le unește) și crearea anvelopei convexe a două seturi convexe pe baza unor reguli simple (pas recursiv).

Observații

Plicul convex este un concept util de exemplu în problemele de relaxare .

Notă

^ În realitate, ne putem imagina foarte bine că datele de intrare sunt zona închisă de unul sau mai multe segmente închise. În acest caz $p_{1}\cdots p_{n}$ ${\ displaystyle p_ {1} \ cdots p_ {n}}$ ${\ displaystyle p_ {1} \ cdots p_ {n}}$ acestea sunt în mod evident vârfurile liniei (lor) întrerupte.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] În realitate, ne putem imagina foarte bine că datele de intrare sunt zona închisă de unul sau mai multe segmente închise. În acest caz $p_{1}\cdots p_{n}$ ${\ displaystyle p_ {1} \ cdots p_ {n}}$ ${\ displaystyle p_ {1} \ cdots p_ {n}}$ acestea sunt în mod evident vârfurile liniei (lor) întrerupte.

[1]