學校課程/計算幾何

計算幾何 - 期中考練習

contents

  1. (15 points total)
    a. (10 points) Given a set of points that are presorted by their x-coordinate value, provide an algorithm that computes the convex hull of these points in O(n).
    b. (5 points) If more than 2 points are possibly on an edge of convex hull, explain briefly how your algorithm handles this case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) 
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    for(i = n-1, t = m+1; i >= 0; i--) 
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    return m - 1;
}

會將三點一線段的中間那一點替除掉，直到一個線段上只經過兩個點。

  1. (20 points total)
    a. (5 points) What are the types of event points in the plane sweep algorithm for line segment intersection problem?
    b. (10 points) Explain briefly when each type of event points is inserted to the event queue. Create a simple example (with 2 line segments) to demonstrate how it works.
    c. (5 points) When will the plane sweep algorithm for line segment intersection problem not suitable? Give a quantitative answer (i.e., describe your answer by using the Big-O notations). In addition, why is applying plane sweep algorithm on subdivision overlay in general a good idea?
  • 掃描時遇到的三種情況
    1. 碰到開始的左端點 (加入此線段)
    2. 碰到結束的右端點 (移除此線段)
    3. 碰到線段之間的交點 (預測下個最近的相交點後，將其包含這個交點線段移除後，重新加入)
  • 很簡單的，請參考上述三種情況繪製。
  • 當交集的數量在$\Theta(n^{2})$ 的時候，複雜度是$\Theta(n^{2}log n)$，還不如直接窮舉任兩個線段計算交點$\Theta(n^{2})$，就算要去重複，常數也比掃描線算法來得低。
  1. (20 points total)
    a. (10 points) Draw a simple polygon with 4 different types of vertices. Mark each vertex with its type. In addition, which two out of these 4 types are NOT allowed in a y-monotone piece?
    b. (5 points) Mark the “helper” for each of the vertices in your part (a) simple polygon that are not allowed in a y-monotone piece.
    c. (5 points) The triangulation of a y-monotone piece (with n vertices) can be done in linear time. Explain briefly why.
  • start, split, end, merge, regular vertex 明明有五種！
  • split, merge vertex 不符合 y-monotone piece
  • 加入 helper，對於 split 而言要往下找 split 或者是 regular vertex 相連，對 merge 而言要往上找 merge 或者是 regular 相連。
  • 因為往左可以根據維護凹性在 O(n) 時間內完成三角化，同理往右走訪。
  1. (20 points total)
    a. (5 points) What is the worst-case time complexity for the algorithm that solves the 2-dimensional linear programming problem?
    b. (5 points) Simplex algorithm is known to solve the linear programming problem in Operational Research. Why don’t we simple apply Simplex algorithm for the 2-dimensional linear programming problem?
    c. (10 points) Let (H, c) be a linear program. We number the half-planes h1, h2,…, hn. Let Hi be the set of the first i constraints, together with the special constraints m1 and m2 (i.e., the bound so that the solution space is limited). Let vi be the optimal point in Hi that satisfies the constraints. Explain why vi = vi-1 if vi-1 is contained in hi.

*$O(n^{2})$ incremental LP problem，每加入一個半平面，都必須重新計算最佳交集。

  • Simplex algorithm O(n log n)，在 2D 限制下，可以做到 O(n)。
  • 其實這是一個廢話，因為 hi 加上去，只會讓最佳解更糟，如果最佳解沒變，那麼最佳解仍然維持。
  1. (15 points total)
    a. (10 points) Briefly explain what a “split node” is. Create a balanced one-dimensional search tree with 8 leave nodes to be “1”, “2”, “3”, “4”, “5”, “6”, “7”, and “8”, and a range query [2, 6] to show where the split node is and how it helps to find all numbers in the range.
    b. (5 points) Both kd-trees and range trees are designed to do range query. Give one scenario that the kd-trees should be used and another scenario that the range trees should be adopted.
1
2
3
4
5
6
7
8
9
           [4]
          /   \
         /     \
        /       \
     [2]        [6]
    /   \       / \
  [1]  [3]    [5]  \
  /\    /\     /\   \
[1][2][3][4] [5][6] [7]

找到其中一邊的 split node 的寫法如下：

1
2
3
4
5
6
v = root
while v is not leaf && (r <= xv || xv' > l)
    if l <= xv'
        v = lc(v)
    else
        v = rc(v)

最後我們找到兩個 split node [1], [7]，在兩個 split node 之間的葉節點都是答案，對於葉節點可以利用建造時，使用一個 linked list 去完成。

  • 對於多維度範圍查找用 range tree 最好，可以保證在$O(log^{d} n)$ 以內找到解，kd-tree 在這種情況很容易退化。
  • 對於最鄰近點搜索則是使用 kd-tree 最好，range tree 反而沒辦法支持這種操作。
  1. (20 points)
    a. (5 points) Draw the trapezoidal map of the following given figure. Note that the bounding box is provided already. (Give each trapezoid a number, which will be used in part (b).)
    b. (10 points) Follow the algorithm to construct the search structure D for the trapezoidal map in part a). The segments are inserted in the order of s4, s3, s2, and s1.
    c. (5 points) In the trapezoidal algorithm, the endpoints of line segments are assumed to have different x-coordinate value (i.e., so-called general position). While a method was provided to relax this constraint, explain briefly why the composite-number method (i.e., transform (x, y) to (x|y, y|x)) which has been used in kd-trees and range trees to deal with the similar constraint was not adopted?
  • 因為它們是 range query，對於相同的 x 值仍然要算相同，利用偏斜的效果不利於操作。