Теорема Каратеодори (выпуклая оболочка)

Чтобы узнать о других значениях, см. теорему Каратеодори (значения) .

Теорема Каратеодори — теорема выпуклой геометрии . В нем говорится, что если точка $x$ лежит в выпуклой оболочке $\mathrm {Conv} (P)$ из набора $P\subset \mathbb {R} ^{d}$, затем $x$ лежит в каком-то $d$-мерный симплекс с вершинами в $P$. Эквивалентно, $x$ можно записать как выпуклую комбинацию не более чем $d+1$ указывает на $P$. Кроме того, $x$ можно записать как выпуклую комбинацию не более чем $d+1$ крайние точки в $P$, так как неэкстремальные точки можно удалить из $P$ без изменения состава $x$ в выпуклой оболочке.

Эквивалентная теорема для конических комбинаций утверждает, что если точка $x$ лежит в коническом корпусе $\mathrm {Cone} (P)$ из набора $P\subset \mathbb {R} ^{d}$, затем $x$ можно записать как коническую комбинацию не более $d$ указывает на $P$.

Две другие теоремы Хелли и Радона тесно связаны с теоремой Каратеодори: последняя теорема может быть использована для доказательства первых теорем и наоборот.

Результат назван в честь Константина Каратеодори , доказавшего теорему в 1911 году для случая, когда $P$ компактен ​ . В 1914 году Эрнст Стейниц расширил теорему Каратеодори для произвольных множеств.

Пример

Иллюстрация теоремы Каратеодори для квадрата в R. ²

Теорема Каратеодори в двух измерениях утверждает, что мы можем построить треугольник, состоящий из точек из P , который заключает в себе любую точку выпуклой оболочки P .

Например, пусть P = {(0,0), (0,1), (1,0), (1,1)}. Выпуклая оболочка этого множества представляет собой квадрат. Пусть x = (1/4, 1/4) в выпуклой оболочке P . Затем мы можем построить набор {(0,0),(0,1),(1,0)} = P ′, выпуклая оболочка которого является треугольником и заключает в себе x.

Доказательство

Примечание. Мы будем использовать только тот факт, что $\mathbb {R}$ является упорядоченным полем , поэтому теорема и доказательство работают, даже если $\mathbb {R}$ заменяется любым полем $\mathbb {F}$, вместе с общим заказом.

Сначала формально сформулируем теорему Каратеодори:

Теорема Каратеодори — Если $x\in \mathrm {Cone} (S)\subset \mathbb {R} ^{d}$, затем $x$ представляет собой неотрицательную сумму не более $d$ точки $S$.

Если $x\in \mathrm {Conv} (S)\subset \mathbb {R} ^{d}$, затем $x$ является выпуклой суммой не более $d+1$ точки $S$.

Суть теоремы Каратеодори заключается в конечном случае. Такое сведение к конечному случаю возможно, поскольку $\mathrm {Conv} (S)$ – множество конечной выпуклой комбинации элементов $S$ ( выпуклой оболочки подробности см. на странице ).

Лемма — Если $q_{1},...,q_{N}\in \mathbb {R} ^{d}$ затем $\forall x\in \mathrm {Conv} (\{q_{1},...,q_{N}\})$, существует $w_{1},...,w_{N}\geq 0$ такой, что $x=\sum _{n}w_{n}q_{n}$, и самое большее $d$ из них ненулевые.

Благодаря лемме теорема Каратеодори представляет собой простое расширение:

Доказательство теоремы Каратеодори.

Для любого $x\in \mathrm {Conv} (S)$, представлять $x=\sum _{n=1}^{N}w_{n}q_{n}$ для некоторых $q_{1},...,q_{N}\in S$, затем $x\in \mathrm {Conv} (\{q_{1},...,q_{N}\})$, и мы воспользуемся леммой.

Вторая часть сводится к первой части путем «поднятия одного измерения» - распространенный прием, используемый для сведения аффинной геометрии к линейной алгебре и сведения выпуклых тел к выпуклым конусам.

Явно, пусть $S\subset \mathbb {R} ^{d}$, затем определите $\mathbb {R} ^{d}$ с подмножеством $\{w\in \mathbb {R} ^{d+1}:w_{d+1}=1\}$. Это вызывает встраивание $S$ в $S\times \{1\}\subset \mathbb {R} ^{d+1}$.

Любой $x\in S$, по первой части, имеет «приподнятое» представление $(x,1)=\sum _{n=1}^{N}w_{n}(q_{n},1)$ где максимум $d+1$ из $w_{n}$ ненулевые. То есть, $x=\sum _{n=1}^{N}w_{n}q_{n}$, и $1=\sum _{n=1}^{N}w_{n}$, что завершает доказательство.

Доказательство леммы

Это тривиально, когда $N\leq d$. Если мы сможем доказать это всем $N=d+1$, то по индукции мы доказали это для всех $N\geq d+1$. Таким образом, остается доказать это для $N=d+1$. Это докажем индукцией по $d$.

