Carathéodory's theorem (convex hull) (original) (raw)
Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie. Dans le plan, il affirme que tout point dans l'enveloppe convexe d'un ensemble de points est dans l'intérieur d'un triangle dont les sommets sont dans (l'enveloppe convexe d'un ensemble de points est l'ensemble des barycentres de trois points de ).
| Property | Value | |
|---|---|---|
| dbo:abstract | V konvexní geometrii Carathéodoryho věta říká, že když bod x z Rd leží v konvexním obalu množiny P, pak v množině P existuje d+1 nebo méně bodů takových, že x leží v jejich konvexním obalu. Například, nechť P = {(0,0), (0,1), (1,0), (1,1)}, což je podmnožina R2 (d=2). Konvexní obal této množiny je čtverec. Nechť x = (1/4, 1/4). Vidíme, že x leží v konvexním obalu P. Carathéodoryho věta říká, že v P jsou 3 (=d+1) body takové, že x je v jejich konvexním obalu. V našem případě to jsou např. body {(0,0),(0,1),(1,0)}. Věta navíc říká, že v rovině můžeme vždy najít trojúhelník ze tří bodů z P, obsahující libovolný bod konvexního obalu P. Věta je pojmenována po Constantinu Carathéodorym, který ji dokázal v roce 1911 pro případ, že P je kompaktní. V roce 1912 rozšířil Carathéodoryho větu pro libovolnou P podmnožinu Rd. (cs) Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Namely, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where . The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained. Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the membership of x in the convex hull. The similar theorems of Helly and Radon are closely related to Carathéodory's theorem: the latter theorem can be used to prove the former theorems and vice versa. The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when P is compact. In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in Rd. (en) Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie. Dans le plan, il affirme que tout point dans l'enveloppe convexe d'un ensemble de points est dans l'intérieur d'un triangle dont les sommets sont dans (l'enveloppe convexe d'un ensemble de points est l'ensemble des barycentres de trois points de ). (fr) 数学のの分野におけるカラテオドリの定理（カラテオドリのていり、英: Carathéodory's theorem）とは、Rd 内の点 x がある集合 P の凸包に属するなら、d + 1 個あるいはそれ以下の個数の点からなる P の部分集合 P′ で、x がその凸包に属するようなものが存在する。また同値であるが、 に対し、x は P 内の頂点の r-単体に属する。1911年に、P がコンパクトである場合の証明を与えたコンスタンティン・カラテオドリの名にちなむ。1914年には、がその定理を Rd 内の任意の集合 P に対して拡張した。 例えば、R2 の部分集合である P = {(0,0), (0,1), (1,0), (1,1)} を考える。この集合の凸包は正方形である。今、P の凸包に属する点 x = (1/4, 1/4) を考える。このとき、凸包が三角形であるような集合 {(0,0),(0,1),(1,0)} = P′ を構成すると、x はその中に属し、|P′ | = 3 であるために定理が成立する一例となる。2次元の場合は、この例のように P 内の任意の点を囲む三角形を P の点から構成することが出来るので、カラテオドリの定理を図として可視化する試みは有用となる。 (ja) Теорема Каратеодори о выпуклой оболочке утверждает, что для любой точки выпуклой оболочки подмножества евклидового пространства найдётся содержащий её невырожденный симплекс с вершинами в этом подмножестве. (ru) Теорема Каратеодорі, відноситься до опуклої геометрії та стверджує, що якщо точка x з Rd лежить в опуклій оболонці множини P, то для P знайдеться підмножина P′, яка складається з d + 1 або меншої кількості точок, таких що x лежить в опуклій оболонці P′. Це рівнозначно тому, що x лежить в r-симплексі з вершинами в множині P, де . Теорема названа на честь Костянтина Каратеодорі, який її довів в 1911 році у випадку, коли P — компактна множина. У 1914 році Ернст Стейніц розповсюдив теорему Каратеодорі на випадок довільної множини P з Rd. Наприклад, розглянемо набір P = {(0,0), (0,1), (1,0), (1,1)}, який є підмножиною в R2. Опукла оболонка цієї множини являє собою квадрат. Розглянемо тепер точку x = (1/4, 1/4), яка знаходиться в опуклій оболонці P. Тоді можна побудувати множину {(0,0), (0,1), (1,0)} = P′, опукла оболонка якої є трикутник і охоплює x, і, отже, теорема виконується в даному випадку, так як потужність |
| dbo:thumbnail | wiki-commons:Special:FilePath/Caratheodorys_theorem_example.svg?width=300 | |
| dbo:wikiPageExternalLink | https://planetmath.org/caratheodorystheorem | |
| dbo:wikiPageID | 892014 (xsd:integer) | |
| dbo:wikiPageLength | 12835 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1117392042 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbc:Articles_containing_proofs dbr:Constantin_Carathéodory dbr:Tverberg's_theorem dbc:Theorems_in_convex_geometry dbc:Theorems_in_discrete_geometry dbr:Conical_combination dbr:Convex_combination dbr:Convex_geometry dbr:Convex_hull dbr:Choquet_theory dbr:Simplex dbr:PLS_(complexity) dbr:Linear_independence dbc:Convex_hulls dbr:Ernst_Steinitz dbc:Geometric_transversal_theory dbr:Perron–Frobenius_theorem dbr:Helly's_theorem dbr:Kirchberger's_theorem dbr:Krein–Milman_theorem dbr:Real_number dbr:Shapley–Folkman_lemma dbr:Conical_hull dbr:PlanetMath dbr:PPAD_(complexity) dbr:Radon's_theorem dbr:W.l.o.g. dbr:File:Caratheodorys_theorem_example.svg | |
| dbp:wikiPageUsesTemplate | dbt:Italics_correction dbt:Anchor dbt:Cite_book dbt:Cite_journal dbt:Other_uses dbt:Reflist dbt:Rp dbt:Short_description dbt:Convex_analysis_and_variational_analysis | |
| dct:subject | dbc:Articles_containing_proofs dbc:Theorems_in_convex_geometry dbc:Theorems_in_discrete_geometry dbc:Convex_hulls dbc:Geometric_transversal_theory | |
| rdf:type | yago:WikicatTheoremsInConvexGeometry yago:WikicatTheoremsInDiscreteGeometry yago:WikicatTheoremsInGeometry yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 | |
| rdfs:comment | Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie. Dans le plan, il affirme que tout point dans l'enveloppe convexe d'un ensemble de points est dans l'intérieur d'un triangle dont les sommets sont dans (l'enveloppe convexe d'un ensemble de points est l'ensemble des barycentres de trois points de ). (fr) 数学のの分野におけるカラテオドリの定理（カラテオドリのていり、英: Carathéodory's theorem）とは、Rd 内の点 x がある集合 P の凸包に属するなら、d + 1 個あるいはそれ以下の個数の点からなる P の部分集合 P′ で、x がその凸包に属するようなものが存在する。また同値であるが、 に対し、x は P 内の頂点の r-単体に属する。1911年に、P がコンパクトである場合の証明を与えたコンスタンティン・カラテオドリの名にちなむ。1914年には、がその定理を Rd 内の任意の集合 P に対して拡張した。 例えば、R2 の部分集合である P = {(0,0), (0,1), (1,0), (1,1)} を考える。この集合の凸包は正方形である。今、P の凸包に属する点 x = (1/4, 1/4) を考える。このとき、凸包が三角形であるような集合 {(0,0),(0,1),(1,0)} = P′ を構成すると、x はその中に属し、|P′ | = 3 であるために定理が成立する一例となる。2次元の場合は、この例のように P 内の任意の点を囲む三角形を P の点から構成することが出来るので、カラテオドリの定理を図として可視化する試みは有用となる。 (ja) Теорема Каратеодори о выпуклой оболочке утверждает, что для любой точки выпуклой оболочки подмножества евклидового пространства найдётся содержащий её невырожденный симплекс с вершинами в этом подмножестве. (ru) V konvexní geometrii Carathéodoryho věta říká, že když bod x z Rd leží v konvexním obalu množiny P, pak v množině P existuje d+1 nebo méně bodů takových, že x leží v jejich konvexním obalu. Například, nechť P = {(0,0), (0,1), (1,0), (1,1)}, což je podmnožina R2 (d=2). Konvexní obal této množiny je čtverec. Nechť x = (1/4, 1/4). Vidíme, že x leží v konvexním obalu P. Carathéodoryho věta říká, že v P jsou 3 (=d+1) body takové, že x je v jejich konvexním obalu. V našem případě to jsou např. body {(0,0),(0,1),(1,0)}. Věta navíc říká, že v rovině můžeme vždy najít trojúhelník ze tří bodů z P, obsahující libovolný bod konvexního obalu P. (cs) Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Namely, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where . The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained. Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the m (en) Теорема Каратеодорі, відноситься до опуклої геометрії та стверджує, що якщо точка x з Rd лежить в опуклій оболонці множини P, то для P знайдеться підмножина P′, яка складається з d + 1 або меншої кількості точок, таких що x лежить в опуклій оболонці P′. Це рівнозначно тому, що x лежить в r-симплексі з вершинами в множині P, де . Теорема названа на честь Костянтина Каратеодорі, який її довів в 1911 році у випадку, коли P — компактна множина. У 1914 році Ернст Стейніц розповсюдив теорему Каратеодорі на випадок довільної множини P з Rd. (uk) |
| rdfs:label | Carathéodoryho věta (cs) Carathéodory's theorem (convex hull) (en) Théorème de Carathéodory (géométrie) (fr) カラテオドリの定理 (凸包) (ja) Теорема Каратеодори о выпуклой оболочке (ru) Теорема Каратеодорі про опуклу оболонку (uk) | |
| owl:sameAs | freebase:Carathéodory's theorem (convex hull) wikidata:Carathéodory's theorem (convex hull) dbpedia-cs:Carathéodory's theorem (convex hull) dbpedia-fr:Carathéodory's theorem (convex hull) dbpedia-ja:Carathéodory's theorem (convex hull) dbpedia-ru:Carathéodory's theorem (convex hull) dbpedia-uk:Carathéodory's theorem (convex hull) dbpedia-vi:Carathéodory's theorem (convex hull) https://global.dbpedia.org/id/2L3b3 | |
| prov:wasDerivedFrom | wikipedia-en:Carathéodory's_theorem_(convex_hull)?oldid=1117392042&ns=0 | |
| foaf:depiction | wiki-commons:Special:FilePath/Caratheodorys_theorem_example.svg | |
| foaf:isPrimaryTopicOf | wikipedia-en:Carathéodory's_theorem_(convex_hull) | |
| is dbo:wikiPageDisambiguates of | dbr:Carathéodory's_theorem dbr:Hull | |
| is dbo:wikiPageRedirects of | dbr:Caratheodory's_theorem_(convex_hull) dbr:Colorful_caratheodory_theorem dbr:Caratheodory_theorem_(convex_hull) dbr:Carathéodory_theorem_(convex_hull) | |
| is dbo:wikiPageWikiLink of | dbr:Olof_Hanner dbr:Caratheodory's_theorem_(convex_hull) dbr:Colorful_caratheodory_theorem dbr:Constantin_Carathéodory dbr:Convex_set dbr:Convex_combination dbr:Convex_cone dbr:Convex_hull dbr:Convex_polytope dbr:Leon_Mirsky dbr:Combinatorial_Geometry_in_the_Plane dbr:Steinitz's_theorem_(disambiguation) dbr:Oriented_matroid dbr:Carathéodory's_theorem dbr:Hans_Rådström dbr:List_of_convexity_topics dbr:Helly's_theorem dbr:Circolo_Matematico_di_Palermo dbr:Kirchberger's_theorem dbr:Orthogonal_convex_hull dbr:R._Tyrrell_Rockafellar dbr:Shapley–Folkman_lemma dbr:Knaster–Kuratowski–Mazurkiewicz_lemma dbr:Hull dbr:Imre_Bárány dbr:List_of_theorems dbr:Radon's_theorem dbr:Caratheodory_theorem_(convex_hull) dbr:Carathéodory_theorem_(convex_hull) | |
| is foaf:primaryTopic of | wikipedia-en:Carathéodory's_theorem_(convex_hull) |
