Konvexní obal - Convex hull - Wikipedia

Konvexní trup červené sady je modrá a červená konvexní sada.

v geometrie, konvexní obal nebo konvexní obálka nebo konvexní uzávěr tvaru je nejmenší konvexní sada který to obsahuje. Konvexní trup může být definován buď jako průnik všech konvexních množin obsahujících danou podmnožinu a Euklidovský prostor nebo ekvivalentně jako množina všech konvexní kombinace bodů v podmnožině. Pro ohraničený podmnožina roviny, lze konvexní trup vizualizovat jako tvar uzavřený gumičkou roztaženou kolem této podmnožiny.

Konvexní trupy otevřené sady jsou otevřené a konvexní trupy kompaktní sady jsou kompaktní. Každá kompaktní konvexní sada je jejím konvexním trupem extrémní body. Konvexní operátor trupu je příkladem a operátor uzavření a všechny antihmota může být reprezentován použitím tohoto operátoru uzavření na konečné sady bodů algoritmické problémy s nalezením konvexního trupu konečné sady bodů v rovině nebo jiných nízkodimenzionálních euklidovských prostorech a jeho dvojí problém protnutí poloprostory, jsou zásadní problémy výpočetní geometrie. Mohou být vyřešeny včas ${ displaystyle O (n log n)}$ pro dvourozměrné nebo trojrozměrné množiny bodů a v čase odpovídající nejhorší možné složitosti výstupu dané parametrem věta horní meze ve vyšších dimenzích.

Stejně jako u sad konečných bodů byly studovány také konvexní trupy jednoduché polygony, Brownův pohyb, prostorové křivky, a epigrafy funkcí. Konvexní trupy mají široké uplatnění v matematice, statistice, kombinatorické optimalizaci, ekonomii, geometrickém modelování a etologii. Mezi související struktury patří ortogonální konvexní trup, konvexní vrstvy, Delaunayova triangulace a Voronoiho diagram, a konvexní lebka.

Definice

Konvexní trup ohraničené planární množiny: analogie gumičky

Sada bodů v a Euklidovský prostor je definován jako konvexní pokud obsahuje úsečky spojující každou dvojici jejích bodů. Konvexní trup dané sady ${ displaystyle X}$ lze definovat jako^[1]

1. (Jedinečná) minimální konvexní sada obsahující ${ displaystyle X}$
2. Průnik všech konvexních množin obsahujících ${ displaystyle X}$
3. Sada všech konvexní kombinace bodů v ${ displaystyle X}$
4. Spojení všech jednoduchosti s vrcholy dovnitř ${ displaystyle X}$

Pro ohraničené množiny v euklidovské rovině, ne všichni na jedné linii, je hranicí konvexního trupu znak jednoduchá uzavřená křivka s minimem obvod obsahující ${ displaystyle X}$. Lze si představit protahování a gumička takže obklopuje celou sadu ${ displaystyle S}$ a poté jej uvolnit a umožnit mu uzavřít smlouvu; když se stane napnutým, uzavře konvexní trup ${ displaystyle S}$.^[2] Tato formulace se okamžitě nezobecňuje na vyšší dimenze: pro konečnou množinu bodů v trojrozměrném prostoru je sousedství kostra bodů je obklopuje libovolně malou povrchovou plochou, menší než je povrch konvexního trupu.^[3] Ve vyšších dimenzích však varianty problém s překážkou nalezení povrchu s minimální energií nad daným tvarem může mít jako řešení konvexní trup.^[4]

Pro objekty ve třech rozměrech první definice uvádí, že konvexní trup je nejmenší možný konvex mezní objem Definici pomocí průniků konvexních množin lze rozšířit na neeuklidovská geometrie a definici pomocí konvexních kombinací lze rozšířit z euklidovských prostorů na libovolné skutečné vektorové prostory nebo afinní prostory; konvexní trupy lze také zobecnit abstraktnějším způsobem orientované matroidy.^[5]

Rovnocennost definic

3D konvexní trup mraku 120 bodů

