평면의 n 지점 세트가 o (nlogn) 시간에 볼록한 n 다각형을 형성하는지 테스트 n 다각형을 형성하는지 여부, 즉

평면에 n 개의 점이 주어졌고 볼록한 n 다각형을 형성하는지 여부, 즉 모두 볼록 껍질에 있는지 확인하려고한다고 가정합니다. 누군가가 o (nlogn) 시간에, 즉 CH를 계산하지 않고이 작업을 수행하는 방법을 알고 있는지 궁금합니다.

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

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

$P$

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

반복되는 숫자가 없으면 점은 볼록한 위치에 있습니다. $n$

$Ω (n \log n)$

Ω(nlog⁡n)

$n$

$X$

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

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

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

$O (n l o g n)$

O(nlogn)

점의 순서를 알면 시퀀스의 각 점에서 다음 점까지의 각도는 단조로운 것이어야합니다. 이것은 필요한 조건을 형성하고 충분한 것으로 생각합니다.

내부 포인트를 얻는 것은 독자를위한 연습으로 남습니다.

$O (n l o g n)$

O(nlogn)

How IT