볼록 선체 : 알려진 점 수 자체가 아닌 점

주어진 점 집합 S (크기가 n)에서 볼록 선체를 계산하는 알고리즘을 찾아야합니다. 정확히 볼록 선체를 형성하는 정확히 6 점에서 S까지입니다.볼록 선체 : 알려진 점 수 자체가 아닌 점

무엇이 가장 좋고 가장 효율적인 방법은입니까?

S (n은 6 점)에서 O (n^6)을 취하고 O (n)을 취할 볼록 선체인지 확인하는 모든 가능한 점들의 조합을 생성하려고 생각했습니다. 그러나 매우 나쁜 총 런타임으로 이어집니다. 더 좋은 방법이 있어야합니다. 어떤 힌트?

사이드 노트로, nC6은 O (n^6)이 아니라 O (n) –

입니다. –

https://en.wikipedia.org/wiki/Convex_hull_algorithms을 확인하십시오. –

단지 6 점이 볼록한 선체에있는 경우 Jarvis March 또는 Gift-wrapping 알고리즘이 매우 효율적입니다. h은 볼록 선체에있는 점의 수인 O(nh) 시간에서 실행됩니다.

2016-07-07 10:19:19

이 답변을 제공해 주셔서 감사합니다. –

h = 6은 상수이기 때문에이 문제는 O (n) 알고리즘이므로 주어진 문제에 대해 최적 일 가능성이 높습니다. 각 점을 한 번만 봐야합니다. 즉, 문제의 복잡도는 Ω (n). –

Graham Scan에서 O(nlogn)에 비해 시간 복잡도가 O(nh)이기 때문에 Jarvis March/Gift-wrapping 알고리즘이 매우 빠릅니다.

생각보다 빠른 알고리즘은 O(nlogh)에서 실행되는 Chan의 알고리즘 일 뿐이지 만 h은 매우 작으므로 그 차이는 매우 미미합니다. Chan의 알고리즘 here에 대해 자세히 알아보십시오.

2016-07-07 14:45:25 MathBunny

답변