Není zřejmé, že první definice má smysl: proč by měla existovat jedinečná minimální konvexní sada obsahující ${ displaystyle X}$, pro každého ${ displaystyle X}$? Druhá definice je však průsečík všech konvexních množin obsahujících ${ displaystyle X}$, je dobře definovaný. Je to podmnožina každé jiné konvexní množiny ${ displaystyle Y}$ který obsahuje ${ displaystyle X}$, protože ${ displaystyle Y}$ je zahrnuta mezi soubory, které se protínají. Jedná se tedy přesně o jedinečnou minimální konvexní sadu obsahující ${ displaystyle X}$. Proto jsou první dvě definice rovnocenné.^[1]

Každá konvexní sada obsahuje ${ displaystyle X}$ musí (za předpokladu, že je konvexní) obsahovat všechny konvexní kombinace bodů v ${ displaystyle X}$, takže množina všech konvexních kombinací je obsažena v průsečíku všech konvexních sad obsahujících ${ displaystyle X}$. Sada všech konvexních kombinací je naopak konvexní sada obsahující ${ displaystyle X}$, takže obsahuje také průnik všech konvexních množin obsahujících ${ displaystyle X}$, a proto jsou druhá a třetí definice rovnocenné.^[6]

Ve skutečnosti podle Carathéodoryova věta, pokud ${ displaystyle X}$ je podmnožinou a ${ displaystyle d}$-dimenzionální euklidovský prostor, každá konvexní kombinace konečně mnoha bodů ${ displaystyle X}$ je také konvexní kombinace nanejvýš ${ displaystyle d + 1}$ body v ${ displaystyle X}$. Sada konvexních kombinací a ${ displaystyle (d + 1)}$-tuple bodů je a simplexní; v letadle je to trojúhelník a v trojrozměrném prostoru je to čtyřstěn. Proto každá konvexní kombinace bodů ${ displaystyle X}$ patří simplexu, jehož vrcholy patří ${ displaystyle X}$a třetí a čtvrtá definice jsou ekvivalentní.^[6]

Horní a dolní část trupu

Ve dvou rozměrech je konvexní trup někdy rozdělen na dvě části, horní trup a dolní trup, táhnoucí se mezi levými a pravými body trupu. Obecněji řečeno, u konvexních trupů v jakékoli dimenzi lze rozdělit hranici trupu na body směřující vzhůru (body, u nichž je paprsek směřující nahoru disjunktní od trupu), body směřující dolů a krajní body. U trojrozměrných trupů tvoří části hranice směřující nahoru a dolů topologické disky.^[7]

Topologické vlastnosti

Uzavřené a otevřené trupy

The uzavřený konvexní trup sady je uzavření konvexního trupu a otevřený konvexní trup je interiér (nebo v některých zdrojích relativní interiér ) konvexního trupu.^[8]

Uzavřený konvexní trup ${ displaystyle X}$ je průsečík všech uzavřených poloprostory obsahující ${ displaystyle X}$Pokud je konvexní trup ${ displaystyle X}$ již je uzavřená sada sám (jak se stane, například, pokud ${ displaystyle X}$ je konečná množina nebo obecněji kompaktní sada ), pak se rovná uzavřenému konvexnímu trupu. Průsečík uzavřených poloprostorů je však sám uzavřen, takže když není uzavřený konvexní trup, nelze jej tímto způsobem znázornit.^[9]

Pokud je otevřený konvexní trup množiny ${ displaystyle X}$ je ${ displaystyle d}$-dimenzionální, pak každý bod trupu náleží maximálně otevřenému konvexnímu trupu ${ displaystyle 2d}$ body ${ displaystyle X}$. Množiny vrcholů čtverce, pravidelného osmistěnu nebo vyšší dimenze křížový mnohostěn uveďte příklady, kde přesně ${ displaystyle 2d}$ body jsou potřeba.^[10]

Zachování topologických vlastností

The čarodějnice z Agnesi. Body na červené křivce nebo nad ní poskytují příklad uzavřené množiny, jejíž konvexní trup je otevřený (otevřený horní polorovina ).

Topologicky konvexní trup otevřená sada je vždy sám otevřený a konvexní trup kompaktní sady je vždy sám kompaktní. Existují však uzavřené sady, pro které není uzavřený trup uzavřený.^[11] Například uzavřená množina

${ displaystyle left {(x, y) mathop { bigg |} y geq { frac {1} {1 + x ^ {2}}} vpravo }}$

