跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2019年8月実施 筆記試験 第1問

Author​

tomfluff

Description​

点列 をこの順に結んでできる凸 角形が与えられたとき、その凸 角形の三角形分割とは、その内部を重なりなく三角形に分割する方法のことである。

まずは、凸 角形の三角形分割の数を求める。その数を と書く。例えば、 = 2 である。

(1) の値を答えよ。

(2) を の各式を用いて書き表せ。ただし、 とする。

(3) 任意の に対する を求めるアルゴリズムは、以下のような疑似コードで表現できる。 ① に当てはまるコードを答えよ。またこのアルゴリズムの計算量（オーダー）を答えよ。

C[2] = 1; C[3] = 1;
for(i=4...n)
    C[i] = 0;
for(i=4...n)
    for(j=0...i-3)
        [        ①        ]
return C[n];

次に、凸 角形のコスト最小三角形分割を求める。ここで、三角形分割のコストとは、構成する三角形のコストの和であるとし、三角形のコストとはその三角形を構成する辺のコストの和であるとする。 また、凸 角形を構成する任意の 頂点 と を結ぶ辺のコスト はすべて与えられているものとする。

(4) 与えられた凸 角形のコスト最小三角形分割を求める問題を、小問題に分けて解いていくことを考える。 頂点 から時計回りに 個の頂点を訪問し、 に戻ってくる経路によって囲まれる多角形について、コスト最小の三角形分割のコストを と書くことにする（下図参照）。 ここで、 が についてすべて計算済みであるとして、 を と の式で表せ。ただし、 とする。またその状況を説明する図も付して示せ。

(5) 上記 (4) で得られた関係式を用いて、任意の凸 角形の三角形分割の最小コストを求めるアルゴリズムの疑似コードを、10 行程度で示せ。またその計算量（オーダー）を答えよ。

Description (English)​

Given a convex n-gon made by connecting a point sequence in this order, a triangulation of the convex n-gon is a way of dividing its interior into triangles without overlap.

First, we count the number of triangulations of a convex n-gon. We denote the number as : For example, .

Answer the values of , , and .

Represent as a function of , , , ..., and . We define and .

The following pseudo-code implements an algorithm for computing for arbitrary . Answer the code that fills [ ① ]. Also answer the computational complexity (order) of the algorithm.

C[2] = 1; C[3] = 1;
for(i=4...n)
    C[i] = 0;
for(i=4...n)
    for(j=0...i-3)
        [        ①        ]
return C[n];

Next, we find the triangulation of a convex n-gon with a minimum cost. Here, the cost of a triangulation is defined as the sum of the cost of triangles in the triangulation, and the cost of a triangle is defined as the sum of the cost of the edges composing the triangle. Assume that all (), the costs of the edges connecting an arbitrary pair of vertices () of the n-gon, are given.

We consider solving the problem of finding a triangulation with a minimum cost by dividing the problem into subproblems. We denote as the cost of triangulating a polygon made by a path starting from , visiting vertices clockwise, and then coming back to (see the figure below). Assume that are all given for and . Represent as a function of and . We define . Also draw a figure explaining the situation.

Give approximately 10-line pseudo-code implementing an algorithm to compute the minimum cost of triangulating an arbitrary n-gon using the formula obtained in (4). Also answer the computational complexity (order) of the algorithm.

Kai​

(1)​

C[4]=2, C[3]=1, C[2]=1

C[5]=5

C[6]=14

C[7]=42

(2)​

Based on the representation we can see that:

(3)​

To complete the code we must add:

C[i] = C[i] + C[j+2]*C[i-j-1]

This will allow the sum to equal the equation found in (2).

(4)​

Based on the assumptions:

Basically, we choose an arbitrary triangle and using the fact all the other information is known. Then we look at the cost of the shape left of the triangle and right of it and combine with the cost of the triangle itself.

(5)​

The following cose assumes (based on no. 4) that and are given.

minimum_cost = +infinity
for (i=1...n-2)
    local_cost = E[0,i+1]+E[i+1,n-i+1]+D(0,i)+D(i,i+1)+D(i+1,i)
    minimal_cost = min(local_cost, minimal_cost)
return minimal_cost

In this code we go over all possible divisions of the shape n-gon into 2 subshapes and compute the minimum for these with the addition of the dividing edge. This uses the formula acquired in (4).

The time complexity for this, assuming that the information is known as stated in (4) is .

目录