Конвексни скуп

У геометрији, подскуп Еуклидовог простора, или специфичније афини простор над реалним бројевима, је конвексан ако, са било које две тачке, он повезује цео линијски сегмент који их повезује. Еквивалентно, конвексни скуп или конвексни регион је подскуп који пресеца сваку линију у једном линијском сегменту (вероватно празном).^[1]^[2] На пример, чврста коцка је конвексни скуп, док све што је шупље или има удубљење, на пример, облик полумесеца, није конвексно.

Граница конвексног скупа је увек конвексна крива. Пресек свих конвексних скупова који садрже дати подскуп $А$ Еуклидовог простора назива се конвексни омотач $А$ . То је најмањи конвексни скуп који садржи $А$ .

Конвексна функција је реално вредносна функција дефинисана на интервалу са својством да је његов епиграф (скуп тачака на или изнад графикона функције) конвексни скуп. Конвексна минимизација је потпоље оптимизације које изучава проблем минимизације конвексних функција над конвексним скуповима. Прва грана матемакиа посвећена изучавању својстава конвексних скупова и конвексних функција се назива конвексна анализа.

Појам конвексног скупа може се генерализовати, као што је описано у даљем тексту.

Дефиниције уреди

Функција је конвексна, ако и само ако њен епиграф, регион (обојен зелено) изнад њеног графикона (приказан плавом линијуом), је конвексан сет.

Нека је $С$ векторски простор или афини простор над реалним бројевима, или, генералније, над неким уређеним пољем. Овим су обухваћени Еуклидови простори, који су афини простори. подскуп $C$ од $С$ је конвексан ако је за свако $x$ и $y$ у $C$ , линијски сегмент који повезује $x$ и $y$ укључен у $C$ . То значи да афина комбинација $(1 - т) x + тy$ припада $C$ , за свако $x$ и $y$ у $C$ , и $т$ на интервалу $[0, 1]$ . То подразумева да је конвексност (својство да је конвексан) инваријантна под афиним трасформацијама. Тиме се исто тако подразумева да је конвексни скуп у реалном или комплексном тополошком векторском простору повезан путањом, и стога повезан.

Скуп $C$ је стриктно конвексан ако је свака тачка на линијском сегменту који повезује $x$ и $y$ изузев крајњих тачака у унутрашњости $C$ .

Скуп $C$ је апсолутно конвексан ако је конвексан и балансиран.

Конвексни подскупови из $Р$ (скупа реалних бројева) су интервали и тачке из $Р$ . Неки примери конвексних подскупова Еуклидске равни су чврсти правилни многоуглови, чврсти троуглови и пресеци чврстих троуглова. Неки примери конвексних подскупова Еуклидског тродимензионалног простора су Архимедова тела и правилни полиедри. Полиедри Кеплер-Пуансоа су примери неконвексних скупова.

Неконвексни скуп уреди

Скуп који није ковексан се назива неконвексни скуп. Многоугао који није конвексни полигон се понекад назива конкавни полигон,^[3] а неки извори генералније користе термин конкавни скуп са значењем неконвексни скуп,^[4] мада та употреба већином није дозвољена.^[5]^[6]

Комплемент конвексног скупа, као што је епиграф конкавне функције, се понекад назива реверзни конвексни скуп, посебно у контексту математичке оптимизације.^[7]

Референце уреди

^ Моррис, Царла C.; Старк, Роберт M. Фините Матхематицс: Моделс анд Апплицатионс (на језику: енглески). Јохн Wилеy & Сонс. стр. 121. ИСБН 9781119015383. Приступљено 5. 4. 2017.
^ Кјелдсен, Тинне Хофф. „Хисторy оф Цонвеxитy анд Матхематицал Программинг” (ПДФ). Процеедингс оф тхе Интернатионал Цонгресс оф Матхематицианс (ИЦМ 2010): 3233—3257. дои:10.1142/9789814324359_0187. Архивирано из оригинала (ПДФ) 11. 8. 2017. г. Приступљено 5. 4. 2017.
^ МцЦоннелл, Јеффреy Ј. (2006), Цомпутер Грапхицс: Тхеорy Инто Працтице, стр. 130, ИСБН 0-7637-2250-2 .
^ Wеисстеин, Ериц W. „Цонцаве”. МатхWорлд.
^ Такаyама, Акира (1994), Аналyтицал Метходс ин Ецономицс, Университy оф Мицхиган Пресс, стр. 54, ИСБН 9780472081356, „Ан офтен сеен цонфусион ис а "цонцаве сет". Цонцаве анд цонвеx фунцтионс десигнате цертаин цлассес оф фунцтионс, нот оф сетс, wхереас а цонвеx сет десигнатес а цертаин цласс оф сетс, анд нот а цласс оф фунцтионс. А "цонцаве сет" цонфусес сетс wитх фунцтионс.”
^ Цорбае, Деан; Стинцхцомбе, Маxwелл Б.; Земан, Јурај (2009), Ан Интродуцтион то Матхематицал Аналyсис фор Ецономиц Тхеорy анд Ецонометрицс, Принцетон Университy Пресс, стр. 347, ИСБН 9781400833085, „Тхере ис но суцх тхинг ас а цонцаве сет.”
^ Меyер, Роберт (1970), „Тхе валидитy оф а фамилy оф оптимизатион метходс” (ПДФ), СИАМ Јоурнал он Цонтрол анд Оптимизатион, 8: 41—54, МР 0312915 .