(sada bodů, které leží na nebo nad čarodějnice z Agnesi ) má otevřeno horní polorovina jako jeho konvexní trup.^[12]

Kompaktnost konvexních trupů kompaktních sad v konečných trojrozměrných euklidovských prostorech je zobecněna Kerin – Smulianova věta, podle kterého uzavřený konvexní trup slabě kompaktní podmnožiny a Banachův prostor (podmnožina, která je kompaktní pod slabá topologie ) je slabě kompaktní.^[13]

Extrémní body

An extrémní bod konvexní množiny je bod v množině, který neleží na žádném otevřeném úsečce mezi dalšími dvěma body stejné množiny. U konvexního trupu musí být každý krajní bod součástí dané množiny, protože jinak to nemůže být vytvořený jako konvexní kombinace daných bodů. Podle Kerin – Milmanova věta, každá kompaktní konvexní množina v euklidovském prostoru (nebo obecněji v a lokálně konvexní topologický vektorový prostor ) je konvexní trup jejích krajních bodů.^[14] To však nemusí platit pro konvexní množiny, které nejsou kompaktní; například celá euklidovská rovina a koule otevřené jednotky jsou konvexní, ale ani jedna nemá žádné extrémní body. Choquetova teorie rozšiřuje tuto teorii z konečných konvexních kombinací krajních bodů na nekonečné kombinace (integrály) v obecnějších prostorech.^[15]

Geometrické a algebraické vlastnosti

Operátor uzavření

Operátor konvexního trupu má charakteristické vlastnosti a operátor uzavření:^[16]

• to je rozsáhlý, což znamená, že konvexní trup každé sady ${ displaystyle X}$ je nadmnožinou ${ displaystyle X}$.
• to je neklesající, což znamená, že pro každé dvě sady ${ displaystyle X}$ a Y s ${ displaystyle X subseteq Y}$, konvexní trup ${ displaystyle X}$ je podmnožinou konvexního trupu ${ displaystyle Y}$.
• to je idempotentní, což znamená, že pro každého ${ displaystyle X}$, konvexní trup konvexního trupu ${ displaystyle X}$ je stejný jako konvexní trup ${ displaystyle X}$.

Při aplikaci na konečnou množinu bodů se jedná o operátor uzavření antihmota, antihmota ostřelování množiny bodů. Každá antihmota může být takto reprezentována konvexními trupy bodů v euklidovském prostoru dostatečně vysoké dimenze.^[17]

Minkowského součet

Operace konstrukce konvexního trupu a převzetí Minkowského součet dojíždět mezi sebou v tom smyslu, že Minkowského součet konvexních trupů množin poskytuje stejný výsledek jako konvexní trup Minkowského součtu stejných množin. To poskytuje krok směrem k Věta Shapley – Folkman ohraničující vzdálenost Minkowského součtu od jeho konvexního trupu.^[18]

Projektivní dualita

The projektivní duální operace na konstrukci konvexního trupu sady bodů je konstrukce průniku rodiny uzavřených poloprostorů, které všechny obsahují počátek (nebo jakýkoli jiný určený bod).^[19]

Speciální případy

Sady konečných bodů

Konvexní trup bodů v rovině

Konvexní trup množiny konečných bodů ${ displaystyle S podmnožina mathbb {R} ^ {d}}$ tvoří a konvexní mnohoúhelník když ${ displaystyle d = 2}$, nebo obecněji a konvexní mnohostěn v ${ displaystyle mathbb {R} ^ {d}}$. Každý krajní bod trupu se nazývá a vrchol, a (podle Kerin-Milmanovy věty) je každý konvexní polytop konvexním trupem jeho vrcholů. Jedná se o jedinečný konvexní mnohostěn, jehož vrcholy patří ${ displaystyle S}$ a to zahrnuje vše ${ displaystyle S}$.^[2]Pro sady bodů v obecná pozice, konvexní trup je a zjednodušený mnohostěn.^[20]

Podle věta horní meze, počet tváří konvexního trupu ${ displaystyle n}$ body v ${ displaystyle d}$-dimenzionální euklidovský prostor je ${ displaystyle O (n ^ { lfloor d / 2 rfloor})}$.^[21] Zejména ve dvou a třech rozměrech je počet ploch nanejvýš lineární ${ displaystyle n}$.^[22]

