Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Опукла оболонка



План:


Введення

Опуклою оболонкою множини X називається найменше опукле безліч, що містить X . "Найменше безліч" тут означає найменший елемент по відношенню до вкладення множин, тобто таке опукле безліч, що містить дану фігуру, що він утримується в будь-якому іншому опуклому безлічі, що містить дану фігуру.

Зазвичай опукла оболонка визначається для підмножин векторного простору над числами і на відповідних афінних просторах (зокрема в евклідовому просторі).

Опукла оболонка множини X звичайно позначається \ Operatorname {Conv} X .


1. Приклад

Опукла оболонка: приклад з ласо

Уявіть собі дошку, до якої вбито - але не по саму шляпку - багато цвяхів. Візьміть мотузку, зв'яжіть на ній ковзаючу петлю ( ласо) і накиньте її на дошку, а потім затягніть. Мотузка оточує всі цвяхи, але стосується вона тільки деяких, найбільш зовнішніх. Ті цвяхи, яких вона стосується, складають опуклу оболонку для всієї групи цвяхів [1].


2. Властивості

  • X - Опукле безліч тоді і тільки тоді, коли \ Operatorname {Conv} X = X .
  • Для довільного підмножини лінійного простору X існує єдина опукла оболонка \ Operatorname {Conv} X - Це перетин всіх опуклих множин, що містять X .
  • Опуклою оболонкою кінцевого набору точок на площині є опуклий плоский багатокутник (у вироджених випадках - відрізок або крапка), причому його вершини є підмножиною вихідного набору точок. Аналогічний факт вірний і для кінцевого набору точок у багатовимірному просторі.
  • Опукла оболонка X дорівнює перетину всіх півпросторів, що містять X .

3. Варіації і узагальнення

Опуклою оболонкою функції f називають таку функцію \ Operatorname {Conv} f , Що

\ Operatorname {epi} \; \ operatorname {Conv} f = \ operatorname {Conv} \; \ operatorname {epi} f ,

де epi f - надграфік функції f.

Варто відзначити зв'язок поняття опуклої оболонки функції з перетворенням Лежандра неопуклих функцій. Нехай f * - перетворення Лежандра функції f. Тоді якщо \ Operatorname {Conv} f -Власна функція (приймає кінцеві значення на непорожня множина), то

f ^{**} = \ overline {\ operatorname {Conv}} f


\ Overline {\ operatorname {Conv}} f - Опукле замикання f, тобто функція, надграфік якої є замиканням надграфіка f.


Література

  • Половинкин Е. С, Балашов М. В. Елементи опуклого і сильно опуклого аналізу. - М .: Физматлит, 2004. - 416 с. - ISBN 5-9221-0499-3.
  • Прапаратов Ф., Шеймос М. Обчислювальна геометрія: Вступ = Computational Geometry An introduction - М .: Світ, 1989. - С. 478.
  • Кормен, Томас Х., Лейзерсон, Чарльз І., Ривест, Рональд Л., Штайн, Кліфорд. Глава 33. Обчислювальна геометрія / / Алгоритми: побудова й аналіз = Introduction to Algorithms - 2-e видання. - М .: "Вільямс", 2005. - ISBN 5-8459-0857-4.
  • Ласло М. Обчислювальна геометрія та комп'ютерна графіка на C + + - М .: БІНОМ, 1997. - С. 304.
  • Ананій В. Левітін Глава 3. Метод грубої сили: Пошук опуклої оболонки. / / Алгоритми: введення в розробку та аналіз = Introduction to The Design and Analysis of Aigorithms - М .: "Вільямс", 2006. - С. 157-157. - ISBN 0-201-74395-7.

Примітки

  1. Даніель Хельпер, курс "Побудова алгоритмів", Хайфський університет.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Опукла функція
Оболонка
Зовнішня оболонка
Серозна оболонка
Перекриття-оболонка
Слизова оболонка
Електронна оболонка
Географічна оболонка
Оболонка операційної системи
© Усі права захищені
написати до нас
Рейтинг@Mail.ru