빠른 선체 알고리즘에 의한 convex convex hull 컴퓨팅

Question

전산 기하학을 배우고 있으며, convex hull을 계산하기위한 빠른 선체 알고리즘에 대한 주제를 배우기 시작했습니다. 나는 질문을 가지고 있는데, 만약 내가 알고리즘이 최악의 시간 복잡성을 가질 2D 점 (말하자면 10 점)의 집합을 그렸으면 어떻게 할 것인가? 포인트가 무엇인지 알아내는 쉬운 방법이 있습니까?

빠른 선체 알고리즘의 의사 코드

Answer 1

here을 찾을 수 있습니다 나는 아무 거부 이제까지 주어진 점은 볼록 다각형을 형성 할 때, 즉 발생하지 때 QuickHull의 최악의 경우는 추측 파티션은을 때 가장 불균형 한

각도를 기하학적으로 줄이면서 원을 따라 점을 찍을 수 있습니다.

Answer 2

최악의 경우 시간 복잡도 동작을 생성 할 수 있습니다 점 세트를 건설하는 것은 당신이 공부하는 재료에 주어진 특정 의사에 따라 달라집니다.

Quickhull의 최악 복잡도 O (N 2⁾이며, 평균의 경우 성능 O (NlogN)이다. 당신이 보았을 지 모르겠지만, 퀵홀은 분단 및 정복 전략을 따릅니다. 따라서, 후자 (즉,보다 양호한) 시간 복잡성을 달성하는 것은 문제를 2 개의 유사한 크기의 (이상적으로는 동일한) 하위 문제로 나눌 수 있는지에 달려있다. 분할 단계가 균형을 이루지 않고 2 개의 하위 문제 요소의 수가 크게 다를 경우 알고리즘은 N 번 반복해야합니다. 다시 말하면, 각각의 재귀 적 단계에서, 문제의 크기는 원래 문제의 크기의 일부분으로 줄이는 대신에 일정한 양만큼 줄어들 것이다.

사용자가 제공 한 의사 코드는 가장 낮은 X 좌표 (즉, 가장 왼쪽 및 오른쪽 끝점)가있는 점을 경계로 사용하여 공간을 2로 나눕니다. 이상적으로 이것은 점을 두 개의 똑같은 큰 세트로 나누어야합니다. 그러나이 방법이 입력으로 주어진 특정 점에 비효율적으로 렌더링되면 어떻게 될까요? 그런 다음 각 단계에서 일정한 양의 점 (예 : c)을 제외하고 다른 절반에는 여전히 N-c 점이 포함됩니다. 따라서 문제는 O (N) 단계를 반복해야하며 2 차 복잡도로 끝납니다.

이러한 예제 중 하나는 포인트가있는 V 모양을 그리는 것이라고 생각합니다. 아래에 나와 있습니다.

(0, 5) 
(10, 5) 
(1, 4) 
(9, 4) 
(2, 3) 
(8, 3) 
(3, 2) 
(7, 2) 
(4, 1) 
(6, 1) 
(5, 0)