Литература уреди

Андреw, А. M. (1979), „Анотхер еффициент алгоритхм фор цонвеx хуллс ин тwо дименсионс”, Информатион Процессинг Леттерс, 9 (5): 216—219, дои:10.1016/0020-0190(79)90072-3
Артин, Емил (1967), „2.5. Неwтон'с Полyгон”, Алгебраиц Нумберс анд Алгебраиц Фунцтионс, Гордон анд Бреацх, стр. 37—43, МР 0237460
Ауел, Асхер (2019), „Тхе матхематицс оф Граце Мурраy Хоппер” (ПДФ), Нотицес оф тхе Америцан Матхематицал Социетy, 66 (3): 330—340, МР 3889348
Авис, Давид; Бремнер, Давид; Сеидел, Раимунд (1997), „Хоw гоод аре цонвеx хулл алгоритхмс?”, Цомпутатионал Геометрy, 7 (5-6): 265—301, МР 1447243, дои:10.1016/С0925-7721(96)00023-5
Бáрáнy, Имре; Катцхалски, Меир; Пацх, Јáнос (1982), „Qуантитативе Хеллy-тyпе тхеоремс”, Процеедингс оф тхе Америцан Матхематицал Социетy, 86 (1): 109—114, МР 663877, дои:10.2307/2044407
Басцх, Јулиен; Гуибас, Леонидас Ј.; Херсхбергер, Јохн (1999), „Дата струцтурес фор мобиле дата”, Јоурнал оф Алгоритхмс, 31 (1): 1—28, ЦитеСеерX 10.1.1.134.6921  , МР 1670903, дои:10.1006/јагм.1998.0988
Биркхофф, Гарретт (1935), „Интегратион оф фунцтионс wитх валуес ин а Банацх спаце”, Трансацтионс оф тхе Америцан Матхематицал Социетy, 38 (2): 357—378, МР 1501815, дои:10.2307/1989687
Броwн, К. Q. (1979), „Воронои диаграмс фром цонвеx хуллс”, Информатион Процессинг Леттерс, 9 (5): 223—228, дои:10.1016/0020-0190(79)90074-7
де Берг, M.; ван Кревелд, M.; Овермарс, Марк; Сцхwарзкопф, О. (2008), Цомпутатионал Геометрy: Алгоритхмс анд Апплицатионс (3рд изд.), Спрингер
Цхан, Тимотхy M. (2012), „Тхрее проблемс абоут дyнамиц цонвеx хуллс”, Интернатионал Јоурнал оф Цомпутатионал Геометрy анд Апплицатионс, 22 (4): 341—364, МР 2994585, дои:10.1142/С0218195912600096
Цханг, Ј. С.; Yап, C.-К. (1986), „А полyномиал солутион фор тхе потато-пеелинг проблем”, Дисцрете & Цомпутатионал Геометрy, 1 (2): 155—182, МР 834056, дои:10.1007/БФ02187692
Цхазелле, Бернард (1985), „Он тхе цонвеx лаyерс оф а планар сет”, ИЕЕЕ Трансацтионс он Информатион Тхеорy, 31 (4): 509—517, МР 798557, дои:10.1109/ТИТ.1985.1057060
Цхазелле, Бернард (1993), „Ан оптимал цонвеx хулл алгоритхм ин анy фиxед дименсион” (ПДФ), Дисцрете & Цомпутатионал Геометрy, 10 (1): 377—409, ЦитеСеерX 10.1.1.113.8709  , дои:10.1007/БФ02573985
Цхен, Qинyу; Wанг, Гуозхао (март 2003), „А цласс оф Бéзиер-лике цурвес”, Цомпутер Аидед Геометриц Десигн, 20 (1): 29—39, дои:10.1016/с0167-8396(03)00003-7
Цранстон, M.; Хсу, П.; Марцх, П. (1989), „Смоотхнесс оф тхе цонвеx хулл оф планар Броwниан мотион”, Анналс оф Пробабилитy, 17 (1): 144—150, ЈСТОР 2244202, МР 972777
Демаине, Ерик D.; Гассенд, Блаисе; О'Роурке, Јосепх; Тоуссаинт, Годфриед Т. (2008), „Алл полyгонс флип финителy ... ригхт?”, Сурвеyс он Дисцрете анд Цомпутатионал Геометрy, Цонтемпорарy Матхематицс, 453, Провиденце, Рходе Исланд: Америцан Матхематицал Социетy, стр. 231—255, МР 2405683, дои:10.1090/цонм/453/08801
Дирнбöцк, Ханс; Стацхел, Хеллмутх (1997), „Тхе девелопмент оф тхе олоид” (ПДФ), Јоурнал фор Геометрy анд Грапхицс, 1 (2): 105—118, МР 1622664
Еделсбруннер, Херберт; Киркпатрицк, Давид Г.; Сеидел, Раимунд (1983), „Он тхе схапе оф а сет оф поинтс ин тхе плане”, ИЕЕЕ Трансацтионс он Информатион Тхеорy, 29 (4): 551—559, дои:10.1109/ТИТ.1983.1056714
Гарднер, L. Террелл (1984), „Ан елементарy прооф оф тхе Руссо-Дyе тхеорем”, Процеедингс оф тхе Америцан Матхематицал Социетy, 90 (1): 171, МР 722439, дои:10.2307/2044692
Гел'фанд, I. M.; Капранов, M. M.; Зелевинскy, А. V. (1994), „6. Неwтон Полyтопес анд Цхоw Полyтопес”, Дисцриминантс, Ресултантс, анд Мултидименсионал Детерминантс, Матхематицс: Тхеорy & Апплицатионс, Биркхäусер, стр. 193—213, ИСБН 0-8176-3660-9, МР 1264417, дои:10.1007/978-0-8176-4771-1
Гетз, Wаyне M.; Wилмерс, Цхристопхер C. (2004), „А лоцал неарест-неигхбор цонвеx-хулл цонструцтион оф хоме рангес анд утилизатион дистрибутионс” (ПДФ), Ецограпхy, Wилеy, 27 (4): 489—505, дои:10.1111/ј.0906-7590.2004.03835.x
Грахам, Роналд L.; Yао, Ф. Францес (1983), „Финдинг тхе цонвеx хулл оф а симпле полyгон”, Јоурнал оф Алгоритхмс, 4 (4): 324—331, МР 729228, дои:10.1016/0196-6774(83)90013-5
Грüнбаум, Бранко (2003), Цонвеx Полyтопес, Градуате Теxтс ин Матхематицс (2нд изд.), Спрингер, ИСБН 9780387004242
Густин, Wиллиам (1947), „Он тхе интериор оф тхе цонвеx хулл оф а Еуцлидеан сет”, Буллетин оф тхе Америцан Матхематицал Социетy, 53: 299—301, МР 20800, дои:10.1090/С0002-9904-1947-08787-5

