Skip to content

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2022年8月実施 問題10

Author

zephyr

Description

There are two points \(A\), \(B\) and \(2^n\) data points \(P_1, \cdots, P_{2^n}\) in a 2-dimensional Euclidean plane. Assume that the distance \(\epsilon\) between \(A\) and \(B\), and the distances \(a_1, \cdots, a_{2^n}\) between \(A\) and the data points are given. The distances \(b_1, \cdots, b_{2^n}\) between \(B\) and the data points are not given, but a function \(f(P_i, P_j)\) defined below can be used to identify the sign of \(b_i - b_j\) for \(1 \leq i < j \leq 2^n\).

\[ f(P_i, P_j) = \mathrm{sgn}(b_i - b_j) = \begin{cases} 1 & \text{if } b_i - b_j > 0 \\ 0 & \text{if } b_i - b_j = 0 \\ -1 & \text{if } b_i - b_j < 0 \end{cases} \]

Assume that \(|a_i - a_j| > \epsilon\) for any \(a_i, a_j\) \((1 \leq i \leq j \leq 2^n)\).

(1) Show the pseudo-code of an algorithm to sort \(P_1, \cdots, P_{2^n}\) by ascending order of the distances from \(A\) in \(O(n2^n)\) worst computational time.

(2) Explain why the worst computational time of the algorithm shown in (1) is \(O(n2^n)\).

(3) Prove that if \(a_i - a_j > 2\epsilon\) then \(b_i > b_j\).

(4) When \(P_1, \cdots, P_{2^n}\) are already sorted by ascending order of the distances from \(A\), show an algorithm to sort by ascending order of the distances from \(B\) that calls function \(f\) the minimum number of times, and evaluate that number of times.

Kai

(1) Pseudo-code to sort \(P_1, \cdots, P_{2^n}\) by ascending order of the distances from \(A\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sort_by_distances_from_A(points, distances_from_A):
    if len(points) <= 1:
        return points
    mid = len(points) // 2
    left_half = merge_sort_by_distances_from_A(points[:mid], distances_from_A[:mid])
    right_half = merge_sort_by_distances_from_A(points[mid:], distances_from_A[mid:])
    return merge(left_half, right_half, distances_from_A)

def merge(left, right, distances_from_A):
    sorted_points = []
    while left and right:
        if distances_from_A[left[0]] < distances_from_A[right[0]]:
            sorted_points.append(left.pop(0))
        else:
            sorted_points.append(right.pop(0))
    sorted_points.extend(left)
    sorted_points.extend(right)
    return sorted_points

points = [P_1, P_2, ..., P_{2^n}]
distances_from_A = [a_1, a_2, ..., a_{2^n}]
sorted_points = merge_sort_by_distances_from_A(points, distances_from_A)

P.S.: Quicksort can also be used to sort the points by distances from \(A\) in \(O(n2^n)\) worst computational time.

(2) Explain the worst computational time of the algorithm shown in (1) is \(O(n2^n)\)

The merge sort algorithm has a time complexity of \(O(k \log k)\), where \(k\) is the number of elements to sort because it divides the array into two halves and recursively sorts them in a time complexity of \(O(k)\) in each step. In this case, \(k = 2^n\), so the time complexity of the merge sort algorithm is \(O(n2^n)\).

(3) Prove that if \(a_i - a_j > 2\epsilon\) then \(b_i > b_j\)

Consider 2 triangles formed by points \(A\), \(B\), and \(P_i\), \(P_j\):

  • \(\triangle ABP_i\) with sides \(a_i\), \(b_i\), and \(\epsilon\)

  • \(\triangle ABP_j\) with sides \(a_j\), \(b_j\), and \(\epsilon\)

By the triangle inequality, we have:

\[ b_i + \epsilon \geq a_i \quad \text{and} \quad a_i + \epsilon \geq b_i \]

Given that \(a_i - a_j > 2\epsilon\), we can write:

\[ b_i + \epsilon \geq a_i > a_j + 2\epsilon \geq b_j + \epsilon \]

Therefore, \(b_i > b_j\).

(4) Algorithm to sort by ascending order of the distances from \(B\)

Given that \(|a_i - a_j| > \epsilon\) for any \(a_i, a_j\), we can find out that for any \(i\) (\(1 \leq i \leq 2^n-2\)), \(a_{i+2} - a_i > 2\epsilon\) since \(|a_{i+2} - a_i| = |a_{i+2} - a_{i+1} + a_{i+1} - a_i| \geq |a_{i+2} - a_{i+1}| + |a_{i+1} - a_i| > 2\epsilon\). This implies that \(b_{i+2} > b_i\) by the proof in (3).

Therefore, we can sort \(B_1, \cdots, B_{2^n}\) by combining two sorted arrays \(B_{2i}\) and \(B_{2i+1}\), where \(B_{2i+1}\) and \(B_{2i}\) are sorted by \(a_{2i+1}\) and \(a_{2i}\), respectively.

So we can use the following algorithm to merge two sorted arrays \(B_{2i}\) and \(B_{2i+1}\):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def sort_by_distances_from_B(points, distances_from_A, distances_from_B):
    # 2^n points sorted by distances from A
    sorted_points = []
    i, j = 0, 0 # Pointers for the two sorted arrays

    # Merge the two sorted arrays of n/2 points each
    while i < len(points) and j < len(points):
        if f(points[i], points[j]) == 1: # b_i > b_j
            sorted_points.append(points[i])
            i += 1
        else:
            sorted_points.append(points[j])
            j += 1

    return sorted_points

Evaluation of the number of times the function \(f\) is called

The function \(f\) is called \(2^{n-1}\) times in the worst case. This is because the function \(f\) is called for each pair of points in the two sorted arrays of \(2^{n-1}\) points each. The function \(f\) is called \(2^{n-1}\) times to compare the distances between the points in the two arrays.

Knowledge

排序算法 算法 复杂度分析 几何 三角不等式

难点解题思路

  • 通过归并排序方法来排序点集 \(P_1, \cdots, P_{2^n}\)，利用三角不等式证明点与点之间距离的关系，提供了新的思路来求解几何问题。
  • 利用归并排序和冒泡排序的结合，优化了排序过程中函数调用次数。

解题技巧和信息

  • 对于复杂度分析，归并排序和冒泡排序是常见的有效方法。
  • 使用几何和三角不等式的知识可以帮助解决关于点距离的问题。
  • 在已知一个点集的部分顺序信息时，可以利用该信息减少计算量，优化算法。

重点词汇

  • Sort 排序
  • Merge 归并
  • Triangle inequality 三角不等式
  • Euclidean distance 欧几里得距离
  • Computational complexity 计算复杂度

参考资料

  1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein - Chapter on Sorting and Order Statistics
  2. "Algorithms" by Robert Sedgewick and Kevin Wayne - Chapter on Sorting