Выпуклое положение - Convex position

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

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

В Теорема Эрдеша – Секереса гарантирует, что каждый набор п указывает в общая позиция (нет трех в строке) имеет по крайней мере логарифмическое количество точек в выпуклом положении.[6] Если п точки выбираются равномерно случайным образом в единичный квадрат, вероятность того, что они находятся в выпуклом положении, равна[7]

.

Рекомендации

  1. ^ а б Матушек, Иржи (2002), Лекции по дискретной геометрии, Тексты для выпускников по математике, Springer-Verlag, стр. 30, ISBN  978-0-387-95373-1.
  2. ^ Тот, Геза; Валтр, Павел (2005), "Теорема Эрдеша-Секереса: оценки сверху и связанные результаты", Комбинаторная и вычислительная геометрия, Математика. Sci. Res. Inst. Publ., 52, Кембридж: Cambridge Univ. Press, стр. 557–568, МИСТЕР  2178339.
  3. ^ Deĭneko, Владимир Г .; Хоффманн, Майкл; Окамото, Ёсио; Вегингер, Герхард Дж. (2006), «Задача коммивояжера с небольшим количеством внутренних точек», Письма об исследованиях операций, 34 (1): 106–110, Дои:10.1016 / j.orl.2005.01.002, МИСТЕР  2186082.
  4. ^ Мульцер, Вольфганг; Роте, Гюнтер (2008), «Триангуляция с минимальным весом является NP-сложной», Журнал ACM, 55 (2), статья A11, arXiv:cs.CG/0601002, Дои:10.1145/1346330.1346336.
  5. ^ Клинчек, Г. Т. (1980), "Минимальные триангуляции многоугольных областей", Анналы дискретной математики, 9: 121–123, Дои:10.1016 / s0167-5060 (08) 70044-х.
  6. ^ Эрдеш, Пол; Секерес, Джордж (1935), «Комбинаторная задача геометрии», Compositio Mathematica, 2: 463–470.
  7. ^ Валтр, П. (1995), "Вероятность того, что п случайные точки находятся в выпуклом положении », Дискретная и вычислительная геометрия, 13 (3–4): 637–643, Дои:10.1007 / BF02574070, МИСТЕР  1318803.