볼록 다각형 의 최 적 화 된 삼각형 분할 문제

볼록 다각형 의 최 적 화 된 삼각형 분할 문제
문제 설명
    다각형 은 평면 상의 세그먼트 선형 폐 곡선 이다.다각형 은 일련의 수미 가 연 결 된 직선 구간 으로 구 성 된 것 이다.다각형 을 구성 하 는 각 직선 구간 을 이 다각형 의 변 이 라 고 한다.다각형 이 두 변 을 연결 하 는 연결 점 을 다각형 의 정점 이 라 고 한다.다각형 의 변 사이 에 연결 정점 외 에 다른 공공 점 이 없다 면 이 다각형 을 간단 한 다각형 이 라 고 한다.간단 한 다각형 은 평면 을 세 부분 으로 나 누 었 다. 다각형 안에 둘러싸 인 모든 점 은 다각형 의 내 부 를 구성 했다.다각형 자체 가 다각형 의 경 계 를 구성한다.평면 상의 나머지 점 은 다각형 의 외 부 를 구성한다.간단 한 다각형 과 그 내부 가 폐 돌출 집합 을 구성 할 때 이 간단 한 다각형 을 돌출 다각형 이 라 고 부른다.즉, 돌출 다각형 경계 나 내부 의 임 의 두 점 으로 연 결 된 직선 구간 의 모든 점 은 이 돌출 다각형 의 내부 나 경계 에 있다 는 것 이다.
    일반적으로 다각형 정점 의 시계 반대 방향 서열 로 돌출 다각형, 즉 P = < v0 을 나타 낸다. ,v1 ,… ,vn - 1 > 은 n 개의 변 v0v 1, v1v 2,..., vn - 1vn 의 돌출 다각형 을 나타 내 는데 그 중에서 v0 = vn 을 약정 합 니 다.
    만약 에 vi 와 vj 가 다각형 에 인접 하지 않 은 두 개의 정점 이 라면 선분 vivj 는 다각형 의 현 이 라 고 부른다.현 은 다각형 을 돌출 된 두 개의 다각형 으로 나 누 었 다. ,vi+1 ,… ,vj > 와 < vj ,vj+1 ,… ,vi>。다각형 의 삼각 분할 은 다각형 을 서로 겹 치지 않 는 삼각형 의 현 으로 분할 하 는 집합 T 이다.그림 1 은 돌출 다각형 의 두 개의 서로 다른 삼각형 분할 이다.
(a)
(b)
그림 1 돌출 다각형 의 2 개의 서로 다른 삼각형 분할
    볼록 다각형 P 의 한 삼각형 분할 T 에서 각 현 은 서로 교차 하지 않 고 현 수가 가장 크다. 즉, P 의 어느 하나 가 T 에 없 는 현 은 반드시 T 중의 한 현 과 교차 해 야 한다.n 개의 정점 이 있 는 돌출 다각형 의 삼각 스 크 래 치 에는 마침 n - 3 개의 현 과 n - 2 개의 삼각형 이 있다.
    볼록 다각형 의 가장 좋 은 삼각형 분할 문 제 는 다음 과 같다. 볼록 다각형 P = < v0 ,v1 ,… ,vn - 1 > 다각형 의 변 과 현 으로 구 성 된 삼각형 에 정 의 된 권 함수ω。이 돌출 다각형 의 삼각형 분할 을 확정 하여 이 삼각형 분할 에 대응 하 는 권 리 를 분할 하 는 것 이 바로 삼각형 상의 권 리 를 최소 화 하 는 것 이다.
    삼각형 의 다양한 권 함수 W 를 정의 할 수 있 습 니 다.정의 ω(△ vivjvk) = | vivj | + | vivk | + | vkvj |, 그 중에서 | vivj | 점 vi 에서 vj 까지 의 오 씨 거리 입 니 다.이 권 함수 에 해당 하 는 가장 좋 은 삼각형 분할 은 최소 현 장삼 각 분할 이다.
