Anvelopă convexă

Î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 Format:Ill-wd 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 Format:Ill-wd. Operatorul „anvelopă convexă” este un exemplu de Format:Ill-wd, iar orice Format:Ill-wd 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 Format:Ill-wd. Pentru mulțimi situate în plan sau în spațiul tridimensional, acestea pot fi rezolvate cu resurse de calcul de complexitatea $O (n \log n)$ , iar pentru dimensiuni superioare, în cel mai rău caz cu resurse de calcul de complexitatea dată de Format:Ill-wd.

La fel ca pentru mulțimi de puncte, anvelopa convexă a fost studiată pentru poligoane simple, mișcare browniană, curbe în spațiu și Format:Ill-wd. Anvelopa convexă are aplicații în matematică, statistică, optimizare combinatorie, economie, modelare geometrică și etologie. Structurile conexe includ Format:Ill-wd, Format:Ill-wd, triangularea Delaunay și Format:Ill-wd.

Definiții

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 $X$ date poate fi definită prin:Format:Sfnp

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

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 $X$ . Se poate imagina întinderea unui fir de cauciuc în jurul întregii mulțimi $S$ , iar apoi, eliberându-l, el se strânge; când se oprește, el închide anvelopa convexă a $S$ .Format:Sfnp 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 Format:Ill-wd al punctelor le include cu o suprafață arbitrar de mică, mai mică decât suprafața anvelopei convexe.^[1] Cu toate acestea, în dimensiuni superioare, variante ale Format:Ill-wd de a găsi o suprafață cu energie minimă pe deasupra unei forme date pot avea drept soluție anvelopa convexă.Format:Sfnp

Pentru obiectele tridimensionale, prima definiție afirmă că anvelopa convexă este cel mai mic posibil Format:Ill-wd 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 Format:Ill-wd.Format:Sfnp

Echivalența definițiilor

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

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

În fapt, conform Format:Ill-wd, dacă $X$ este o submulțime a spațiului euclidian $d$ -dimensional, orice combinație convexă a unui număr finit de puncte din $X$ este și o combinație convexă în $d + 1$ a punctelor din $X$ . Mulțimea combinațiilor convexe ale unui $(d + 1)$ -Format:Ill 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 $X$ aparține unui simplex, ale cărui vârfuri aparțin lui $X$ , iar a treia și a patra definiție sunt echivalente.^[2]

Anvelopele de sus și de jos

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.^[3] Ideea de partiționare a corpului în două zone provine dintr-o variantă eficientă a algoritmului Graham.^[4]

Proprietăți topologice

Anvelope închise și deschise

Anvelopa convexă închisă este Format:Ill-wd anvelopei convexe, iar anvelopa convexă deschisă este interiorul anvelopei convexe.Format:Sfnp

