볼록 위치

이산형 및 계산형 기하학에서 유클리드 평면 또는 고차원 유클리드 공간의 점 집합은 다른 점의 볼록 결합으로 나타낼 수 없는 경우 볼록 위치 또는 볼록 독립된 위치에 있다고 한다.^[1]모든 점이 볼록한 선체의 정점일 경우 유한한 점 집합은 볼록한 위치에 있다.^[1]보다 일반적으로 볼록한 세트의 집단은 쌍방향으로 분리되어 있고 다른 세트의 볼록한 선체에 들어 있지 않으면 볼록한 위치에 있다고 한다.^[2]

볼록한 위치를 가정하면 특정 계산 문제를 더 쉽게 해결할 수 있다.예를 들어, 비행기의 임의적인 지점 집합에 대한 여행 판매원 문제인 NP-hard는 볼록한 위치에 있는 지점의 경우 사소한 것으로, 최적의 투어는 볼록한 선체라는 것이다.^[3]마찬가지로 평면 점 세트의 최소 중량 삼각형은 임의 점 세트의 경우 NP-hard이지만 ^[4]볼록한 위치에 있는 점의 동적 프로그래밍에 의해 다항 시간 내에 해결할 수 있다.^[5]

Erdős-Szekeres 정리는 2개 이상의 차원에 $있는{\displaystyle }$ n ${\displaystyle n}$ 포인트의$$ 모든 세트가 볼록한 위치의 포인트 수를 최소한 가지고 있음을 보장한다.^[6]단위 사각형에서 무작위로 n ${\displaystyle n}$개의$$ 점을 균일하게 선택한 경우 볼록한 위치에 있을 확률은^[7]

$${\displaystyle \left \binom {2n-2}{n-1}/n!\right)^{2}}$$

McMullen 문제는 $최대{\displaystyle }$ 숫자 $\nu {\displaystyle }$( ${\displaystyle d}$) ${\displaystyle \nu (d)}$을(를) 요구하여 d ${\displaystyle d}$차원$$ 투영 공간에서 모든 $\nu {\displaystyle }$(${\displaystyle d)}$가 일반 위치에 있도록$$ 한다.알려진 한계는 $2{\displaystyle \mathrm{}}$ ${\displaystyle d}$+ ${\displaystyle 1}$ ${\displaystyle \le }$ ${\displaystyle (d}$) ≤ (${\displaystyle d}$ )${\displaystyle \le }$ 2${\displaystyle }$d +${\displaystyle +}$(${\displaystyle \mathrm{d}}$+ 1 ) / ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rceil }$ (d) $\d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil$} 입니다$.$^[8]

참조