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

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

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

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

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

Ссылки

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

[m02-1] Перейти обратно: ^а ^б Матушек, Иржи (2002), Лекции по дискретной геометрии , Тексты для аспирантов по математике , Springer-Verlag, стр. 30, ISBN 978-0-387-95373-1

[tv05-2] Тот, Геза; Валтр, Павел (2005), «Теорема Эрдеша-Секереша: верхние оценки и связанные с ними результаты», Комбинаторная и вычислительная геометрия , Матем. наук. Рез. Инст. Опубл., т. 1, с. 52, Кембридж: Кембриджский университет. Пресс, стр. 557–568, МР 2178339.

[dhow06-3] Дейнеко Владимир Георгиевич; Хоффманн, Майкл; Окамото, Ёсио; Воегингер, Герхард Дж. (2006), «Задача коммивояжера с небольшим количеством внутренних точек», Operations Research Letters , 34 (1): 106–110, doi : 10.1016/j.orl.2005.01.002 , MR 2186082

[mr08-4] Мюльцер, Вольфганг; Роте, Гюнтер (2008), «Триангуляция с минимальным весом NP-трудна», Журнал ACM , 55 (2), статья A11, arXiv : cs.CG/0601002 , doi : 10.1145/1346330.1346336

[k80-5] Клинчек, Г.Т. (1980), «Минимальные триангуляции полигональных областей», Анналы дискретной математики , 9 : 121–123, doi : 10.1016/s0167-5060(08)70044-x , ISBN 9780444861115

[es35-6] Эрдос, Пол ; Секерес, Джордж (1935), «Комбинаторная проблема в геометрии» , Compositio Mathematica , 2 : 463–470.

[v95-7] Валтр, П. (1995), «Вероятность того, что n случайных точек находятся в выпуклом положении», Discrete & Computational Geometry , 13 (3–4): 637–643, doi : 10.1007/BF02574070 , MR 1318803

[flvs01-8] Фордж, Дэвид; Лас Верньяс, Мишель ; Шухерт, Питер (2001), «10 точек в измерении 4, проективно не эквивалентных вершинам выпуклого многогранника», Комбинаторная геометрия (Luminy, 1999), European Journal of Combinatorics , 22 (5): 705–708, doi : 10.1006 /eujc.2000.0490 , МР 1845494

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]