Anvelopa convexă închisă a $X$ este intersecția tuturor semispațiilor care conțin $X$ . Dacă anvelopa convexă a $X$ este deja ea însăși o mulțime închisă (asta se întâmplă, de exemplu, dacă $X$ 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.Format:Sfnp

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

Conservarea proprietăților topologice

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.^[6] De exemplu, mulțimea închisă

{(x, y) | y \geq \frac{1}{1 + x^{2}}}

(mulțimea punctelor aflate deasupra curbei Format:Ill-wd are semiplanul de deasupra curbei drept anvelopă convexă, deschisă.^[7]

Compactitatea anvelopelor convexe ale mulțimilor compacte din spațiile euclidiene, finite dimensional, este generalizată de Format:Ill-wd, conform căreia anvelopa convexă închisă a unei submulțimi slab compacte dintr-un spațiu Banach (o submulțime compactă în sensul Format:Ill-wd) este slab compactă.Format:Sfnp

Puncte extreme

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 Format:Ill-wd, orice mulțime convexă compactă dintr-un spațiu euclidian (sau mai general într-un Format:Ill-wd) 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. Format:Ill-wd extinde această teorie de la combinații de puncte extreme convexe finite, la combinații infinite (integrale) în spații mai generale.Format:Sfnp

Proprietăți geometrice și algebrice

Operator de închidere

Operatorul anvelopă convexă are proprietăți caracteristice unui operator de închidere:Format:Sfnp

Este extensiv, în sensul că anvelopa convexă a oricărei mulțimi $X$ este o mulțime care include mulțimea $X$ (este o supramulțime a mulțimii $X$ ).
Este nedecrescător, în sensul că pentru oricare două mulțimi $X$ și $Y$ cu $X \subseteq Y$ anvelopa convexă a $X$ este o submulțime a anvelopei convexe a $Y$ .
Este Format:Ill-wd, în sensul că pentru oricare mulțime $X$ anvelopa convexă a anvelopei convexe a $X$ este identică cu anvelopa convexă a $X$ .

Atunci când este aplicat unei mulțimi finite de puncte, acesta este operatorul de închidere al unui Format:Ill-wd, 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.Format:Sfnp

Suma Minkowski

Operațiile de construire a anvelopei convexe și a Format:Ill-wd 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 Format:Ill-wd, care limitează distanța unei sume Minkowski de anvelopa sa convexă.^[8]

Dualitate proiectivă

Operația de construire a anvelopei convexe a unui set de puncte este una Format:Ill-wd. 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),Format:Sfnp nu semispațiul său complementar.

Cazuri speciale

Mulțimi finite de puncte

Anvelopa convexă a unei mulțimi finite de puncte $S \subset ℝ^{d}$ formează în plan un poligon convex, sau, mai general, un politop convex în $ℝ^{d}$ . Fiecare punct extrem al anvelopei este numit vârf, iar (conform Format:Ill-wd) orice politop convex este anvelopa convexă a vârfurilor sale. El este unicul politop convex ale cărui vârfuri aparțin la $S$ și include toată $S$ .Format:Sfnp Pentru mulțimi de puncte aflate în poziții oarecare, anvelopa convexă este un simplex.Format:Sfnp

Conform teoremei limitei superioare, numărul de fețe al anvelopei convexe a $n$ puncte în spațiul euclidian $d$ -dimensional este $O (n^{⌊ d / 2 ⌋})$ .Format:Sfnp În particular, în două sau trei dimensiuni numărul fețelor este cel mult liniar în $n$ .Format:Sfnp

Poligoane simple

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.Format:Sfnp 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 Format:Ill-wd afirmă că acest proces de expansiune se termină în cele din urmă.Format:Sfnp

Mișcarea browniană

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 $π / 2 < θ < π$ 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) $1 - π / 2 θ$ .Format:Sfnp

Curbe în spațiu

Î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 Format:Ill-wd.Format:Sfnp Un exemplu este oloidul, care este anvelopa convexă a două cercuri din plane perpendiculare, fiecare trecând prin centrul celuilalt.Format:Sfnp 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 Format:Ill-wd ș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.Format:Sfnp

Funcții

Anvelopa convexă a unei funcții $f$ 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 $f$ .Format:Sfnp 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 Format:Ill-wd.Format:Sfnp

Calcul

Î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.Format:Sfnp În două dimensiuni este suficientă lista punctelor care sunt vârfuri în ordinea ciclică în jurul anvelopei.Format:Sfnp

Pentru anvelopa convexă în două sau trei dimensiuni, complexitatea algoritmilor este dată de numărul de puncte date inițial $n$ și numărul de puncte de pe anvelopa convexă $h$ , care poate fi semnificativ mai mic ca $n$ . Pentru anvelope în mai multe dimensiuni, numărul fețelor din alte dimensiuni poate și el conta. Algoritmul Graham poate calcula anvelopa convexă a $n$ puncte în plan în timp de ordinul $O (n \log n)$ . 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 $O (n \log h)$ . Astfel de algoritmi sunt algoritmul Chan și algoritmul Kirkpatrick–Seidel.Format:Sfnp Pentru dimensiuni $d > 3$ , timpul de calcul al anvelopei convexe este de ordinul $O (n^{⌊ d / 2 ⌋})$ , în funcție de situația cea mai proastă din problemă.^[9] Anvelopa convexă a unui poligon simplu din plan poate fi construită în timp de ordin liniar.^[10]

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 Format:Ill-wd,Format:Sfnp iar pentru puncte care se mișcă continuu, o structură de date de tip Format:Ill-wd.Format:Sfnp. Construcția anvelopei convexe este un pas premergător în alți algoritmi, care calculează „lungimea” și „diametrul” mulțimii de puncte.Format:Sfnp

