Anvelopă convexă

De la Wikipedia, enciclopedia liberă
Anvelopa convexă a mulțimii roșii este mulțimea convexă albastră și roșie.

În geometrie anvelopa convexă sau închiderea convexă a unei forme este cea mai mică mulțime convexă care o cuprinde. Anvelopa convexă poate fi definită fie ca intersecția tuturor mulțimilor convexe care conțin o submulțime dată a spațiului euclidian, fie ca mulțimea tuturor combinațiilor convexe⁠(d) ale punctelor din submulțimea dată. Pentru o porțiune dintr-un plan, anvelopa convexă poate fi vizualizată printr-un fir de cauciuc întins în jurul porțiunii.

Anvelopa convexă a unei mulțimi deschise este una deschisă, iar anvelopa convexă a unei mulțimi compacte este una compactă. Orice mulțime convexă compactă este anvelopa convexă a punctelor sale extreme⁠(d). Operatorul „anvelopă convexă” este un exemplu de operator de închidere⁠(d), iar orice antimatroid⁠(d) poate fi reprezentat prin aplicarea acestui operator de închidere la o mulțime finită de puncte. Problema algoritmilor de trasare a anvelopei convexe a unei mulțimi finite de puncte din plan sau alte spații euclidiene cu dimensiuni inferioare, precum și problema duală a intersectării semispațiilor, sunt probleme fundamentale ale geometriei algoritmice⁠(d). Pentru mulțimi situate în plan sau în spațiul tridimensional, acestea pot fi rezolvate cu resurse de calcul de complexitatea , iar pentru dimensiuni superioare, în cel mai rău caz cu resurse de calcul de complexitatea dată de teorema limitei superioare⁠(d).

La fel ca pentru mulțimi de puncte, anvelopa convexă a fost studiată pentru poligoane simple, mișcare browniană, curbe în spațiu și epigrafele funcțiilor⁠(d). Anvelopa convexă are aplicații în matematică, statistică, optimizare combinatorie, economie, modelare geometrică și etologie. Structurile conexe includ anvelopa convexă ortogonală⁠(d), straturile convexe⁠(d), triangulația Delaunay și pavarea Voronoi⁠(d).

Definiții[modificare | modificare sursă]

Anvelopa convexă a unei mulțimi mărginite din plan: analogia firului de cauciuc

O mulțime de puncte din spațiul euclidian este definită drept convexă dacă aceasta conține toate segmentele care unesc oricare pereche de puncte ale sale. Anvelopa convexă a unei mulțimi date poate fi definită prin:[1]

  1. Mulțimea convexă minima (unică) conținând
  2. Intersecția tuturor mulțimilor convexe conținând
  3. Mulțimea tuturor combinațiilor convexe de puncte din
  4. Reuniunea tuturor simplexurilor cu vârfuri în

Pentru o mulțime cu frontieră din planul euclidian, cu elemente necoliniare, frontiera anvelopei convexe este linia închisă cu perimetrul minim conținând pe . Se poate imagina întinderea unui fir de cauciuc în jurul întregii mulțimi , iar apoi, eliberându-l, el se strânge; când se oprește, el închide anvelopa convexă a .[2] Această formulare nu se poate generaliza imediat pentru dimensiuni superioare: pentru o mulțime finită de puncte din spațiul tridimensional, o vecinătate a arborelui de acoperire⁠(d) al punctelor le include cu o suprafață arbitrar de mică, mai mică decât suprafața anvelopei convexe.[3] Cu toate acestea, în dimensiuni superioare, variante ale problemei obstacolelor⁠(d) de a găsi o suprafață cu energie minimă pe deasupra unei forme date pot avea drept soluție anvelopa convexă.[4]

Pentru obiectele tridimensionale, prima definiție afirmă că anvelopa convexă este cel mai mic posibil volum de delimitare⁠(d) convex al obiectelor. Definiția pe baza intersecției mulțimilor convexe poate fi extinsă la geometriile neeuclidiene, iar definiția pe baza combinațiilor convexe poate fi extinsă la un spațiu vectorial real sau la un spațiu afin oarecare; anvelopa convexă poate fi generalizată abstract în cadrul matroizilor orientați⁠(d).[5]

Echivalența definițiilor[modificare | modificare sursă]