주의: 이 문 제 를 해결 하 는 알고리즘 은 임의의 권 함수 에 적용 되 어야 합 니 다.
참고 해답
동적 계획 산법 으로 도 돌출 다각형 의 최 적 화 된 삼각형 분할 문 제 를 효과적으로 해결 할 수 있다.비록 이것 은 계산 기하학 문제 이지 만 본질 적 으로 행렬 의 곱 하기 최 적 화 된 계산 순서 문제 와 매우 비슷 하 다.
1. 삼각 분할 의 구조 와 관련 된 문제
    볼록 다각형 의 삼각 분할 과 표현 식 의 완전 괄호 방식 은 매우 밀접 한 관 계 를 가진다.보시 다시 피 행렬 의 곱 하기 최 적 화 된 계산 순서 문 제 는 행렬 체인 의 완전 괄호 방식 과 같다.이런 문제 들 간 의 상관 성 은 그들 이 대응 하 는 완전 이 진 트 리 의 동 구성 에서 볼 수 있다.이곳 의 이른바 완전 이 진 트 리 란 잎 결점 이외 의 모든 결점 의 도수 가 2 인 이 진 트 리 를 가리킨다.
    하나의 표현 식 의 완전 괄호 방식 은 완전 이 진 트 리 에 대응 하 며, 사람들 은 이 이 진 트 리 를 표현 식 의 문법 트 리 라 고 부른다.예 를 들 어 괄호 를 완전히 넣 은 행렬 의 곱 하기 (A1 (A2A 3) (A4 (A5A 6)) 와 대응 하 는 문법 트 리 는 그림 3 (a) 과 같다.
그림 3    표현 식 문법 트 리 와 삼각 분할 의 대응
    문법 트 리 의 모든 잎 은 표현 식 의 원 자 를 나타 낸다.문법 트 리 에 표현 식 E1 을 나타 내 는 왼쪽 하위 트 리 와 표현 식 Er 를 나타 내 는 오른쪽 하위 트 리 가 있 으 면 이 노드 를 뿌리 로 하 는 하위 트 리 로 표현 식 (E1Er) 을 표시 합 니 다.따라서 n 개의 원자 가 있 는 완전 괄호 표현 식 은 n 개의 잎 결점 이 있 는 유일한 문법 트 리 에 대응 하고 반대로 도 마찬가지 입 니 다.
    볼록 다각형 < v0 ,v1 ,… ,vn - 1 > 의 삼각 분할 도 문법 트 리 로 표시 할 수 있다.예 를 들 어 그림 3 (a) 에서 돌출 다각형 의 삼각형 부분 은 그림 3 (b) 에서 보 여 준 문법 트 리 로 표시 할 수 있다.이 문법 나무의 뿌리 결점 은 변 v0v 6 이 고 삼각형 분할 중의 현 은 나머지 내부 결점 을 구성한다.다각형 에서 v0v 6 변 을 제외 한 모든 변 은 문법 나무의 잎 결점 이다.나무 뿌리 v0v 6 는 삼각형 v0v3v 6 의 한 변 으로 이 삼각형 은 원래 의 다각형 을 3 개 부분 으로 나 누 었 다. 삼각형 v0v3v 6, 돌출 다각형 < v0 ,v1 ,… ,v3 > 와 볼록 다각형 < v3 ,v4 ,… ,v6>。삼각형 v0v3v 6 의 다른 두 변, 즉 현 v3v 6 와 v0v 3 를 뿌리 로 하 는 두 아들.그것들 을 뿌리 로 하 는 서브 트 리 는 각각 볼록 다각형 < v0 을 나타 낸다. ,v1 ,… ,v3 > 와 볼록 다각형 < v3 ,v4 ,… ,v6 > 의 삼각 분할.
    일반적인 상황 에서 n - 1 개의 잎 이 있 는 문법 나무 에 대응 하 는 돌출 n 변형 의 삼각형 분할반대로 n - 1 개의 잎 이 있 는 문법 나무 에 따라 해당 하 는 돌출 n 변형 의 삼각형 으로 나 눌 수 있다.즉, 돌출 n 변형 의 삼각 분할 과 n - 1 개의 잎의 문법 나무 사이 에 일일이 대응 하 는 관계 가 존재 한 다 는 것 이다.n 개 행렬 의 완전 괄호 곱 하기 와 n 개 잎의 문법 트 리 사이 에 일일이 대응 하 는 관계 가 존재 하기 때문에 n 개 행렬 의 완전 괄호 곱 하기 도 돌출 (n + 1) 변형 의 삼각형 분할 과 일일이 대응 하 는 관계 가 존재 한다.그림 3 의 (a) 와 (b) 는 이러한 대응 관 계 를 나타 내 는데 이때 n = 6.매트릭스 연속 곱 하기 A1A 2. A 6 의 모든 행렬 Ai 는 돌출 (n + 1) 변형 중의 한 변 vi - 1vi 에 대응 합 니 다.삼각 분할 중의 한 현 vivj, i < j - 1 은 행렬 의 곱 하기 Ai + 1. j 에 대응 합 니 다. 。
    사실 행렬 의 곱 하기 최 적 화 된 계산 순서 문 제 는 돌출 다각형 의 최 적 화 된 삼각형 분할 문제 의 특수 한 상황 이다.주어진 매트릭스 체인 A1A2.. An 에 대해 해당 하 는 돌출 (n + 1) 변형 P = < v0 을 정의 합 니 다. ,v1 ,… ,vn >, 행렬 Ai 와 돌출 다각형 의 변 vi - 1vi 를 일일이 대응 합 니 다.행렬 Ai 의 비트 가 pi - 1 이면×pi, i = 1, 2,..., n 은 삼각형 vivjvk 의 권한 편지 수 치 를 다음 과 같이 정의 합 니 다. ω(△vivjvk)=pipjpk。이 권 함수 의 정의 에 따라 돌출 다각형 P 의 최 적 화 된 삼각형 분할 에 대응 하 는 문법 트 리 는 행렬 체인 A1A 2. An 의 최 적 화 된 괄호 방식 을 제시 합 니 다.
2. 최 우수 서브 구조 성
    볼록 다각형 의 가장 좋 은 삼각형 분할 문 제 는 가장 좋 은 서브 구조 성 을 가지 고 있다.사실 돌출 (n + 1) 변형 P = < v0 ,v1 ,… ,vn > 의 가장 좋 은 삼각형 분할 T 는 삼각형 v0vkvn 을 포함 합 니 다. 1 ≤ k ≤ n - 1 이면 T 의 권 리 는 3 개 부분 권 의 합, 즉 삼각형 v0vkvn 의 권, 자 다각형 < v0 ,v1 ,… ,vk > 의 권리 와 < vk ,vk+1 ,… ,권 의 합.T 가 확정 한 이 두 개의 다각형 의 삼각 분할 도 가장 좋다 고 단언 할 수 있다. 왜냐하면 < v0 이 있 으 면 ,v1 ,… ,vk > 또는 < vk ,vk+1 ,… ,vn > 의 더 작은 권력 의 삼각 분할 은 T 가 가장 좋 은 삼각 분할 이 아 닌 모순 을 초래 할 수 있다.
3. 최 적 화 된 삼각 분할 에 대응 하 는 권 의 재 귀 구조
    우선, 정의 t [i, j], 1 ≤ i < j ≤ n, 돌출 자 다각형 < vi - 1 ,vi ,… ,vj > 의 최 적 화 된 삼각형 분할 에 대응 하 는 가중치, 즉 최 적 화 된 값.편리 함 을 위해 퇴화 된 다각형 < vi - 1 설치 ,vi > 가중치 0 이 있 습 니 다.이에 따라 계산 할 돌출 (n + 1) 변 다각형 P 에 대응 하 는 권 리 는 t [1, n] 로 정의 된다.
    t [i, j] 의 값 은 가장 좋 은 서브 구조의 성질 을 이용 하여 귀속 적 으로 계산 할 수 있다.퇴화 된 2 정점 다각형 의 가중치 가 0 이기 때문에 t [i, i] = 0, i = 1, 2, n.j 1 i ≥ 1 시, 자 다각형 < vi - 1 ,vi ,… ,vj > 적어도 세 개의 정점 이 있다.구조 적 성질 보다 가장 우수한 t [i, j] 의 값 은 t [i, k] 의 값 에 t [k + 1, j] 의 값 을 더 하고 △ vi - 1vkvj 의 값 을 더 하 며 i ≤ k ≤ j - 1 의 범위 내 에서 가장 작다.이로부터 t [i, j] 는 다음 과 같이 재 귀적 으로 정의 할 수 있다.
4. 최 우수 값 계산
    (2.3) 식 과 행렬 을 곱 하 는 가장 좋 은 계산 순서 문제 에서 m [i, j] 의 (2. l) 식 을 비교 하면 알 수 있 듯 이 권 함수 의 정 의 를 제외 하고 두 개의 재 귀 식 은 완전히 같다.따라서 m [i, j] 를 계산 하 는 알고리즘 MATRIXCHAIN_ORDER 는 아주 작은 수정 을 하면 t [i, j] 를 계산 하 는 데 완전히 적용 된다.
    아래 에 설명 한 계산 돌출 (n + 1) 변형 P = < v0 ,v1 ,… ,vn > 의 삼각 분할 최 적 화 된 가중치 의 동적 계획 알고리즘 MINIMUMWEIGHT_TRIANGLATION, 입력 은 볼록 다각형 P = < v0 ,v1,..., vn > 의 권 함수ω，출력 은 t [i, j] 와 t [i, k] + t [k + 1, j] +ω(△ vi - 1vkvj) 최 적 위치 (k =) s [i, j], 1 ≤ i ≤ j ≤ n.

Procedure MINIMUM_WEIGHT_TRIANGULATION(P,w)；
begin
  n:=length[p]-1;
  for i:=1 to n do t[i,i]:=0;
    for ll:=2 to n do
      for i:=1 to n-ll+1 do
        begin
          j:=i+ll-1;
          t[i,j]:=∞;
          for k:=i to j-1 do
            begin
              q:=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
              if q<t[i,j] then
                begin
                  t[i,j]:=q;
                  s[i,j]:=k;
                end;
            end;
        end;
  return(t,s);
end;

MATRIX 와CHAIN_ORDER 와 마찬가지 로 알고리즘 MINIMUMWEIGHT_TRIANGLATION 점용θ(n2) 공간, 시간 소모θ(n3)。
5. 구조 최 우수 삼각 분할
우리 가 본 바 와 같이 임의의 1 ≤ i ≤ j ≤ n, 알고리즘 MINIMUMWEIGHT_TRIANGLATION 은 각 자형의 다각형 < vi - 1 을 계산 하고 있 습 니 다. ,vi ,… ,vj > 의 가장 좋 은 삼각형 분할 에 대응 하 는 가중치 t [i, j] 와 동시에 s [i, j] 에서 이 가장 좋 은 삼각형 분할 에서 변 (또는 현) vi - 1vj 로 구 성 된 삼각형 의 세 번 째 정점 위 치 를 기록 했다.따라서 최 우수 서브 구조 성질 을 이용 하여 s [i, j], 1 ≤ i ≤ j ≤ n, 돌출 (n + l) 변형 P = < v0 ,v1 ,… ,vn > 의 가장 좋 은 삼각형 분할 은 쉽게Ο시간 내 에 구성 하 다.