Базовый случай: $d=1,N=2$, тривиально.

Индукционный корпус. Представлять $x=\sum _{n=1}^{d+1}w_{n}q_{n}$. Если некоторые $w_{n}=0$, то доказательство закончено. Итак, предположим, что все $w_{n}>0$

Если $\{q_{1},...,q_{d}\}$ линейно зависима, то мы можем использовать индукцию по ее линейной оболочке, чтобы исключить один ненулевой член в $\sum _{n=1}^{d}{\frac {w_{n}}{w_{1}+\cdots +w_{d}}}q_{n}$, и тем самым устранить его в $x=\sum _{n=1}^{d+1}w_{n}q_{n}$ также.

В противном случае существует $(u_{1},...,u_{d})\in \mathbb {R} ^{d}$, такой, что $\sum _{n=1}^{d}u_{n}q_{n}=q_{d+1}$. Тогда мы можем интерполировать полный интервал представлений:

$$x=\sum _{n=1}^{d}(w_{n}+\theta w_{d+1}u_{n})q_{n}+(1-\theta )w_{d+1}q_{d+1};\quad \theta \in [0,1]$$

Если $w_{n}+w_{d+1}u_{n}\geq 0$ для всех $n=1,...,d$, затем установите $\theta =1$. В противном случае, пусть $\theta$ быть самым маленьким $\theta$ такой, что один из $w_{n}+\theta w_{d+1}u_{n}=0$. Тогда мы получим выпуклое представление $x$ с $\leq d$ ненулевые члены.

Альтернативные доказательства используют теорему Хелли или теорему Перрона-Фробениуса .

Варианты

Номер Каратеодори

Для любого непустого $P\subset \mathbb {R} ^{d}$, определите его число Каратеодори как наименьшее целое число $r$, такой, что для любого $x\in \mathrm {Conv} (P)$, существует представление $x$ в виде выпуклой суммы до $r$ элементы в $P$.

Теорема Каратеодори просто утверждает, что любое непустое подмножество $\mathbb {R} ^{d}$ есть номер Каратеодори $\leq d+1$. Эта верхняя граница не обязательно достигается. Например, единичная сфера в $\mathbb {R} ^{d}$ имеет число Каратеодори, равное 2, поскольку любая точка внутри сферы представляет собой выпуклую сумму двух точек на сфере.

С дополнительными предположениями о $P\subset \mathbb {R} ^{d}$, верхние границы строго ниже, чем $d+1$ можно получить.

Безразмерный вариант

Недавно Адипрасито, Барани, Мустафа и Терпаи доказали вариант теоремы Каратеодори, не зависящий от размерности пространства.

Красочная теорема Каратеодори

Пусть X ₁ , ..., X _{d +1} — множества из R ^д и пусть x — точка, содержащаяся в пересечении выпуклых оболочек всех этих d +1 множеств.

Тогда существует множество T = { x ₁ , ..., x _{d +1} }, где x ₁ ∈ X ₁ , ..., x _{d +1} ∈ X _{d +1} , такое, что выпуклая оболочка T содержит точка х .

Если рассматривать множества X ₁ , ..., X _{d +1} как разные цвета, то множество T состоит из точек всех цветов, отсюда и слово «красочный» в названии теоремы. Множество T также называют радужным симплексом , поскольку это d -мерный симплекс , в котором каждый угол имеет свой цвет.

У этой теоремы есть вариант, в котором выпуклая оболочка заменяется конической оболочкой . Пусть X ₁ , ..., X _d — множества из R ^д и пусть x — точка, содержащаяся в пересечении конических оболочек всех этих d множеств. Тогда существует множество T = { x ₁ , ..., x _d где x ₁ ∈ X ₁ , ..., x _d ∈ X _d , такое, что коническая оболочка T } , содержит точку x .

Мустафа и Рэй распространили эту красочную теорему на перенос точек на выпуклые тела.

Вычислительная задача поиска красочного множества лежит на пересечении классов сложности PPAD и PLS .

См. также

• Лемма Шепли – Фолкмана.
• Теорема Хелли
• Теорема Кирхбергера
• N-мерный многогранник
• Теорема Радона и ее обобщение Теорема Тверберга
• Теорема Крейна – Милмана
• Теория Шоке

Дальнейшее чтение

• Экхофф, Дж. (1993). «Теоремы типа Хелли, Радона и Каратеодори». Справочник по выпуклой геометрии . Том. А, Б. Амстердам: Северная Голландия. стр. 389–448.
• Мустафа, Набиль; Менье, Фредерик; Гоаок, Ксавьер; Де Лоэра, Хесус (2019). «Дискретные, но вездесущие теоремы Каратеодори, Хелли, Спернера, Такера и Тверберга». Бюллетень Американского математического общества . 56 (3): 415–511. arXiv : 1706.05975 . дои : 10.1090/bull/1653 . ISSN   0273-0979 . S2CID   32071768 .

Внешние ссылки

• Краткое изложение теоремы в терминах выпуклых оболочек (на PlanetMath )