Structuri conexe

Format:Imagine dublă Ș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:

Format:Ill-wd 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.Format:Sfnp
Format:Ill-wd 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.Format:Sfnp
Format:Ill-wd sau anvelopa pozitivă a unei submulțimi a spațiului vectorial este mulțimea tuturor combinațiilor pozitive de puncte din submulțime.Format:Sfnp
Format:Ill-wd a unui obiect tridimensional, în funcție de câteva puncte de vedere, constă din punctele $p$ astfel încât toate razele care pleacă dintr-un punct de vedere și trec printr-un punct $p$ intersectează obiectul. Echivalent este intersecția conurilor neconvexe generate contururile obiectului obținute din punctele respective de vedere. Este folosită la Format:Ill-wd drept cea mai mare formă care produce aceleași contururi văzute din punctele de vedere date.Format:Sfnp
Anvelopa cercuală, sau anvelopa alfa a unei submulțimi din plan este intersecția tuturor discurilor cu o rază dată $1 / α$ care conțin submulțimea.Format:Sfnp
Format:Ill-wd 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.Format:Sfnp
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.Format:Sfnp
Anvelopa convexă ortogonală este un caz particular a unei construcții mai generale, Format:Ill-wd, care poate fi considerată ca fiind cel mai mic Format:Ill-wd care conține punctele date din spațiul metric dat.Format:Sfnp
Anvelopa convexă olomorfă este o generalizare a conceptelor similare cu Format:Ill-wd, obținută ca intersecție a mulțimilor de funcții olomorfe care conțin mulțimea dată.Format:Sfnp

Triangularea Delaunay a unei mulțimi de puncte și a dualului său, Format:Ill-wd, sunt matematic conexe cu anvelopa convexă: triangularea Delaunay a unei mulțimi de puncte din $ℝ^{n}$ poate fi văzută ca proiecția anvelopei convexe în $ℝ^{n + 1} .$ Format:Sfnp Format:Ill-wd 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 triangulării 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.Format:Sfnp Format:Ill-wd 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.Format:Sfnp

Aplicații

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

Matematică

Format:Ill-wd ale polinoamelor de o singură variabilă și Format:Ill-wd 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.^[11] Anvelopa convexă și polinoamele se întâlnesc, de asemenea, în Format:Ill-wd, conform căreia rădăcinile derivatei unui polinom se află toate în anvelopa convexă a rădăcinilor polinomului.Format:Sfnp

În Format:Ill-wd, intervalul numeric al unei matrice normale este anvelopa convexă a valorilor proprii ale acesteia.Format:Sfnp Format:Ill-wd descrie anvelopa convexă a elementelor unitare într-o Format:Ill-wd.Format:Sfnp În geometria discretă, atât Format:Ill-wd, cât și Format:Ill-wd se referă la existența împărțirii mulțimilor de vârfuri în subseturi cu anvelope convexe care se intersectează.Format:Sfnp

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 Format:Ill-wd în topologia bi- și tridimensională.Format:Sfnp 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.Format:Sfnp

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ă

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.Format:Sfnp

În Format:Ill-wd 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.Format:Sfnp

Optimizare combinatorică

Î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ă.^[12] În Format:Ill-wd 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.Format:Sfnp

Economie

În Format:Ill-wd al echilibrului economic general, se presupune că agenții economici au bugetul stabilit și Format:Ill-wd. 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.^[13]

Modelare geometrică

În Format:Ill-wd, 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.Format:Sfnp

Î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.Format:Sfnp

Etologie

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.^[14] 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,Format:Sfnp sau metoda poligonului convex local prin combinarea poligoanelor convexe conform Format:Ill-wd.Format:Sfnp

Fizică cuantică

