Concept

Carathéodory's theorem (convex hull)

Carathéodory's theorem is a theorem in convex geometry. It states that if a point lies in the convex hull of a set , then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in , as non-extremal points can be removed from without changing the membership of in the convex hull. Its equivalent theorem for conical combinations states that if a point lies in the conical hull of a set , then can be written as the conical combination of at most points in . 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 is compact. In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary set. Carathéodory's theorem in 2 dimensions states that we can construct a triangle consisting of points from P that encloses any point in the convex hull of P. For example, let P = {(0,0), (0,1), (1,0), (1,1)}. The convex hull of this set is a square. Let x = (1/4, 1/4) in the convex hull of P. We can then construct a set {(0,0),(0,1),(1,0)} = ′, the convex hull of which is a triangle and encloses x. Note: We will only use the fact that is an ordered field, so the theorem and proof works even when is replaced by any field , together with a total order. We first formally state Carathéodory's theorem: The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because is the set of finite convex combination of elements of (see the convex hull page for details). With the lemma, Carathéodory's theorem is a simple extension: Alternative proofs uses Helly's theorem or the Perron–Frobenius theorem. For any nonempty , define its Carathéodory's number to be the smallest integer , such that for any , there exists a representation of as a convex sum of up to elements in .

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.