Anvelopa convexă tridimensională a unei mulțimi grupate de 120 de puncte

Nu este evident că prima definiție are sens: de ce trebuie ca mulțimea convexă care cuprinde să fie minimă și de ce este ea unică? Definiția a doua, intersecția tuturor mulțimilor convexe care conțin , este bine definită. Ea este o submulțime a oricărei alte mulțimi convexe care conțin , deoarece este inclusă în mulțimile care se intersectează. Ca urmare, ea este exact unica mulțime convexă minimă care conține . Prin urmare, primele două definiții sunt echivalente.[1]

Fiecare mulțime convexă care conține trebuie (presupunând că este convexă) să conțină toate combinațiile convexe de puncte din , astfel toate combinațiile convexe sunt conținute în intersecția tuturor mulțimilor convexe care conțin . Invers, mulțimea tuturor combinațiilor convexe este ea însăși o mulțime convexă care conține , deci conține și intersecția tuturor mulțimilor convexe care conțin , prin urmare a doua și a treia definiție sunt echivalente.[6]

În fapt, conform teoremei Carathéodory⁠(d), dacă este o submulțime a spațiului euclidian -dimensional, orice combinație convexă a unui număr finit de puncte din este și o combinație convexă în a punctelor din . Mulțimea combinațiilor convexe ale unui -tuplu⁠(en) de puncte este un simplex; în plan el este un triunghi, iar în spațiul tridimensional este un tetraedru. Prin urmare, orice combinație convexă de puncte din aparține unui simplex, ale cărui vârfuri aparțin lui , iar a treia și a patra definiție sunt echivalente.[6]

Anvelopele de sus și de jos[modificare | modificare sursă]

Pentru calcule, uneori anvelopa convexă este împărțită în două părți. În două dimensiuni, anvelopa convexă este uneori împărțită în două părți, în anvelopa „de sus” și cea „de jos” („sus” și „jos” în sensul foii de hârtie pe care este desenată), întinzându-se între punctele cel mai „din stânga” și cel mai „din dreapta” (tot în sensul foii de hârtie) ale figurii. Mai general, pentru corpurile convexe în orice dimensiune se poate împărți corpul în zone orientate „în sus”, respectiv „în jos” (în sensul cum este privit un corp în mod obișnuit), figura de separație fiind definită de punctele care apar ca extreme în proiecția ortogonală în direcția verticală. Pentru corpurile tridimensionale, părțile orientate în sus și în jos ale frontierei formează discuri topologice.[7] Ideea de partiționare a corpului în două zone provine dintr-o variantă eficientă a algoritmului Graham⁠(d).[8]

Proprietăți topologice[modificare | modificare sursă]

Anvelope închise și deschise[modificare | modificare sursă]

Anvelopa convexă închisă este închiderea⁠(d) anvelopei convexe, iar anvelopa convexă deschisă este interiorul anvelopei convexe.[9]

Anvelopa convexă închisă a este intersecția tuturor semispațiilor care conțin . Dacă anvelopa convexă a este deja ea însăși o mulțime închisă (asta se întâmplă, de exemplu, dacă este o mulțime finită sau, mai general, o mulțime compactă), atunci ea este anvelopa convexă închisă. Totuși, o intersecție de spații închise este în sine închisă, așa că atunci când o anvelopă convexă nu este închisă nu poate fi reprezentată în acest fel.[10]

Dacă anvelopa convexă deschisă a mulțimii este -dimensională, atunci orice punct al anvelopei aparține unei anvelope convexe deschise a cel mult puncte ale . Mulțimile vârfurilor unui pătrat, al unui octaedru regulat sau al unui ortoplex sunt exemple în care sunt necesare exact puncte.[11]

Conservarea proprietăților topologice[modificare | modificare sursă]

Vrăjitoarea lui Agnesi. Punctele de pe, sau de deasupra curbei roșii sunt un exemplu de mulțime închisă, la care anvelopa convexă este deschisă (vezi semiplanul de deasupra curbei).

Topologic, anvelopa convexă a unei mulțimi deschise este ea însăși una deschisă, iar anvelopa convexă a unei mulțimi compacte ea însăși compactă. Totuși, există mulțimi închise ale căror anvelope convexe nu sunt închise.[12] De exemplu, mulțimea închisă