Jednoduché mnohoúhelníky

Konvexní trup jednoduchého mnohoúhelníku

Konvexní trup a jednoduchý mnohoúhelník uzavírá daný polygon a je jím rozdělen do oblastí, z nichž jeden je samotný polygon. Ostatní regiony ohraničené a polygonální řetěz polygonu a jedné konvexní hrany trupu jsou volány kapsy. Výpočet stejného rozkladu rekurzivně pro každou kapsu tvoří hierarchický popis daného polygonu zvaného jeho konvexní strom rozdílů.^[23] Odražení kapsy napříč konvexní hranou trupu rozšiřuje daný jednoduchý polygon na polygon se stejným obvodem a větší oblastí a Erdős – Nagyova věta uvádí, že tento proces rozšiřování nakonec končí.^[24]

Brownův pohyb

Křivka generovaná Brownův pohyb v rovině, v jakémkoli pevném čase, má pravděpodobnost 1 mít konvexní trup, jehož hranice tvoří a spojitě diferencovatelná křivka. Nicméně pro jakýkoli úhel ${ displaystyle theta}$ v dosahu ${ displaystyle pi / 2 < theta < pi}$, během Brownova pohybu budou chvíle, kdy se pohybující se částice dotkne hranice konvexního trupu v úhlovém bodě ${ displaystyle theta}$. The Hausdorffova dimenze této sady výjimečných časů je (s vysokou pravděpodobností) ${ displaystyle 1- pi / 2 theta}$.^[25]

Prostorové křivky

An oloid, konvexní trup dvou kruhů ve 3D prostoru

Pro konvexní trup a prostorová křivka nebo konečná množina prostorových křivek v obecné poloze v trojrozměrném prostoru, části hranice od křivek jsou rozvinutelné a ovládané povrchy.^[26] Mezi příklady patří oloid, konvexní trup dvou kruhů v kolmých rovinách, z nichž každá prochází středem druhé,^[27] the sféikon, konvexní trup dvou půlkruhů v kolmých rovinách se společným středem a tvary D, konvexní tvary získané z Alexandrovova věta o jedinečnosti pro povrch vytvořený slepením dvou rovinných konvexních sad o stejném obvodu.^[28]

Funkce

Konvexní trup nebo spodní konvexní obálka funkce ${ displaystyle f}$ na reálném vektorovém prostoru je funkce, jejíž epigraf je spodní konvexní trup epigrafu ${ displaystyle f}$.Jedná se o jedinečný maximum konvexní funkce specializován na ${ displaystyle f}$.^[29] Definici lze rozšířit na konvexní trup množiny funkcí (získaný z konvexního trupu spojení jejich epigrafů nebo ekvivalentně z jejich bodového minima) a v této formě je duální vůči konvexní konjugát úkon.^[30]

Výpočet

v výpočetní geometrie, je známa řada algoritmů pro výpočet konvexního trupu pro konečnou množinu bodů a pro další geometrické objekty. Výpočet konvexního trupu znamená konstrukci jednoznačného a efektivního zastoupení požadovaného konvexního tvaru. Výstupní reprezentace, které byly brány v úvahu pro konvexní trupy množin bodů, zahrnují seznam lineární nerovnosti popisující fazety trupu, an neorientovaný graf aspektů a jejich sousedství nebo celé obličejová mříž trupu.^[31] Ve dvou dimenzích může stačit jednodušší vypsat body, které jsou vrcholy, v jejich cyklickém pořadí kolem trupu.^[2]

U konvexních trupů ve dvou nebo třech rozměrech se složitost odpovídajících algoritmů obvykle odhaduje z hlediska ${ displaystyle n}$, počet vstupních bodů a ${ displaystyle h}$, počet bodů na konvexním trupu, který může být výrazně menší než ${ displaystyle n}$. U trupů vyšších dimenzí může do analýzy vstoupit také počet ploch jiných dimenzí. Grahamovo skenování může vypočítat konvexní trup ${ displaystyle n}$ body v rovině v čase ${ displaystyle O (n log n)}$. U bodů ve dvou a třech rozměrech složitější algoritmy citlivé na výstup je známo, že počítají konvexní trup v čase ${ displaystyle O (n log h)}$. Tyto zahrnují Chanův algoritmus a Algoritmus Kirkpatrick – Seidel.^[32] Pro rozměry ${ displaystyle d> 3}$, je čas pro výpočet konvexního trupu ${ displaystyle O (n ^ { lfloor d / 2 rfloor})}$, což odpovídá nejhorší výstupní složitosti problému.^[33] Konvexní trup jednoduchého mnohoúhelníku v rovině lze zkonstruovat lineární čas.^[34]

