Jump to content

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

Теорема Каратеодори — теорема выпуклой геометрии . В нем говорится, что если точка лежит в выпуклой оболочке из набора , затем лежит в каком-то -мерный симплекс с вершинами в . Эквивалентно, можно записать как выпуклую комбинацию не более чем указывает на . Кроме того, можно записать как выпуклую комбинацию не более чем крайние точки в , так как неэкстремальные точки можно удалить из без изменения состава в выпуклой оболочке.

Эквивалентная теорема для конических комбинаций утверждает, что если точка лежит в коническом корпусе из набора , затем можно записать как коническую комбинацию не более указывает на . [ 1 ] : 257 

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

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

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

Теорема Каратеодори в двух измерениях утверждает, что мы можем построить треугольник, состоящий из точек из 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.

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

[ редактировать ]

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


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

Теорема Каратеодори Если , затем представляет собой неотрицательную сумму не более точки .

Если , затем является выпуклой суммой не более точки .

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

Лемма Если затем , существует такой, что , и самое большее из них ненулевые.

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

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

Для любого , представлять для некоторых , затем , и мы воспользуемся леммой.

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

Явно, пусть , затем определите с подмножеством . Это вызывает встраивание в .

Любой , по первой части, имеет «приподнятое» представление где максимум из ненулевые. То есть, , и , что завершает доказательство.

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

Это тривиально, когда . Если мы сможем доказать это всем , то по индукции мы доказали это для всех . Таким образом, остается доказать это для . Это докажем индукцией по .

Базовый случай: , тривиально.

Индукционный корпус. Представлять . Если некоторые , то доказательство закончено. Итак, предположим, что все

Если линейно зависима, то мы можем использовать индукцию по ее линейной оболочке, чтобы исключить один ненулевой член в , и тем самым устранить его в также.

В противном случае существует , такой, что . Тогда мы можем интерполировать полный интервал представлений:

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

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

Варианты

[ редактировать ]

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

[ редактировать ]

Для любого непустого , определите его число Каратеодори как наименьшее целое число , такой, что для любого , существует представление в виде выпуклой суммы до элементы в .

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

С дополнительными предположениями о , верхние границы строго ниже, чем можно получить. [ 8 ]

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

У этой теоремы есть вариант, в котором выпуклая оболочка заменяется конической оболочкой . [ 10 ] : Thm.2.2 Пусть X 1 , ..., X d — множества из R д и пусть x — точка, содержащаяся в пересечении конических оболочек всех этих d множеств. Тогда существует множество T = { x 1 , ..., x d где x 1 X 1 , ..., x d X d , такое, что коническая оболочка T } , содержит точку x . [ 10 ]

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

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Ловас, Ласло ; Пламмер, доктор медицины (1986). Теория соответствия . Анналы дискретной математики. Том. 29. Северная Голландия. ISBN  0-444-87916-1 . МР   0859549 .
  2. ^ Данцер, Л.; Грюнбаум, Б .; Клее, В. (1963). «Теорема Хелли и ее родственники». Выпуклость . Учеб. Симп. Чистая математика. Том. 7. Американское математическое общество . стр. 101–179. См., в частности, стр. 109.
  3. ^ Каратеодори, К. (1911). «Об области изменения констант Фурье положительных гармонических функций» . Rendiconti del Circolo Matematico di Palermo (1884–1940) (на немецком языке). 32 (1): 193–217 [см. стр. 200 внизу]. дои : 10.1007/BF03014795 . S2CID   120032616 .
  4. ^ Стейниц, Эрнст (1913). «Условно сходящиеся ряды и выпуклые системы». Дж. Рейн Анжью. Математика . 1913 (143): 128–175. дои : 10.1515/crll.1913.143.128 . S2CID   120411668 .
  5. ^ Леонард, И. Эд; Льюис, Дж. Э. (2016). «3.3 Выпуклые оболочки». Геометрия выпуклых множеств . Хобокен, Нью-Джерси: Уайли Блэквелл. ISBN  978-1-119-02266-4 .
  6. ^ Эгглстон, Х.Г. (1958). Выпуклость . Издательство Кембриджского университета. дои : 10.1017/cbo9780511566172 . ISBN  9780511566172 . См. стр. 40–41.
  7. ^ Насоди, Мартон; Полянский, Александр (2021). «Перрон и Фробениус встречают Каратеодори». Электронный журнал комбинаторики . 28 (3). arXiv : 1901.00540 . дои : 10.37236/9996 . S2CID   119656227 .
  8. ^ Барань, Имре; Карасев, Роман (20 июля 2012 г.). «Заметки о числе Каратеодори». Дискретная и вычислительная геометрия . 48 (3): 783–792. arXiv : 1112.5942 . дои : 10.1007/s00454-012-9439-z . ISSN   0179-5376 . S2CID   9090617 .
  9. ^ Адипрасито, Карим; Барань, Имре; Мустафа, Набиль Х.; Терпаи, Тамаш (28 августа 2019 г.). «Теоремы Каратеодори, Хелли и Тверберга без размерности». arXiv : 1806.08725 [ math.MG ].
  10. ^ Jump up to: а б с Барань, Имре (1 января 1982 г.). «Обобщение теоремы Каратеодори» . Дискретная математика . 40 (2–3): 141–152. дои : 10.1016/0012-365X(82)90115-7 . ISSN   0012-365X .
  11. ^ Монтехано, Луи; Фабила, Руй; Брачо, Хавьер; Барани, Имре; Ароча, Джордж Л. (1 сентября 2009 г.). «Очень красочные теоремы » Дискретная и вычислительная геометрия . 42 (2): 142–154. дои : 10.1007/s00454-009-9180-4 . ISSN   1432-0444 .
  12. ^ Jump up to: а б Мустафа, Набиль Х.; Рэй, Саураб (6 апреля 2016 г.). «Оптимальное обобщение теоремы Красочного Каратеодори» . Дискретная математика . 339 (4): 1300–1305. дои : 10.1016/j.disc.2015.11.019 . ISSN   0012-365X .
  13. ^ Менье, Фредерик; Мюльцер, Вольфганг; Саррабезолль, Полина; Стейн, Янник (01 января 2017 г.), «Радуга в конце линии? Формулировка PPAD красочной теоремы Каратеодори с приложениями», Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2017 г. , Материалы , Общество промышленной и прикладной математики, стр. 1342–1351, arXiv : 1608.01921 , doi : 10.1137/1.9781611974782.87 , ISBN  978-1-61197-478-2 , S2CID   5784949

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

[ редактировать ]
  • Экхофф, Дж. (1993). «Теоремы типа Хелли, Радона и Каратеодори». Справочник по выпуклой геометрии . Том. А, Б. Амстердам: Северная Голландия. стр. 389–448.
  • Мустафа, Набиль; Менье, Фредерик; Гоаок, Ксавьер; Де Лоэра, Хесус (2019). «Дискретные, но вездесущие теоремы Каратеодори, Хелли, Спернера, Такера и Тверберга». Бюллетень Американского математического общества . 56 (3): 415–511. arXiv : 1706.05975 . дои : 10.1090/bull/1653 . ISSN   0273-0979 . S2CID   32071768 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8a3727a1e2d73f84c7a74cbb68c7d771__1720461840
URL1:https://arc.ask3.ru/arc/aa/8a/71/8a3727a1e2d73f84c7a74cbb68c7d771.html
Заголовок, (Title) документа по адресу, URL1:
Carathéodory's theorem (convex hull) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)