(mulțimea punctelor aflate deasupra curbei vrăjitoarea lui Agnesi⁠(d) are semiplanul de deasupra curbei drept anvelopă convexă, deschisă.[13]

Compactitatea anvelopelor convexe ale mulțimilor compacte din spațiile euclidiene, finite dimensional, este generalizată de teorema Krein–Šmulian⁠(d), conform căreia anvelopa convexă închisă a unei submulțimi slab compacte dintr-un spațiu Banach (o submulțime compactă în sensul topologiei slabe⁠(d)) este slab compactă.[14]

Puncte extreme[modificare | modificare sursă]

Un punct extrem al unei mulțimi convexe este un punct din mulțime care nu se află pe niciun segment de linie deschisă între oricare alte două puncte ale aceleiași mulțimi. Pentru o anvelopă convexă fiecare punct extrem trebuie să facă parte din mulțimea dată, pentru că altfel nu poate fi format ca o combinație convexă din punctele date. Conform teoremei Kerin – Milman⁠(d), orice mulțime convexă compactă dintr-un spațiu euclidian (sau mai general într-un spațiu vectorial topologic convex local⁠(d)) este anvelopa convexă a punctelor sale extreme. Totuși, acest lucru poate să nu fie adevărat pentru mulțimile convexe care nu sunt compacte; de exemplu, întregul plan euclidian și bila unitate deschisă sunt ambele convexe, dar niciunul dintre ele nu are puncte extreme. Teoria Choquet⁠(d) extinde această teorie de la combinații de puncte extreme convexe finite, la combinații infinite (integrale) în spații mai generale.[15]

Proprietăți geometrice și algebrice[modificare | modificare sursă]

Operator de închidere[modificare | modificare sursă]

Operatorul anvelopă convexă are proprietăți caracteristice unui operator de închidere:[16]

  • Este extensiv, în sensul că anvelopa convexă a oricărei mulțimi este o mulțime care include mulțimea (este o supramulțime a mulțimii ).
  • Este nedecrescător, în sensul că pentru oricare două mulțimi și cu anvelopa convexă a este o submulțime a anvelopei convexe a .
  • Este idempotent⁠(d), în sensul că pentru oricare mulțime anvelopa convexă a anvelopei convexe a este identică cu anvelopa convexă a .

Atunci când este aplicat unei mulțimi finite de puncte, acesta este operatorul de închidere al unui antimatroid⁠(d), antimatroidul interiorului mulțimii de puncte. Astfel fiecare antimatroid poate fi reprezentat prin corpuri convexe de puncte într-un spațiu euclidian de dimensiuni suficient de mari.[17]

Suma Minkowski[modificare | modificare sursă]

Operațiile de construire a anvelopei convexe și a sumei Minkowski⁠(d) sunt echivalente, în sensul că suma Minkowski a anvelopelor convexe ale mulțimilor dă același rezultat ca și anvelopa convexă a sumei Minkowski a acelorași mulțimi. Aceasta duce la lema Shapley–Folkman⁠(d), care limitează distanța unei sume Minkowski de anvelopa sa convexă.[18]

Dualitate proiectivă[modificare | modificare sursă]

Operația de construire a anvelopei convexe a unui set de puncte este una dual proiectivă⁠(d). Adică la construirea intersecției închise a unei familii de semispații, din fiecare pereche duală de semispații care formează spațiul se ia semispațiul care conține originea (sau un alt punct desemnat),[19] nu semispațiul său complementar.

Cazuri speciale[modificare | modificare sursă]

Mulțimi finite de puncte[modificare | modificare sursă]

Anvelopa convexă a unor puncte din plan

Anvelopa convexă a unei mulțimi finite de puncte formează în plan un poligon convex, sau, mai general, un politop convex în . Fiecare punct extrem al anvelopei este numit vârf, iar (conform teoremei Krein–Milman⁠(d)) orice politop convex este anvelopa convexă a vârfurilor sale. El este unicul politop convex ale cărui vârfuri aparțin la și include toată .[2] Pentru mulțimi de puncte aflate în poziții oarecare, anvelopa convexă este un simplex.[20]

Conform teoremei limitei superioare, numărul de fețe al anvelopei convexe a puncte în spațiul euclidian -dimensional este .[21] În particular, în două sau trei dimensiuni numărul fețelor este cel mult liniar în .[22]

Poligoane simple[modificare | modificare sursă]

Anvelopa convexă a unui poligon simplu

Anvelopa convexă a unui poligon simplu include poligonul dat și este împărțită în regiuni, una din ele fiind poligonul însuși (albastru în figura alăturată). Alte regiuni, delimitate de lanțul poligonal (frontiera) poligonului și de anvelopa convexă, se numesc buzunare. Calculând aceeași descompunere recursiv pentru fiecare buzunar se formează o descriere ierarhică a poligonului dat, numită arborele diferențelor convexe.[23] Reflectarea unui buzunar peste marginea acestuia de pe anvelopa convexă extinde poligonul simplu dat într-un poligon cu același perimetru și suprafață mai mare, iar teorema Erdős–Nagy⁠(d) afirmă că acest proces de expansiune se termină în cele din urmă.[24]

Mișcarea browniană[modificare | modificare sursă]

Curba generată de mișcarea browniană în plan, în orice moment fix, are probabilitatea 1 de a avea o anvelopă convexă a cărei limită formează o curbă continuă diferențiabilă. Totuși, pentru orice unghi din intervalul vor exista momente în timpul mișcării browniene în care particula în mișcare atinge limita corpului convex în vârful unui unghi. Dimensiunea Hausdorff a acestei mulțimi de excepții este (cu probabilitate mare) .[25]

Curbe în spațiu[modificare | modificare sursă]

Un oloid, anvelopa convexă a două cercuri în spațiul tridimensional

În cazul anvelopei convexe a unei curbe din spațiu sau a unei mulțimi finite de curbe din spațiu aflate în poziții oarecare în spațiul tridimensional, părțile frontierei departe de curbe sunt suprafețe desfășurabile și riglate⁠(d).[26] Un exemplu este oloidul, care este anvelopa convexă a două cercuri din plane perpendiculare, fiecare trecând prin centrul celuilalt.[27] Alt exemplu este sfericonul, anvelopa convexă a două semicercuri în plane perpendiculare având aceeași rază și același centru. Forma acestor anvelope convexe rezultă din teorema unicității a lui Alexandrov⁠(d) și sunt suprafețe obținute prin lipirea a două mulțimi convexe plane (zonele de contact ale celor două componente) cu același perimetru.[28]

Funcții[modificare | modificare sursă]

Anvelopa convexă a unei funcții pe un spațiu vectorial real este funcția al cărei epigraf este anvelopa convexă de jos a epigrafului său. Este o funcție convexa maximă unică majorată de .[29] Definiția poate fi extinsă la anvelopa convexă a unui set de funcții (obținută din anvelopa convexă a reuniunii epigrafelor lor sau echivalent din minimul lor punctual) și, în această formă, este duală față de operația conjugata convexă⁠(d).[30]

Calcul[modificare | modificare sursă]

În geometria algoritmică se cunosc o seamă de algoritmi pentru calculul anvelopei convexe a unei mulțimi finite de puncte și pentru alte obiecte geometrice. Calculul anvelopei convexe înseamnă construirea eficientă și neambiguă a reprezentării formei convexe cerute. Rezultatul constă într-o listă de inegalități liniare care descriu fațetele anvelopei, un graf al fațetelor și cu care se învecinează, sau laticea fețelor anvelopei.[31] În două dimensiuni este suficientă lista punctelor care sunt vârfuri în ordinea ciclică în jurul anvelopei.[2]

Pentru anvelopa convexă în două sau trei dimensiuni, complexitatea algoritmilor este dată de numărul de puncte date inițial și numărul de puncte de pe anvelopa convexă , care poate fi semnificativ mai mic ca . Pentru anvelope în mai multe dimensiuni, numărul fețelor din alte dimensiuni poate și el conta. Algoritmul Graham poate calcula anvelopa convexă a puncte în plan în timp de ordinul . Pentru puncte în două sau trei dimensiuni se cunosc algoritmi mai complicați, cu performanțe în funcție de numărul de puncte ale soluției, algoritmi care calculează anvelopa convexă în timp de ordinul . Astfel de algoritmi sunt algoritmul Chan și algoritmul Kirkpatrick–Seidel.[32] Pentru dimensiuni , timpul de calcul al anvelopei convexe este de ordinul , în funcție de situația cea mai proastă din problemă.[33] Anvelopa convexă a unui poligon simplu din plan poate fi construită în timp de ordin liniar.[34]

Pentru a urmări o mulțime de puncte care se modifică prin adăugări sau eliminări de puncte se poate folosi o structură de date de tip anvelopă convexă dinamică⁠(d),[35] iar pentru puncte care se mișcă continuu, o structură de date de tip anvelopă convexă cinetică⁠(d).[36]. Construcția anvelopei convexe este un pas premergător în alți algoritmi, care calculează „lungimea” și „diametrul” mulțimii de puncte.[37]

Structuri conexe[modificare | modificare sursă]

Imagine indisponibilă Imagine indisponibilă
Anvelopă convexă ortogonală
Anvelopă convexă relativă

Și alte forme pot fi definite pentru o mulțime de puncte la fel cum este definită anvelopa convexă: prin supramulțimea minimă cu o anume proprietate, prin intersecția tuturor formelor care conțin punctele, sau prin reuniunea tuturor combinațiilor de puncte de un anumit tip. Exemple:

  • Anvelopa afină⁠(d) este cel mai mic subspațiu afin al spațiului euclidian conținând mulțimea dată, sau reuniunea tuturor combinațiilor de puncte din mulțime.[38]
  • Spațiul vectorial generat⁠(d) este cel mai mic subspațiu liniar al spațiului vectorial care conține mulțimea dată, sau reuniunea tuturor combinațiilor de puncte din mulțime.[38]
  • Anvelopa conică⁠(d) sau anvelopa pozitivă a unei submulțimi a spațiului vectorial este mulțimea tuturor combinațiilor pozitive de puncte din submulțime.[38]
  • Anvelopa vizuală⁠(d) a unui obiect tridimensional, în funcție de câteva puncte de vedere, constă din punctele astfel încât toate razele care pleacă dintr-un punct de vedere și trec printr-un punct intersectează obiectul. Echivalent este intersecția conurilor neconvexe generate contururile obiectului obținute din punctele respective de vedere. Este folosită la reconstrucțiile 3D⁠(d) drept cea mai mare formă care produce aceleași contururi văzute din punctele de vedere date.[39]
  • Anvelopa cercuală, sau anvelopa alfa a unei submulțimi din plan este intersecția tuturor discurilor cu o rază dată care conțin submulțimea.[40]
  • Anvelopa convexă relativă⁠(d) a unei submulțimi a unui poligon simplu bidimensional este intersecția tuturor supramulțimilor, unde o mulțime din interiorul aceluiași poligon este relativ convexă dacă conține geodezicele dintre oricare două dintre punctele sale.[41]
  • Anvelopa convexă ortogonală, sau anvelopa convexă rectilinie, este intersecția tuturor supramulțimilor ortogonal convexe și a supramulțimilor conectate, în care o mulțime este ortogonal convexă dacă conține toate segmentele dintre perechile de puncte, orientate paralel cu axele.[42]
  • Anvelopa convexă ortogonală este un caz particular a unei construcții mai generale, anvelopa injectivă⁠(d), care poate fi considerată ca fiind cel mai mic spațiu metric injectiv⁠(d) care conține punctele date din spațiul metric dat.[43]
  • Anvelopa convexă olomorfă este o generalizare a conceptelor similare cu varietățile analitice complexe⁠(d), obținută ca intersecție a mulțimilor de funcții olomorfe care conțin mulțimea dată.[44]

Triangulația Delaunay a unei mulțimi de puncte și a dualului său, diagrama Voronoi⁠(d), sunt matematic conexe cu anvelopa convexă: triangulația Delaunay a unei mulțimi de puncte din poate fi văzută ca proiecția anvelopei convexe în [45] Forma alfa⁠(d) a unei mulțimi finite de puncte dă o familie înglobată de obiecte geometrice (neconvexe), care, descriu anvelopa unei mulțimi de puncte la diferite niveluri de detaliu. Orice anvelopă alfa este reuniunea unor elemente ale triangulației Delaunay, alese prin compararea razelor cercului circumscris cu parametrul alfa. Mulțimea de puncte însăși este punctul final al acestei familii de anvelope, iar anvelopa sa convexă formează celălalt punct final.[40] Straturile convexe⁠(d) ale unei mulțimi de puncte sunt o familie de poligoane convexe, cel din exterior fiind anvelopa convexă cu straturile interioare construite recursiv, din puncte care nu sunt vârfuri ale anvelopei convexe.[46]

Aplicații[modificare | modificare sursă]

Anvelopa convexă are aplicații în diferite domenii (vezi mai jos). Astfel, în matematică, anvelopa convexă este folosită pentru a studia polinoamele, vectorii și valorile proprii ale matricilor, și mai multe teoreme din geometria discretă implică anvelopa convexă. Acestea sunt utilizate în statistici robuste drept conturul exterior al adâncimii Tukey⁠(d), se folosesc la vizualizarea datelor bidimensionale și definesc seturi de risc în luarea deciziilor. Anvelopa convexă a vectorilor indicatori ai soluțiilor în problemele combinatorice este miezul optimizării combinatorii⁠(d) și în combinatorica poliedrică⁠(d). În economie, anvelopa convexă poate fi utilizată pentru a aplica metode de convexitate pe piețele neconvexe. În modelarea geometrică, curbele Bézier ajută la netezirea anvelopei convexe, de exemplu la măsurarea carenelor bărcilor. Și în studiul comportamentului animalelor anvelopa convexă este utilizată într-o definiție standard a spațiului vital.

Matematică[modificare | modificare sursă]

Împărțirea a șapte puncte în trei sumulțimi (cele colorate diferit) cu intersecția anvelopelor lor convexe, garantat să existe pentru oricare șapte puncte din plan de teorema Tverberg.

Poligoanele Newton⁠(d) ale polinoamelor de o singură variabilă și politopurile Newton⁠(d) ale polinoamelor multivariabilă sunt anvelope convexe ale punctelor derivate din exponenții termenilor din polinom și pot fi folosite pentru a analiza comportamentul asimptotic al polinomului și evaluările rădăcinilor sale.[47] Anvelopa convexă și polinoamele se întâlnesc, de asemenea, în teorema Gauss–Lucas⁠(d), conform căreia rădăcinile derivatei unui polinom se află toate în anvelopa convexă a rădăcinilor polinomului.[48]

În analiza spectrală⁠(d), intervalul numeric al unei matrice normale este anvelopa convexă a valorilor proprii ale acesteia.[49] Teorema Russo–Dye⁠(d) descrie anvelopa convexă a elementelor unitare într-o C*-algebră⁠(d).[50] În geometria discretă, atât teorema Radon⁠(d), cât și teorema Tverberg⁠(d) se referă la existența împărțirii mulțimilor de vârfuri în subseturi cu anvelope convexe care se intersectează.[51]

Definițiile unei mulțimi convexe ca find segmentele dintre punctele sale, astfel încât acestea să fie conținute în interior și a unei anvelope convexe ca intersecție a tuturor supramulțimilor convexe, se aplică atât spațiilor hiperbolice, cât și spațiilor euclidiene. În spațiul hiperbolic este, totuși, posibil să se ia în considerare anvelopele convexe ale mulțimilor de puncte ideale, puncte care nu aparțin spațiului hiperbolic în sine, dar se află la limita unui model al spațiului respectiv. Limitele anvelopelor convexe ale punctelor ideale ale spațiului hiperbolic tridimensional sunt analoage suprafețelor riglate din spațiul euclidian, iar proprietățile lor metrice joacă un rol important în conjectura de geometrizare⁠(d) în topologia bi- și tridimensională.[52] Anvelopele convexe hiperbolice au fost, de asemenea, utilizate ca parte a calculului triangulațiilor canonice ale varietăților hiperbolice și aplicate pentru a determina echivalența nodurilor.[53]

Vezi și secțiunea mișcarea browniană, pentru aplicațiile anvelopei convexe în acest domeniu și secțiunea curbe în spațiu, pentru aplicațiile în teoria suprafețelor desfășurabile.

Statistică[modificare | modificare sursă]

O corelație. Regiunea umbrită exterioară este anvelopa convexă, iar cea umbrită mai intens din interior este conturul adâncimii Tukey de 50%.

În statistica robustă, anvelopa convexă furnizează o componentă cheie a graficelor de corelație, o metodă pentru vizualizarea împrăștierii unui eșantion bidimensional de puncte. Contururile adâncimilor Tukey formează o familie de mulțimi convexe, având anvelopa convexă spre exterior.[54]

În teoria deciziei⁠(d) pe baze statistice, mulțimea riscurilor deciziilor aleatorii este anvelopa convexă a punctelor de risc din regulile de decizie deterministe, reguli care stau la baza acestor decizii.[55]

Optimizare combinatorie[modificare | modificare sursă]

În optimizarea combinatorie și combinatorica poliedrică, anvelopa convexă a vectorilor indicatori ai soluțiilor unei probleme combinatorice este obiectul de studiu principal. Dacă pot fi găsite fațetele acetor politopuri, descriind politopurile și intersecțiile semispațiilor, atunci pentru soluțiile optime se pot folosi algoritmii din programarea liniară.[56] În optimizarea multiobiectiv⁠(d) se folosește și alt tip de anvelopă convexă, anvelopa convexă a vectorilor ponderați ai soluțiilor. Asta poate maximiza combinația aproape convexă a ponderilor, pe baza examinării vârfurilor anvelopei convexe, în loc de a verifica toate soluțiile posibile.[57]

Economie[modificare | modificare sursă]

În modelul Arrow–Debreu⁠(d) al echilibrului economic general, se presupune că agenții economici au bugetul stabilit și preferințe convexe⁠(d). Aceste presupuneri ale convexității în economie pot fi folosite pentru a demonstra existența unui echilibru. Dacă datele economice nu sunt convexe, se poate folosi în loc anvelopa lor convexă. Teorema Shapley–Folkman arată că pentru piețe mari această aproximare este bună și duce la un „cvasiechilibru” al pieței neconvexe.[58]

Modelare geometrică[modificare | modificare sursă]

În modelarea geometrică⁠(d), una din proprietățile esențiale ale curbelor Bézier este că trec prin punctele de control ale anvelopei convexe. De aceea, anvelopa convexă este folosită la detectarea rapidă a punctelor de intersecție ale acestor curbe.[59]

În proiectarea navelor, pentru a verifica dacă acestea corespund poligonului secțiunilor din proiect se folosește măsurarea anvelopei convexe a secțiunilor transversale ale carenei, metodă bună și în cazul carenelor care au părți concave.[60]

Etologie[modificare | modificare sursă]

Anvelopa convexă este cunoscută în etologie ca poligonul convex minim în studiul comportamentului animalului. Este o abordare clasică, deși poate simplistă, în estimarea spațiului vital al unui animal, pe baza punctelor în care animalul a fost observat.[61] Excepțiile pot face ca poligonul convex minim să fie excesiv de mare, ceea ce a motivat abordări relaxate. Acestea conțin doar un subset de observații, de exemplu, alegând unul dintre straturile convexe care este aproape de procentul țintă al eșantioanelor,[62] sau metoda poligonului convex local prin combinarea poligoanelor convexe conform algoritmului celor k cei mai apropiați vecini⁠(d).[63]

Fizică cuantică[modificare | modificare sursă]

În fizica cuantică, spațiul stărilor⁠(d) oricărui sistem cuantic — mulțimea stărilor cuantice în care se poate afla sistemul — este anvelopa convexă a punctelor extreme definite drept stări pure, iar interiorul ei drept stări mixte.[64] Teorema Gisin-Hughston-Jozsa-Wootters⁠(d) arată că orice stare mixtă poate fi exprimată în mai multe feluri, ca o combinație convexă de stări pure.[65]

Istoric[modificare | modificare sursă]

Anvelopa convexă de jos a punctelor din plan a apărut, sub forma unui poligon Newton, într-o scrisoare din 1676 a lui Isaac Newton către Henry Oldenburg.[66] Termenul de „anvelopă convexă” a apărut inițial, în 1922, în recenziile lui Hans Rademacher asupra lucrărilor lui Dénes Kőnig.[67] Conform lui Lloyd Dines, din 1938 termenul de „anvelopă convexă” a devenit standard. Dines a adăugat că după părerea lui expresia este nefericită, deoarece înțelesul comun pentru „anvelopă” sugerează că s-ar referi doar la suprafața formei, în timp ce în realitate se referă și la interiorul ei.[68]

Note[modificare | modificare sursă]

  1. ^ a b Rockafellar (1970), p. 12.
  2. ^ a b c de Berg et al. (2008), p. 3.
  3. ^ Williams & Rossignac (2005). Vezi și Douglas Zare, answer to "the perimeter of a non-convex set", MathOverflow, May 16, 2014.
  4. ^ Oberman (2007).
  5. ^ Knuth (1992).
  6. ^ a b Rockafellar (1970), p. 12; Lay (1982), p. 17.
  7. ^ de Berg et al. (2008), p. 6
  8. ^ Andrew (1979)
  9. ^ Sontag (1982).
  10. ^ Rockafellar (1970), p. 99.
  11. ^ Steinitz (1914); Gustin (1947); Bárány, Katchalski & Pach (1982)
  12. ^ Grünbaum (2003), p. 16; Lay (1982), p. 21; Sakuma (1977).
  13. ^ Exemplul provine din Talman (1977), Remark 2.6.
  14. ^ Whitley (1986).
  15. ^ Okon (2000).
  16. ^ Kiselman (2002).
  17. ^ Kashiwabara, Nakamura & Okamoto (2005).
  18. ^ Krein & Šmulian (1940), Theorem 3, pages 562–563; Schneider (1993), Theorem 1.1.2 (pages 2–3) and Chapter 3.
  19. ^ de Berg et al. (2008), p. 254.
  20. ^ Grünbaum (2003), p. 57.
  21. ^ de Berg et al. (2008), p. 256.
  22. ^ de Berg et al. (2008), p. 245.
  23. ^ Rappoport (1992).
  24. ^ Demaine et al. (2008).
  25. ^ Cranston, Hsu & March (1989).
  26. ^ Sedykh (1981).
  27. ^ Dirnböck & Stachel (1997).
  28. ^ Seaton (2017).
  29. ^ Rockafellar (1970), p. 36.
  30. ^ Rockafellar (1970), p. 149.
  31. ^ Avis, Bremner & Seidel (1997).
  32. ^ de Berg et al. (2008), p. 13.
  33. ^ Chazelle (1993); de Berg et al. (2008), p. 256.
  34. ^ McCallum & Avis (1979); Graham & Yao (1983); Lee (1983).
  35. ^ Chan (2012).
  36. ^ Basch, Guibas & Hershberger (1999).
  37. ^ Toussaint (1983).
  38. ^ a b c Westermann (1976).
  39. ^ Laurentini (1994).
  40. ^ a b Edelsbrunner, Kirkpatrick & Seidel (1983).
  41. ^ Toussaint (1986).
  42. ^ Ottmann, Soisalon-Soininen & Wood (1984).
  43. ^ Herrlich (1992).
  44. ^ Rossi (1961).
  45. ^ Brown (1979).
  46. ^ Chazelle (1985).
  47. ^ Artin (1967); Gel'fand, Kapranov & Zelevinsky (1994)
  48. ^ Prasolov (2004).
  49. ^ Johnson (1976).
  50. ^ Gardner (1984).
  51. ^ Reay (1979).
  52. ^ Epstein & Marden (1987).
  53. ^ Weeks (1993).
  54. ^ Rousseeuw, Ruts & Tukey (1999).
  55. ^ Harris (1971).
  56. ^ Pulleyblank (1983); v. în special afirmațiile care derivă din teorema 2.9.
  57. ^ Katoh (1992).
  58. ^ Nicola (2000). See in particular Section 16.9, Non Convexity and Approximate Equilibrium, pp. 209–210.
  59. ^ Chen & Wang (2003).
  60. ^ Mason (1908).
  61. ^ Kernohan, Gitzen & Millspaugh (2001), p. 137–140; Nilsen, Pedersen & Linnell (2008)
  62. ^ Worton (1995).
  63. ^ Getz & Wilmers (2004).
  64. ^ Rieffel & Polak (2011).
  65. ^ Kirkpatrick (2006).
  66. ^ Newton (1676); v. Auel (2019), p. 336, așiEscobar & Kaveh (2020).
  67. ^ White (1923), p. 520.
  68. ^ Dines (1938).

Bibliografie[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]