적어도 비교 / 대수 트리 모델에서는 그럴 것 같지 않습니다. 먼저 정의 :

점 집합 어떠한 경우 볼록 점 위치에있는 나머지 점의 볼록 조합으로 기록 될 수 없다 .P P피

$P$피

$P$P

$P$

이제 숫자 집합 이 모두 고유 한지 확인하려면 시간이 걸립니다 (UNIQUENESS라고 함). 이러한 숫자 세트가 주어지면 점 세트

반복되는 숫자가 없으면 점은 볼록한 위치에 있습니다.Ω ( n log n ) n X P = { ( x , x 2 ) | x ∈ X } .n

$n$Ω(nlogn)

$\Omega(n \log n)$n

$n$X

$X$

$$P = \{ (x, x^2) | x \in X\}.$$

반복되는 숫자가있는 경우,이 반복 된 숫자는 나머지 점의 볼록한 조합으로 기록 될 수있는 점에 해당합니다. 즉, 포인트가 볼록한 위치에 있지 않습니다.

즉, 점 세트가 볼록한 위치에 있는지를 결정하는 것은 UNIQUENESS만큼 어렵습니다.

답변