Выпуклое положение

В дискретной и вычислительной геометрии набор точек на евклидовой плоскости или многомерном евклидовом пространстве называется выпуклым или независимым , если ни одна из точек не может быть представлена ​​как выпуклая комбинация других. ^[1] Конечный набор точек находится в выпуклом положении, если все точки являются вершинами их выпуклой оболочки . ^[1] В более общем смысле, семейство выпуклых множеств называется выпуклым, если они попарно не пересекаются и ни одно из них не содержится в выпуклой оболочке других. ^[2]

Предположение о выпуклом положении может облегчить решение некоторых вычислительных задач. Например, задача коммивояжера , NP-трудная для произвольных наборов точек на плоскости, тривиальна для точек в выпуклом положении: оптимальный маршрут — это выпуклая оболочка. ^[3] Аналогично, триангуляция минимального веса плоских наборов точек NP-трудна для произвольных наборов точек, ^[4] но разрешима за полиномиальное время с помощью динамического программирования для точек в выпуклом положении. ^[5]

Теорема Эрдёша –Секереша гарантирует, что каждый набор точек в общем положении (никаких трех в ряд) в двух или более измерениях имеет по крайней мере логарифмическое число точек в выпуклом положении. ^[6] Если точки выбираются равномерно случайным образом в единичном квадрате , вероятность того, что они находятся в выпуклом положении, равна ^[7] ${\displaystyle n}$ ${\displaystyle n}$ $${\displaystyle \left({\binom {2n-2}{n-1}}/n!\right)^{2}.}$$

Задача МакМаллена требует максимального числа, такого, что каждый набор точек в общем положении в -мерном проективном пространстве имеет проективное преобразование в набор в выпуклом положении. Известные границы . ^[8] ${\displaystyle \nu (d)}$ ${\displaystyle \nu (d)}$ ${\displaystyle d}$ ${\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }$

Ссылки

1. Matoušek, Иржи (2002), Лекции по дискретной геометрии, Тексты для выпускников по математике , Springer-Verlag, стр. 30, ISBN 978-0-387-95373-1
2. Tóth, Géza; Valtr, Pavel (2005), "Теорема Эрдёша-Секереша: верхние границы и связанные с ней результаты", Комбинаторная и вычислительная геометрия , Math. Sci. Res. Inst. Publ., т. 52, Кембридж: Cambridge Univ. Press, стр. 557–568, MR  2178339
3. Дейнеко, Владимир Г.; Хоффманн, Майкл; Окамото, Ёсио; Вёгингер, Герхард Дж. (2006), «Задача коммивояжера с несколькими внутренними точками», Operations Research Letters , 34 (1): 106–110, doi :10.1016/j.orl.2005.01.002, MR  2186082
4. Мульцер, Вольфганг; Роте, Гюнтер (2008), «Триангуляция минимального веса NP-трудна», Журнал ACM , 55 (2), Статья A11, arXiv : cs.CG/0601002 , doi :10.1145/1346330.1346336
5. Клинчек, ГТ (1980), «Минимальные триангуляции многоугольных областей», Annals of Discrete Mathematics , 9 : 121–123, doi :10.1016/s0167-5060(08)70044-x, ISBN 9780444861115
6. Эрдеш, Пол ; Секерес, Джордж (1935), «Комбинаторная проблема в геометрии», Compositio Mathematica , 2 : 463–470.
7. Вальтр, П. (1995), «Вероятность того, что n случайных точек находятся в выпуклом положении», Дискретная и вычислительная геометрия , 13 (3–4): 637–643, doi : 10.1007/BF02574070 , MR  1318803
8. Фордж, Дэвид; Лас Верньяс, Мишель ; Шухерт, Питер (2001), «10 точек в размерности 4, не проективно эквивалентных вершинам выпуклого многогранника», Комбинаторные геометрии (Luminy, 1999), Европейский журнал комбинаторики , 22 (5): 705–708, doi : 10.1006/eujc.2000.0490 , MR  1845494