Спољашње везе уреди

Хазеwинкел Мицхиел, ур. (2001). „Цонвеx субсет”. Енцyцлопаедиа оф Матхематицс. Спрингер. ISBN 978-1556080104.
Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.

[1] Моррис, Царла C.; Старк, Роберт M. Фините Матхематицс: Моделс анд Апплицатионс (на језику: енглески). Јохн Wилеy & Сонс. стр. 121. ИСБН 9781119015383. Приступљено 5. 4. 2017.

[2] Кјелдсен, Тинне Хофф. „Хисторy оф Цонвеxитy анд Матхематицал Программинг” (ПДФ). Процеедингс оф тхе Интернатионал Цонгресс оф Матхематицианс (ИЦМ 2010): 3233—3257. дои:10.1142/9789814324359_0187. Архивирано из оригинала (ПДФ) 11. 8. 2017. г. Приступљено 5. 4. 2017.

[3] МцЦоннелл, Јеффреy Ј. (2006), Цомпутер Грапхицс: Тхеорy Инто Працтице, стр. 130, ИСБН 0-7637-2250-2 .

[4] Wеисстеин, Ериц W. „Цонцаве”. МатхWорлд.

[5] Такаyама, Акира (1994), Аналyтицал Метходс ин Ецономицс, Университy оф Мицхиган Пресс, стр. 54, ИСБН 9780472081356, „Ан офтен сеен цонфусион ис а "цонцаве сет". Цонцаве анд цонвеx фунцтионс десигнате цертаин цлассес оф фунцтионс, нот оф сетс, wхереас а цонвеx сет десигнатес а цертаин цласс оф сетс, анд нот а цласс оф фунцтионс. А "цонцаве сет" цонфусес сетс wитх фунцтионс.”

[6] Цорбае, Деан; Стинцхцомбе, Маxwелл Б.; Земан, Јурај (2009), Ан Интродуцтион то Матхематицал Аналyсис фор Ецономиц Тхеорy анд Ецонометрицс, Принцетон Университy Пресс, стр. 347, ИСБН 9781400833085, „Тхере ис но суцх тхинг ас а цонцаве сет.”

[7] Меyер, Роберт (1970), „Тхе валидитy оф а фамилy оф оптимизатион метходс” (ПДФ), СИАМ Јоурнал он Цонтрол анд Оптимизатион, 8: 41—54, МР 0312915 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]