가능한 가장 작은 주위의 주어진 점 집합의 볼록한 선체 또는 2 개의 볼록 선체

Question

평면에서 n> = 3 점이 주어집니다. 우리는 이러한 조건을 충족 하나 또는 두 개의 다각형을 찾고 있습니다 :

1. 다각형 또는 그 다각형 중 적어도 하나의 경계에 위치한 점의 지정된 세트의 모든 지점.
2. 모든 다각형의 모든 꼭지점은 주어진 점 중 하나에 있습니다.
3. 다각형은 제로 영역을 가질 수 없습니다.

발견 된 다각형의 전체 둘레 중 가능한 가장 작은 값을 계산하십시오.

최저 경계선을 가진 다각형을 찾는 데는 문제가 없지만 최저 경계선을 가진 두 개의 다각형을 찾는 효과적인 해결책을 찾을 수 없습니다. (n> = 300)

나는 그것을 해결하는 방법을 알아 내는데 도움이 될만한 힌트가 필요합니다.

Answer 1

첫 번째 단계는 볼록 선체를 계산하는 것입니다. 볼록 선체 H의 점을 p0, p1, p2, p3, ..., pn, p0라고 가정합니다. 최적의 convext 선체 A와 B는이 목록에서 부분 집합 pA와 pB를 포함한다고 가정합시다. 그러면 pA와 pB는 H를 두 지점으로 나눔으로써 얻어진다.

이제 H 만 O (n^2) 방식으로 점을 나눌 수 있음을 알 수 있습니다.

완전한 대답을 원하지 않으므로 안부를 전 해주고 있습니다.