Dynamický konvexní trup datové struktury lze použít ke sledování konvexního trupu sady bodů, které procházejí vkládáním a mazáním bodů,^[35] a kinetický konvexní trup struktury mohou sledovat konvexní trup bodů, které se pohybují nepřetržitě.^[36]Konstrukce konvexních trupů slouží také jako nástroj, stavební blok pro řadu dalších výpočetně-geometrických algoritmů, jako je rotační třmeny metoda výpočtu šířka a průměr množiny bodů.^[37]

Související struktury

Ortogonální konvexní trup

Relativní konvexní trup

Několik dalších tvarů lze definovat ze sady bodů podobným způsobem jako konvexní trup, jako minimální nadmnožina s nějakou vlastností, průnik všech tvarů obsahujících body z dané rodiny tvarů nebo sjednocení všech kombinací body za určitý typ kombinace. Například:

• The afinní trup je nejmenší afinní podprostor euklidovského prostoru obsahující danou množinu nebo sjednocení všech afinních kombinací bodů v množině.^[38]
• The lineární trup je nejmenší lineární podprostor vektorového prostoru obsahující danou množinu nebo sjednocení všech lineárních kombinací bodů v množině.^[38]
• The kónický trup nebo kladný trup podmnožiny vektorového prostoru je množina všech kladných kombinací bodů v podmnožině.^[38]
• The vizuální trup trojrozměrného objektu, vzhledem k množině hledisek, se skládá z bodů ${ displaystyle p}$ tak, že každý paprsek z pohledu přes ${ displaystyle p}$ protíná objekt. Ekvivalentně je to průsečík (nekonvexních) kuželů generovaných obrysem objektu vzhledem ke každému hledisku. Používá se v 3D rekonstrukce jako největší tvar, který může mít stejné obrysy z daných hledisek.^[39]
• Kruhový trup nebo alfa trup podmnožiny roviny je průsečík všech disků s daným poloměrem ${ displaystyle 1 / alpha}$ které obsahují podmnožinu.^[40]
• The relativní konvexní trup podmnožiny dvojrozměrného jednoduchý mnohoúhelník je průsečík všech relativně konvexních nadmnožin, kde množina ve stejném polygonu je relativně konvexní, pokud obsahuje geodetické mezi libovolnými dvěma jeho body.^[41]
• The ortogonální konvexní trup nebo přímočarý konvexní trup je průsečík všech ortogonálně konvexních a spojených nadmnožin, kde množina je ortogonálně konvexní, pokud obsahuje všechny osově rovnoběžné segmenty mezi dvojicemi jejích bodů.^[42]
• Ortogonální konvexní trup je zvláštním případem mnohem obecnější konstrukce, hyperkonvexní trup, které lze považovat za nejmenší injektivní metrický prostor obsahující body daného metrický prostor.^[43]
• The holomorfně konvexní trup je zobecněním podobných konceptů jako komplexní analytické potrubí, získaný jako průnik podúrovňových množin holomorfní funkce obsahující danou sadu.^[44]

The Delaunayova triangulace množiny bodů a jejích dvojí, Voronoiho diagram, jsou matematicky příbuzné konvexním trupům: Delaunayova triangulace bodu zasazeného do ${ displaystyle mathbb {R} ^ {n}}$ lze považovat za projekci konvexního trupu dovnitř ${ displaystyle mathbb {R} ^ {n + 1}.}$^[45]The alfa tvary množiny konečných bodů dávají vnořenou rodinu (nekonvexních) geometrických objektů popisujících tvar množiny bodů na různých úrovních detailů. Každý z alfa tvarů je sjednocením některých rysů Delaunayovy triangulace, vybrané porovnáním jejich circumradius k parametru alfa. Samotná množina bodů tvoří jeden koncový bod této rodiny tvarů a jeho konvexní trup tvoří druhý koncový bod.^[40]The konvexní vrstvy množiny bodů jsou vnořená rodina konvexních polygonů, jejichž nejvzdálenějším bodem je konvexní trup, přičemž vnitřní vrstvy jsou konstruovány rekurzivně z bodů, které nejsou vrcholy konvexního trupu.^[46]

