작은 삼각형으로 된 폴리곤 분할하기

Question

나는 X 개의 꼭지점을 가진 다각형을 가지고 있습니다. 다각형은 이미 X-2 삼각형으로 삼각 분할됩니다. 다각형의 정점이 100000 개라고 가정 해 봅시다. 어떻게 그것을 2 개의 다각형으로 나누습니까? 그 중 하나의 꼭지점 수는 65535 이하입니다 (더 클 수는 없습니다).

Answer 1

이중 그래프 (각 삼각형에 대한 노드, 인접한 삼각형에 대한 호)는 트리입니다. 이 트리를 탐색하여 각 노드가 결정한 하위 트리에있는 노드 수를 추적 할 수 있습니다. 노드의 차수는 3 이하이기 때문에 2/3 목표를 달성 할 수 있어야합니다.