În fizica cuantică, Format:Ill-wd 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.Format:Sfnp Format:Ill-wd arată că orice stare mixtă poate fi exprimată în mai multe feluri, ca o combinație convexă de stări pure.Format:Sfnp

Istoric

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.^[15] Termenul de „anvelopă convexă” a apărut inițial, în 1922, în recenziile lui Hans Rademacher asupra lucrărilor lui Dénes Kőnig.^[16] 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.Format:Sfnp

Note

Format:Listănote

Bibliografie

Format:Refbegin

Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation; see also review by Hans Rademacher (1922), Format:JFM
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation, translated in Journal of Soviet Mathematics 33 (4): 1140–1153, 1986, Format:Doi
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation
Format:Citation

Format:Refend

Legături externe

Format:En icon Convex hull (Format:Ro) la Encyclopedia of Mathematics, EMS Press, Springer, 2001
Format:En icon Convex Hull, (Format:Ro) la Mathworld

Format:Portal

↑ Format:Harvtxt. Vezi și Douglas Zare, answer to "the perimeter of a non-convex set", MathOverflow, May 16, 2014.
↑ ^2,0 ^2,1 Format:Harvtxt, p. 12; Format:Harvtxt, p. 17.
↑ Format:Harvtxt, p. 6
↑ Format:Harvtxt
↑ Format:Harvtxt; Format:Harvtxt; Format:Harvtxt
↑ Format:Harvtxt, p. 16; Format:Harvtxt, p. 21; Format:Harvtxt.
↑ Exemplul provine din Format:Harvtxt, Remark 2.6.
↑ Format:Harvtxt, Theorem 3, pages 562–563; Format:Harvtxt, Theorem 1.1.2 (pages 2–3) and Chapter 3.
↑ Format:Harvtxt; Format:Harvtxt, p. 256.
↑ Format:Harvtxt; Format:Harvtxt; Format:Harvtxt.
↑ ^11,0 ^11,1 Format:Harvtxt; Format:Harvtxt
↑ ^12,0 ^12,1 Format:Harvtxt; v. în special afirmațiile care derivă din teorema 2.9.
↑ ^13,0 ^13,1 Format:Harvtxt. See in particular Section 16.9, Non Convexity and Approximate Equilibrium, pp. 209–210.
↑ ^14,0 ^14,1 Format:Harvtxt, p. 137–140; Format:Harvtxt
↑ Format:Harvtxt; v. Format:Harvtxt, p. 336, așiFormat:Harvtxt.
↑ Format:Harvtxt, p. 520.

[1] Format:Harvtxt. Vezi și Douglas Zare, answer to "the perimeter of a non-convex set", MathOverflow, May 16, 2014.

[rock12lay17-2] 2,0 ^2,1 Format:Harvtxt, p. 12; Format:Harvtxt, p. 17.

[3] Format:Harvtxt, p. 6

[4] Format:Harvtxt

[5] Format:Harvtxt; Format:Harvtxt; Format:Harvtxt

[6] Format:Harvtxt, p. 16; Format:Harvtxt, p. 21; Format:Harvtxt.

[7] Exemplul provine din Format:Harvtxt, Remark 2.6.

[8] Format:Harvtxt, Theorem 3, pages 562–563; Format:Harvtxt, Theorem 1.1.2 (pages 2–3) and Chapter 3.

[9] Format:Harvtxt; Format:Harvtxt, p. 256.

[10] Format:Harvtxt; Format:Harvtxt; Format:Harvtxt.

[AGKZ-11] 11,0 ^11,1 Format:Harvtxt; Format:Harvtxt

[P1983-12] 12,0 ^12,1 Format:Harvtxt; v. în special afirmațiile care derivă din teorema 2.9.

[N2000-13] 13,0 ^13,1 Format:Harvtxt. See in particular Section 16.9, Non Convexity and Approximate Equilibrium, pp. 209–210.

[KGM-14] 14,0 ^14,1 Format:Harvtxt, p. 137–140; Format:Harvtxt

[15] Format:Harvtxt; v. Format:Harvtxt, p. 336, așiFormat:Harvtxt.

[16] Format:Harvtxt, p. 520.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Anvelopă convexă

Cuprins