The konvexní lebka polygonu je největší konvexní polygon obsažený v něm. Najdete jej v polynomiální čas, ale exponent algoritmu je vysoký.^[47]

Aplikace

Konvexní trupy mají široké uplatnění v mnoha oblastech. V rámci matematiky se ke studiu používají konvexní trupy polynomy, matice vlastní čísla, a jednotkové prvky a několik vět v diskrétní geometrie zahrnovat konvexní trupy. Používají se v robustní statistiky jako nejvzdálenější obrys Tukey hloubka, jsou součástí dudák vizualizace dvourozměrných dat a definování sad rizik pravidla náhodného rozhodování. Konvexní trupy vektory indikátorů řešení kombinatorických problémů jsou ústřední kombinatorická optimalizace a polyedrická kombinatorika. V ekonomii, konvexní trupy mohou být použity k použití metod konvexnost v ekonomii na nekonvexní trhy. V geometrickém modelování je vlastnost konvexního trupu Bézierovy křivky pomáhá najít jejich přechody a konvexní trupy jsou součástí měření trupů lodí. A při studiu chování zvířat se ve standardní definici používají konvexní trupy domácí sortiment.

Matematika

Rozdělení sedmi bodů do tří podmnožin s protínajícími se konvexními trupy, zaručeně existující pro všech sedm bodů v rovině Tverbergova věta

Newtonovy mnohoúhelníky univariate polynomy a Newtonské polytopy vícerozměrných polynomů jsou konvexní trupy bodů odvozené od exponentů termínů v polynomu a lze je použít k analýze asymptotické chování polynomu a ocenění jeho kořenů.^[48] Konvexní trupy a polynomy se také spojují v Gauss – Lucasova věta, podle kterého kořeny derivace polynomu leží všechny v konvexním trupu kořenů polynomu.^[49]

v spektrální analýza, číselný rozsah a normální matice je jeho konvexní trup vlastní čísla.^[50]The Russo – Dyeova věta popisuje konvexní trupy jednotkové prvky v C * -algebra.^[51]v diskrétní geometrie, oba Radonova věta a Tverbergova věta se týkají existence oddílů bodových sad do podmnožin s protínajícími se konvexními trupy.^[52]

Definice konvexní množiny obsahující přímkové úseky mezi jejími body a konvexního trupu jako průsečíku všech konvexních nadmnožin platí pro hyperbolické prostory stejně jako do euklidovských prostorů. V hyperbolickém prostoru je však také možné uvažovat o konvexních trupech množin ideální body, body, které nepatří do samotného hyperbolického prostoru, ale leží na hranici modelu tohoto prostoru. Hranice konvexních trupů ideálních bodů trojrozměrného hyperbolického prostoru jsou analogické ovládané povrchy v euklidovském prostoru a jejich metrické vlastnosti hrají důležitou roli v domněnka o geometrizaci v nízkodimenzionální topologie.^[53] Hyperbolické konvexní trupy byly také použity jako součást výpočtu kanonický triangulace z hyperbolické rozdělovače, a použity k určení ekvivalence uzly.^[54]

Viz také část o Brownův pohyb pro použití konvexních trupů na toto téma a část o prostorové křivky pro jejich aplikaci na teorii rozvinutelné povrchy.

Statistika

A dudák. Vnější stínovaná oblast je konvexní trup a vnitřní stínovaná oblast je obrys hloubky 50% Tukey.

v robustní statistiky, konvexní trup poskytuje jednu z klíčových složek a dudák, metoda pro vizualizaci šíření dvourozměrných vzorových bodů. Obrysy Tukey hloubka tvoří vnořenou rodinu konvexních množin s konvexním trupem nejvzdálenější a dudy také zobrazují další mnohoúhelník z této vnořené rodiny, obrys 50% hloubky.^[55]

