Pozycja wypukła

W geometrii dyskretnej i obliczeniowej mówi się , że zbiór punktów na płaszczyźnie euklidesowej lub w wielowymiarowej przestrzeni euklidesowej znajduje się w położeniu wypukłym lub wypukłym niezależnym , jeśli żaden z punktów nie może być przedstawiony jako wypukła kombinacja pozostałych. Skończony zbiór punktów znajduje się w położeniu wypukłym, jeśli wszystkie punkty są wierzchołkami ich otoczki wypukłej . Mówiąc bardziej ogólnie, rodzina zbiorów wypukłych znajduje się w pozycji wypukłej, jeśli są one parami rozłączne i żaden z nich nie jest zawarty w wypukłej otoczce pozostałych.

Założenie wypukłej pozycji może ułatwić rozwiązanie niektórych problemów obliczeniowych. Na przykład problem komiwojażera , NP-trudny dla dowolnych zbiorów punktów na płaszczyźnie, jest trywialny dla punktów w położeniu wypukłym: optymalna trasa to wypukła powłoka. Podobnie triangulacja planarnych zbiorów punktów z minimalną wagą jest NP-trudna dla dowolnych zbiorów punktów, ale możliwa do rozwiązania w czasie wielomianowym przez programowanie dynamiczne dla punktów w pozycji wypukłej.

Erdősa – Szekeresa gwarantuje, że każdy zbiór $punktów$ pozycji ogólnej (żadnych trzech w linii) w dwóch lub więcej wymiarach ma co najmniej logarytmiczną liczbę punktów w pozycji wypukłej. Jeśli punkty są wybierane równomiernie losowo w kwadracie jednostkowym , prawdopodobieństwo, że znajdują się one w pozycji wypukłej, wynosi n {\ displaystyle $}$

$${\ Displaystyle \ lewo ({\ binom {2n-2} {n-1}} / n! \ prawo) ^ {2}.}$$

Problem McMullena prosi $d)}$ maksymalną liczbę $($ re ) $}$$($ -wymiarowa przestrzeń rzutowa ma rzutową transformację do zbioru w położeniu wypukłym. Znane granice to ${\ Displaystyle 2d + 1 \ równoważnik \ nu (d) \ równoważnik 2d + \ lceil (d + 1) / 2 \rceil}$ .