Ve statistice teorie rozhodování, sada rizik a pravidlo náhodného rozhodování je konvexní trup rizikových bodů jejích základních deterministických pravidel rozhodování.^[56]

Kombinatorická optimalizace

v kombinatorická optimalizace a polyedrická kombinatorika, ústředními objekty studia jsou konvexní trupy vektory indikátorů řešení kombinatorického problému. Pokud lze najít aspekty těchto polytopů, které popisují polytopy jako průniky polovičních prostorů, pak algoritmy založené na lineární programování lze použít k nalezení optimálního řešení.^[57] v vícecílová optimalizace, používá se také jiný typ konvexního trupu, konvexní trup váhových vektorů řešení. Jeden může maximalizovat jakýkoli kvazikonvexní kombinace váh hledáním a kontrolou každého konvexního vrcholu trupu, často efektivnější než kontrola všech možných řešení.^[58]

Ekonomika

V Šipka – Debreuův model z obecná ekonomická rovnováha, předpokládá se, že agenti mají konvexní rozpočtové sady a konvexní preference. Tyto předpoklady konvexnost v ekonomice lze použít k prokázání existence rovnováhy. Jsou-li skutečné ekonomické údaje nekonvexní, to může být konvexní tím, že vezme konvexní trupy. Shapley-Folkmanovu větu lze použít k prokázání, že pro velké trhy je tato aproximace přesná a vede k „kvazi-rovnováze“ pro původní nekonvexní trh.^[59]

Geometrické modelování

v geometrické modelování, jedna z klíčových vlastností a Bézierova křivka spočívá v tom, že leží v konvexním trupu jejích řídicích bodů. Tuto takzvanou „konvexní vlastnost trupu“ lze použít například k rychlé detekci průsečíků těchto křivek.^[60]

V geometrii konstrukce lodi a lodi obvod řetězu je měření velikosti plachetnice definované pomocí konvexního trupu průřezu trup plavidla. Liší se od obvod kůže, obvod samotného průřezu, s výjimkou lodí a lodí, které mají konvexní trup.^[61]

Etologie

Konvexní trup je obecně známý jako minimální konvexní polygon v etologie, studium chování zvířat, kde se jedná o klasický, i když možná zjednodušující přístup k odhadu zvířete domácí sortiment na základě bodů, kde bylo zvíře pozorováno.^[62] Odlehlé hodnoty může nadměrně zvětšit minimální konvexní polygon, což motivovalo uvolněné přístupy, které obsahují pouze podmnožinu pozorování, například výběrem jedné z konvexních vrstev, která se blíží cílovému procentu vzorků,^[63] nebo v místní konvexní trup metoda kombinací konvexních trupů sousedství bodů.^[64]

Kvantová fyzika

v kvantová fyzika, státní prostor jakéhokoli kvantového systému - množiny všech způsobů, jak lze systém připravit - je konvexní trup, jehož extrémní body jsou kladně semidefinitní operátory známé jako čisté stavy a jejichž vnitřní body se nazývají smíšené stavy.^[65] The Schrödingerova – HJW věta dokazuje, že jakýkoli smíšený stav lze ve skutečnosti zapsat jako konvexní kombinaci čistých stavů několika způsoby.^[66]

Dějiny

Dolní konvexní trup bodů v rovině se objeví ve formě Newtonova mnohoúhelníku v dopise od Isaac Newton na Henry Oldenburg v roce 1676.^[67] Samotný pojem „konvexní trup“ se objevuje již v práci Garrett Birkhoff  (1935 ) a odpovídající výraz v Němec se objeví dříve, například v Hans Rademacher recenze uživatele Kőnig  (1922 ). V tomto časovém rámci byly rovněž použity jiné výrazy, například „konvexní obálka“.^[68] Do roku 1938, podle Lloyd Dines, pojem „konvexní trup“ se stal standardem; Dines dodává, že tento výraz považuje za nešťastný, protože hovorový význam slova „trup“ by naznačoval, že odkazuje na povrch tvaru, zatímco konvexní trup zahrnuje vnitřek a ne pouze povrch.^[69]

Poznámky

Reference

externí odkazy

• "Konvexní obal", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Weisstein, Eric W., "Konvexní obal", MathWorld
• "Konvexní obal" podle Eric W. Weisstein, Demonstrační projekt Wolfram, 2007.