Chapter 10

10.1

In Section 10.1 we solved the problem of finding all horizontal line segments in a set that intersect a vertical segment. For this we used an interval tree with priority search trees as associated structures. There is also an alternative approach. We can use a 1-dimensional range tree on the y-coordinate of the segments to determine those segments whose y-coordinate lies in the y-range of the query segment. The resulting segments cannot lie above or below the query segment, but they may lie completely to the left or to the right of it. We get those segments in O(logn) canonical subsets. For each of these subsets we use as an associated structure an interval tree on the x-coordinates to find the segments that actually intersect the query segment.

a. Give the algorithm in pseudocode.
b. Prove that the data structure correctly solves the queries.
c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

給 n 個水平線段，詢問垂直的線段與那些水平線段有相交，輸出所有有相交的線段。

a. Algorithm:

1. 對 n 個線段建造 interval tree，使用課本上 CONSTRUCTINTERVALTREE(l) 的做法。
2. 對 interval tree 上每一個 node 建造 Priority Search Tree，node 依照 x 劃分，分別對 node.x 的左右兩側建造 PST，距離 node.x 越遠的端點，其優先權越高，左右子樹依照 y-value 分兩堆。
3. 詢問調用 QUERYINTERVALTREE(v, qx)，得到相對應的 ndoe 後，查找每個 node 下的 Priority Search tree 與線段相交，調用 QUERYPRIOSEARCHTREE()。

b. Prove that the data structure correctly solves the queries.
上述的作法與 axis-parallel rectangular query window 相同。而此問題的詢問是 axis-parallel rectangular query window 的 subset，一個線段的詢問是 qx = qx’ 的情況，故得證。

c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

preprocessing time : O(n log n)
store space : O(n)
query time : O(log n + k)

前處理因 interval tree 最慘 T(n) = 2 T(n/2) + O(n) ，建造 PST 只需要 O(n) ，每個線段最多在兩個 PST 中，得到記憶體空間最多為 O(n) 。詢問最多為 interval tree 的深度 O(log n)

10.2

Let P be a set of n points in the plane, sorted on y-coordinate. Show that, because P is sorted, a priority search tree of the points in P can be constructed in O(n) time.

類似 bottom0up heap construction，已知 bottom-up heap 可在 O(n) 時間內完成。

假設最後的樹高 H，第 i 次的 bottom-up 會調整 2^H-i 個元素，每個元素最多下降 i 層。則

雖然要求左右子樹的 y 值要符合左小、右大，但由於已經根據 y 排好，bottom-up 時，保證調整的 shiftdown 操作會符合其性質。

10.6

Let I be a set of intervals on the real line. We want to be able to count the number of intervals containing a query point in O(logn) time. Thus, the query time must be independent of the number of segments containing the query point.

a. Describe a data structure for this problem based on segment trees, which uses only O(n) storage. Analyze the preprocessing time, and the query time of the data structure.
b. Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
c. Describe a data structure for this problem based on a simple binary search tree. Your structure should have O(n) storage and O(logn) query time. (Hence, segment trees are actually not needed to solve this problem efficiently.)

有 n 個 [l_i, r_i]，詢問一個點 x 被多少個區間包含，輸出為一個整數。

a. 使用 segment tree 儲存所有的 interval。

對於其 node(u) 會 cover(l, r) 的區間，紀錄有多少區間 cover(l, r)，最多有 2n 個葉節點，樹節點最多 4n 個，每個 node 只有一個額外的整樹紀錄區間個數。然而一個區間最多被拆分 O(log n) 個，依序插入需消耗共計 O(n log n) 時間。

preprocessing time : O(n log n)
query time : O(log n)
store space : O(n)

b. 使用 inteerval tree 處理 interval。

對於每個 node 分別對左右兩側建造平衡樹，這個平衡樹要支持某數字是第 k 大或第 k 小的操作。對於一個 node 而言，會有數個區間交 node.x，假設詢問點 qx 在 node.x 左側，則根據左側的平衡樹，查找 qx 是第 k 小，用以回報個數。每一個區間對多在 2 個平衡樹中，故空間複雜度為 O(n) 。

preprocessing time : O(n log n)
query time : O(log² n)
store space : O(n)

c. 使用 simple binary search tree。

1. 將 n 個線段的端點，共計 2n 個丟入 binary search tree。
2. 每一個 node 紀錄有多少個區間包含它，如果 node 是某個線段的右端點，則無視此區間的包含情況。
3. 對於每個詢問 qx，輸出 node = lower_bound(qx) 的包含結果。

將所有端點排序後，會得到 [a₀, a₁, a₂, …, a_2n]，每一個 node 的資訊是 [a_i, a_i+1) 的區間包含訊息。簡單地說，切成最小塊的相鄰資訊，與 segment tree 反過來的概念。

前處理使用 line sweep algorithm 掃描線算法，來找到每一個端點被多少個線段包含。掃描線算法需要 O(n log n) ，binary search tree 只需要 O(n) ，查找 lower_bound 只需要 O(log n) ，保證最多 2n 個端點，樹最多使用 O(n) 個空間。

preprocessing time : O(n log n + n) = O(n log n)
query time : O(log n)
store space : O(n)

10.7

a. We want to solve the following query problem: Given a set S of n disjoint line segments in the plane, determine those segments that intersect a vertical ray running from a point (qx,qy) vertically upwards to infinity. Describe a data structure for this problem that uses O(nlogn) storage and has a query time of O(logn+k), where k is the number of reported answers.
b. Now suppose we only want to report the first segment hit by the query ray. Describe a data structure for this problem with O(n) expected storage and O(logn) expected query time. Hint: Apply the locus approach

給定 n 個不相交的線段，詢問一點開始的射線，射線方向向 y 軸正向，輸出所有交到的線段。

a. 使用 segment tree，依照所有的端點的 x 值，接著對於每個 node 建造以 y 值得 binary search tree，儲存數個線段，因為不相交，保證 binary search tree 在 [xl, xr] 區間的所有線段都是單調的。每個線段最多切成 O(log n) ，故使用空間 O(n log n) ，詢問 O(log n + k) ，只須訪問 O(log n) 個節點，從 binary tree tree 最遠的開始往下輸出即可。

b. 只找第一個碰到的線段，使用 trapezoidal map 找到 point location，走訪 DG 其最後一個 segment below 的情況就是輸出結果。已知 trapezoidal map 在隨機增量算法中，expected size of search structure O(n) ，expected query time O(log n) 。

Chapter 11

11.1

In Chapter 1 we defined the convex hull of a set P of points as the intersection of all convex sets containing the points. In the current chapter we saw another definition: the convex hull of P is the set of all convex combinations of the points in P. Prove that these two definitions are equivalent, that is, prove that a point q is a convex combination of points in P if and only if q lies in every convex set containing P.

首先 convex combinations 指得是$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$，證明 q 會在所有的凸包集中，也就是 q 點相當於任抓幾點出來，會在這幾點形成的凸包中，公式計算類似物理上的質心計算。

(=>)$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$. Prove q lies in every convex set containing P.

• Base : $n = 2, q = \lambda_{1} p_{1} + \lambda_{2} p_{2}$, q lies on segment p₁p₂, which must be a subset of every convex set containing p₁, p₂.
• Suppose: $n \le k$ 均成立，當 n = k + 1 時$\lambda_{k+1} = 0$ 必定成立。

Hence, the point${q}' = \sum_{i=1}^{k} {\lambda_{i}}' p_{i}$ is convex combination of p₁, p₂, …, p_k, q’ lies every convex set containing the them.

every convex set containing p₁, p₂, …, p_k, q’. Since it also contains p_k+1 the set must contain q as a convex combination of two points.
(<=) Prove q lies in every convex set containing P =>$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$
In particular, q lies in the smallest convex set, the convex hull of P. Triangulate the convex hull, q must lie in one of the triangles$\triangle p_{1} p_{2} p_{3}$. Connect q to p₁, p₂, p₃. This partitions the triangle into tree smaller ones.

得證。

11.2

Prove that the worst case running time of algorithm CONVEXHULL is O(n3), and that there are sets of points where a bad choice of the random permutation makes the algorithm actually need Θ(n3) time.

CONVEXHULL 共有三層 for loop.

• LINE 7 如果每次的新加入的 p_i 都在 convex hull 外面，即 F_conflict(p_i) 非空。
• LINE 10$e \in \pounds$，而最多有 i - 1 個，投影的情況下，最多 i 個點都在凸包上，因此最多產生 i - 1 個 facets。
• LINE 18 對每個新加入的 facets 最多增加 n - i 個 conflict 點。

故最慘 O(n³)。

11.6

Describe a data structure that allows you to test whether a query point q lies inside a convex polytope with n vertices in R3. (Hint: Use the results from Chapter 6.)

快速判斷一個點是否在 3D convex hull 中。

• 方案一：3D point location by 3D trapezoidal map. 感覺非常難做，弄出很多柱狀體。
• 方案二：convex hull 最多會有 3n - 6 個面，最多有 3n - 6 個面不等式，判斷是否全在同一側 O(n) 。
• 方案三：將做好的 3D convex hull，將所有點投影到 x-y 平面，每一個梯形區域會由 2 個 convex hull 的面覆蓋，要不沒有面。對於投影的 2D 建造 trapezoidal map。query 一個點 q 時，先投影到 x-y 平面，找到所在的梯形區域，針對兩面的不等式進行判斷。預處理 O(n log n) ，詢問 O(log n) 。

11.8

Describe a randomized incremental algorithm to compute the intersection of half-planes, and analyze its expected running time. Your algorithm should maintain the intersection of the current set of half-planes. To figure out where to insert a new half-plane, maintain a conflict graph between the vertices of the current intersection and the half-planes that are still to be inserted.

• 維護半平面 hi 與 Sj 的相交資訊。

• add half-place
  繞外部 (半平面的另一側的凸包邊) 的 edge e，將 h_conflict(e) 移除掉 intersection(e, h_conflict(e)) in$\bar{h_{i}}$。
  期望值的複雜度依賴中間過程中產生的交集點個數。

• 假設 c(H, h) 表示 inter(H) 和 h 的 conflict vertice 個數。
  則$\sum_{i = 1}^{n} \left [ \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ]$－所有的花費。

對於每一個 vertice v 被創建的時間為 tc(v), 被移除的時間 td(v)。

得證。

Chapter 7

7.1

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Vor(P) has n−1 vertices

證明一個點個數 n > 3 的 Voronoi diagram，存在一個 cell 具有 n - 1 個頂點。

如圖所示，一個點放置在圓心，剩餘的 n - 1 個放置在圓周上。則中間的 cell 必然有 n - 1 個頂點。

7.3

Show that$\Omega (nlogn)$ is a lower bound for computing Voronoi diagrams by reducing the sorting problem to the problem of computing Voronoi diagrams. You can assume that the Voronoi diagram algorithm should be able to compute for every vertex of the Voronoi diagram its incident edges in cyclic order around the vertex.

證明 Voronoi diagram 的 lower bound$\Omega (nlogn)$，藉由 reduce 到 sorting problem。

關於 reduce 證明，將一個簡單、約束較少的問題 A，藉由一個合適的轉換，變成一個困難問題 B 的 subset，已知 A 的 lower bound，則 B 的 lower bound 至少與 A 相同。

1. 假設排序 n 個整數$x_{1}, x_{2}, ..., x_{n}$
2. 轉換成$(x_{1}, 0), (x_{2}, 0), ..., (x_{n}, 0)$ 將所有點放置在 x 軸上，並且額外增加一點$(\infty, 0)$。將 n + 1 個點找到 Voronoi diagram，對於$(\infty, 0)$ 的 cell 而言，恰好邊都是由另外 n 個點對應的 cell 構成 cell edge (相鄰)。假設儲存邊的順序為順或逆時針，則邊的順序等價排序結果。

最後如上圖所示，又已知轉換需要$O(n)$，sorting$\Omega (nlogn)$，則 Voronoi diagram 的 lower bound$\Omega (nlogn)$。

7.5

Give an example where the parabola defined by some site$p_{i}$ contributes more than one arc to the beach line. Can you give an example where it contributes a linear number of arcs?

如上圖所示$p_{i}$ 拉出的拋物線 (parabola) 有可能提供多個弧 (arc)。(最左側的點提供 2 個弧)

一個點$p_{i}$ 存有的 arc 數量與 cell$p_{i}$) 的頂點數量線性相關。由 exercose 7.1 得到最多$O(n)$ 的頂點。同理 arc 數量最多$O(n)$。

beach line 上的 arc 數最多為 Voronoi diagram 的 edge 數，又 Voronoi diagram 的 edge 最大數為$3n - 6$，也因此最多為$O(n)$

7.10

Let P be a set of n points in the plane. Give an$O(nlogn)$ time algorithm to find two points in P that are closest together. Show that your algorithm is correct.

Algorithm:

1. 建造 Voronoi Diagram by fortune’s algorithm$O(nlogn)$
2. 對於每一個 cell$p_{i}$) 檢查鄰居 cell$p_{neighbor}$)，計算$distance(p_{i}, p_{neighbor})$ 的結果。Voronoi diagram 的 edge 數$3n - 6$，每一條 edge 檢查只需要$O(1)$。$O(n)$

證明：每一個點所張開的 cell 只會與相鄰的 cell 最近，否則不符合 Voronoi diagram 的定義。

7.14

Show that the farthest point Voronoi diagram on n points in the plane has at most 2n−3 (bounded or unbounded) edges. Also give an exact bound on the maximum number of vertices in the farthest point Voronoi diagram.

• 歐拉公式$v - e + f = 2$
• 一個頂點至少三條邊。
• farthest point Voronoi diagram 的最多有 n - 2 個頂點。
  • 對於每一個頂點而言，通過其相鄰 cell 對應的點的外接圓，其圓包含所有平面點。
  • 這種圓最多 n - 2 個。
• 從隨機增量算法中得知，插入一個點時，最多增加一個 vertex (繞行時，會刪除對於 cell 相交兩個線段之間的所有 vertex，這種 vertex 至少一個，並且增加與線段的交點 1 個)。$v(3) = 1, v(n) = v(n-1) + 1 \text{ for } n > 3$
• 考慮增加一個虛點，連接所有 unbounded edge $v - e + f = 2 \Rightarrow (n-2+1) - e + n = 2 \Rightarrow e = 2n - 3$。

Chpater 9

9.2

The degree of a point in a triangulation is the number of edges incident to it. Give an example of a set of n points in the plane such that, no matter how the set is triangulated, there is always a point whose degree is n−1.

對於任意三角化的結果，總會有一個點的 degree = n - 1。

• 此點一定能用一條線區隔所有剩餘點。
• 剩餘 n - 1 個點，一定能滿足任兩點的連線不遮蔽其他的點。

example：n - 1 個點落在$y = e^{x}$ 上，且$x < p$，另外一點在$(p, q)$

9.4

Prove that the smallest angle of any triangulation of a convex polygon whose vertices lie on a circle is the same. This implies that any completion of the Delaunay triangulation of a set of points maximizes the minimum angle.

對於所有頂點共圓的凸多邊形，任何的三角化的最小角度都會相同。

1. 任何三角形必然是圓上三點。
2. 任何凸邊形的邊都會是一個三角形上的邊
3. 三角形的邊都是圓的弦，並且對應角度正比弦長大小。
4. 凸多邊形的最小弦長是多邊上的邊，又因一定會在三角形上，任何三角化一定包含這個最小角。

9.7

Prove that all edges of DG(Pr) that are not in DG(Pr−1) are incident to pr. In other words, the new edges of DG(Pr) form a star as in Figure 9.8. Give a direct proof, without referring to algorithm DELAUNAYTRIANGULATION.

對於新增加的邊$e$，只會與新加入的點$p_{r}$ 相連。

• 從 Voronoi diagram 等價 Delaunay triangulation，加入點的 cell，不會使其他兩個 cell 從沒相鄰變成相鄰。

• 對於$\Delta(p_{i}, p_{j}, p_{k})$ 之間加入$p_{r}$，由於$C(p_{i}, p_{j}, p_{k})$ 內部不存在任何點$C'(p_{i}, p_{r})$ (兩點當直徑)，得到$C' \subseteq C$，且$C'$ 內部不存在任何點，確定$\bar{p_{i} p_{r}}$ 屬於 Delaunay 上。同理$\bar{p_{j} p_{r}}$$\bar{p_{k} p_{r}}$。

• 由於$\Delta(p_{l}, p_{i}, p_{j})$ 原本是 Delaunay 上，如果 flip$\bar{p_{i} p_{j}}$，得到$C(p_{i}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$$C(p_{j}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$，確定$\bar{p_{r} p_{l}}$ 屬於 Delaunay 上。

• 也因此，對於增加的三角形進行檢查時，每次已經保證該三角形其中兩邊一定屬於 Delaunay 上，同時必然有$p_{r}$，flip 的邊一定會接到$p_{r}$ 上。遞迴得證。

9.11

A Euclidean minimum spanning tree (EMST) of a set P of points in the plane is a tree of minimum total edge length connecting all the points. EMST’s are interesting in applications where we want to connect sites in a planar environment by communication lines (local area networks), roads, railroads, or the like.

1. Prove that the set of edges of a Delaunay triangulation of P contains an EMST for P.
2. Use this result to give an O(nlogn) algorithm to compute an EMST for P.

對於歐幾里得距離的平面最小生成樹。

1. 證明 EMST 的 edge set 被 Delaunay triangulation 的 edge set 包含。(參考 wiki)
   目標： every edge not in a Delaunay triangulation is also not in any EMST

   • 最小生成樹的性質：任何一個 cycle 上的最重邊將不會在最小生成樹中。

   • Delaunay triangulation： If there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.

     對於鈍角三角形，最大邊必然不在 EMST 中，然而對於 Delaunay triangulation 性質，必須考慮他們兩點的 boundary (shared Voronoi edge) 是否存在。

     假設 p, q 之間沒有邊於 Delaunay，則對於任意通過 p, q 的圓都存在點 r 在圓內，從性質中發現 r 到 p, q 的距離一定小於 p q 之間的距離。同時在 EMST 中，p q r 三點會構成鈍角三角形，其中 p q 是最大邊，p q 之間必然沒有邊。

2. 找到 EMST 的$O(nlogn)$ 算法
   Algorithm:

   1. 利用 Delaunay triangulation 找到所有邊$O(nlogn)$
   2. 最多有 3n - 6 條邊，利用 MST 中的 kruskal’s algorithm$O(ElogE)$
      3.$E = O(3n-6) = O(n)$，得到$O(nlogn)$ 的做法。

9.13

The Gabriel graph of a set P of points in the plane is defined as follows:
p q Two points p and q are connected by an edge of the Gabriel graph if and only if the disc with diameter pq does not contain any other point of P.

1. Prove that DG(P) contains the Gabriel graph of P.
2. Prove that p and q are adjacent in the Gabriel graph of P if and only if the Delaunay edge between p and q intersects its dual Voronoi edge.
3. Give an O(nlogn) time algorithm to compute the Gabriel graph of a set of n points

Gabriel graph：任兩點之間為直徑的圓內若沒有其他點，則兩點之間有邊。

1. 證明 subgraph 關係。

• 根據 Theorem 9.6 (1) 任三點圓內$C(p_{i}, p_{j}, p_{k})$沒有其他點，但是$C(p_{i}, p_{j})$ 內部可能存有其他點 (如單純的 n = 3 的鈍角三角形)。找到$e_{p_{i}, p_{j}} \notin Gabriel \text{ but } e_{p_{i}, p_{j}} \in Delaunay$
  *$C(p_{i}, p_{j})$ 內部沒有其他點，則兩點之間必然有 shared Voronoi edge，符合 Theorem 9.6 (2)。得到 $\text{ if }e_{p_{i}, p_{j}} \in Gabriel \text{ , then } e_{p_{i}, p_{j}} \in Delaunay$，得證$g(P) \subseteq DG(P)$。

1. 如果$\bar{pq}$ 經過多個 Voronoi edge，則$\bar{pq}$ 上一點 x 滿足 $$\bar{xr} < \bar{xp}, \bar{xr} < \bar{xq} \\ \Rightarrow \angle rpx < \angle prx, \angle rqx < \angle xrq \text{(triangle)} \\ \text{let } \angle rpx = a, \angle prx = c, \angle rqx = b, \angle xrq = d \\ \Rightarrow a + b + c + d = 180^{\circ} \\ \Rightarrow c + d > 90^{\circ}$$

符合圓內角性質，點 r 一定在圓內，得證$e_{p_{i}, p_{j}} \notin Gabriel$。

1. 在 O(n logn) 時間內完成。
   Algorithm：

   1. 利用 Delaunay triangulation 找到所有邊$O(nlogn)$

   2. 將$e_{p{i}, p{j}} \in DG(P)$ 進行測試是否有點落在$C(p{i}, p{j})$$O(n)$

      只需要拿鄰居進行檢測，鄰居最多 2 個 (共邊的三角形)。

9.14

The relative neighborhood graph of a set P of points in the plane is defined as follows: Two points p and q are connected by an edge of the relative neighborhood graph if and only if

1. Given two points p and q, let lune(p,q) be the moon-shaped region p q lune(p,q) formed as the intersection of the two circles around p and q whose radius is d(p,q). Prove that p and q are connected in the relative neighborhood graph if and only if lune(p,q) does not contain any point of P in its interior.
2. Prove that DG(P) contains the relative neighborhood graph of P.
3. Design an algorithm to compute the relative neighborhood graph of a given point set.

整體而言類似 9.13。

1. 若 p, q 之間沒有邊，則 $$\exists r : d(p, q) > \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)) \\ \exists r : d(p, q) > d(p, r) \text{ and } d(p, q) > d(q, r)$$ AND 就是做交集操作，不知道該怎麼寫才好。
2. 與 9.14 依樣畫葫蘆，只是$lune(p, q) \subseteq C(p, q)$，則更暗示$\text{ if }e_{p_{i}, p_{j}} \in G \text{ , then } e_{p_{i}, p_{j}} \in Gabriel$
3. 速度是$O(n^{2})$，沒辦法單純看鄰居進行檢查。拿每一條邊進行 O(n) 窮舉。不過在分散式計算，整體是 O(n)。

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 值仍然要算相同，利用偏斜的效果不利於操作。

Master Theorem

1.$\text{if } log_{b}a < c, T(n) = \theta(n^{c})$
2.$\text{if } log_{b}a = c, T(n) = \theta(n^{c} log n)$
3.$\text{if } log_{b}a > c, T(n) = \theta(n^{log_{b}a})$

Extend Master Theorem

1.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha < -1, T(n) = \theta(n^{E})$
2.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha = -1, T(n) = \theta(n^{E} log_{b} log_{b}(n))$
3.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha > -1, T(n) = \theta(n^{E}(log_{b}n)^{\alpha + 1})$

Chapter 5

5.1

In the proof of the query time of the kd-tree we found the following
recurrence:
$$Q(n) = \begin{cases} O(1) & \text{ if } n = 1 \\ 2 + 2Q(n/4)& \text{ if } n > 1 \end{cases}$$
Prove that this recurrence solves to Q(n) = O(√n). Also show that Ω(√n) is a lower bound for querying in a kd-tree by defining a set of n points and a query rectangle appropriately.

1. by master theorem,$a = 2, b = 4, c = 0 \Rightarrow Q(n) = \Theta(\sqrt{n})$
   2.$\Omega(\sqrt{n})$ 是 kd-tree 的 lower_bound。如果 + 號存在的行都一直被執行，另外 - 號行都不會被執行，那麼複雜度就會達到$\Omega(\sqrt{n})$，要明白如何加上 report 則會更慢，必須將包含的點依序回報。找一個不包含所有點的細長矩形於正中央即可，每次循環切割到 x 時，保證會留下 n/4 個節點。

1
2
3
4
5
6
7
8
9
10
11
12
13

Algorithm: SEARCHKDTREE(v, R) 
if v is leaf
    report the points stored at v if it lies in R.
else
-	if region(lc(v)) contains R
        report subtree lc(v)
+	else if lc(v) intersects R
        SEARCHKDTREE(lc(v), R)
  
-	if region(rc(v)) contains R
        report subtree rc(v)
+ 	else if rc(v) intersects R
        SEARCHKDTREE(rc(v), R)

5.3

In Section 5.2 it was indicated that kd-trees can also be used to store sets of points in higher-dimensional space. Let P be a set of n points in d-dimensional space. In parts a. and b. you may consider d to be a constant.

1. Describe an algorithm to construct a d-dimensional kd-tree for the points in P. Prove that the tree uses linear storage and that your algorithm takes$O(n log n)$ time.
2. Describe the query algorithm for performing a d-dimensional range query. Prove that the query time is bounded by$O(n^{1−1/d} +k)$.
3. Show that the dependence on d in the amount of storage is linear, that is, show that the amount of storage is$O(dn)$ if we do not consider d to be a constant. Give the dependence on d of the construction time and the query time as well.

1
2
3
4
5
6
7
8
9

Algorithm : build(int k, int l, int r, int dep)
    if l > r
        return NULL
    m = (l + r)/2
    Node ret = median axis[k%K] of point[l, r] ----- O(n)
    split points[l, r] by median               ----- O(n), C++ std::nth_element()
    ret.lson = build((k+1)%K, l, m-1);
    ret.rson = build((k+1)%K, m+1, r);
    return ret;

1. 利用 median of medians 算法找到中位數，數據儲存用指針來完成搜索，不用移動資料。
   以上代碼根據遞迴公式$T(n) = 2T(n/2) + O(n) \Rightarrow T(n) = \Theta(n log n)$，而 kd-tree 是一個 full binary tree，每一個節點都代表一個實際資料，因此空間複雜度$O(n)$
2. 假設在 d 為空間，Q(n) 表示 n 個點的詢問，依序按照維度切割 (ex. x, y, z, x …)，現在只關注 x 軸上的切割，假設詢問範圍包含所有的 y, z，那麼在 2ed x 節點中，每一個節點具有$n/2^{d}$ 資料，而同一層會有$2^{d-1}$ 個 x 維度的子節點。然後遞迴詢問$2^{d-1}$ 所包含的範圍查找。
   藉由 master theorem,$a = 2^{d-1}, b = 2^{d}, c = 0 \Rightarrow Q(n) = \Theta(n^{1 - 1/d})$ $$Q(n) = \begin{cases} O(1) & \text{ if } n < 2^{d} \\ 2^{d-1} + 2^{d-1} Q(n/2^{d}) & \text{ if } n \geq 2^{d} \end{cases}$$
3. 如果 d 不是常數，每一個內部節點空間 O(d)，有 n 個節點則需 O(dn) 的儲存空間。詢問上，需要在 intersected 花 O(d) 時間決定是否存在交集、包含，再來判斷是否走訪子樹，因此詢問是$2dQ(n) = O(dn^{1-1/d})$，加上回報的效率為$2dQ(n) = O(dn^{1-1/d} + k)$。

5.5

Algorithm SEARCHKDTREE can also be used when querying with other ranges than rectangles. For example, a query is answered correctly if the range is a triangle.

a. Show that the query time for range queries with triangles is linear in the worst case, even if no answers are reported at all. Hint: Choose all points to be stored in the kd-tree on the line y = x.
b. Suppose that a data structure is needed that can answer triangular range queries, but only for triangles whose edges are horizontal, vertical, or have slope +1 or −1. Develop a linear size data structure that answers such range queries in O(n3/4+k) time, where k is the number of points reported. Hint: Choose 4 coordinate axes in the plane and use a 4-dimensional kd-tree.
c. Improve the query time to O(n2/3+k). Hint: Solve Exercise 5.4 first.

1. 最慘情況是 O(n)－詢問範圍為三角形。
   詢問的範圍如圖，所有點落在 y = x 上，三角形範圍是一個很貼近 y = x 的三角形，三角形並沒有包含任何一個點，卻與所有劃分的區域有交集，因此必須走訪所有節點。
2. 如果要支持三角形範圍查找 (三角形的邊要不垂直、平行、斜率 +1、斜率 -1)。找到一個詢問$O(n^{3/4} + k)$ 的資料結構。
   類似 kd-tree，但是輪替的標準為 x 軸 、 y 軸 、 斜率 1 、 斜率 -1 ，根據 5.3(b) 的公式，相當於 d = 4 的情況，得到$O(n^{1 - 1/4} + k) = O(n^{3/4} + k)$。
3. 加快到$O(n^{2/3} + k)$ 的詢問時間。
   在這裡想到是建立兩個 kd-tree，其中一個順序為 x 軸 、 斜率 1 、 斜率 -1 ，另一個順序為 y 軸 、 斜率 1 、 斜率 -1 。前者可以回答向上、向下三角形，後者回答向左、向右三角形。相當於 d = 3 的切割，最多拆成 4 個範圍查找$O(4n^{1 - 1/3} + k) = O(n^{2/3} + k)$。
   1. 在詢問矩形時，拆成四個三角形查找 (向上、向下、向左、向右三角形)
   2. 在詢問三角形時，拆成兩個三角形查找

5.9

One can use the data structures described in this chapter to determine whether a particular point (a,b) is in a given set by performing a range query with range [a : a]×[b : b].

1. Prove that performing such a range query on a kd-tree takes time O(logn).
2. What is the time bound for such a query on a range tree? Prove your answer.

1. 對於 kd-tree 所消耗的時間 O(log n) 說明。 $[a:a] \times [b:b]$ 並不會跨區間。在 SEARCHKDTREE(v, R) 函數中，Line SEARCHKDTREE(lc(v), R) 和 SEARCHKDTREE(rc(v), R) 只會有一個符合。$$Q(n) = \begin{cases} O(1) & \text{ if } n = 1 \\ 1 + Q(n/2) & \text{ if } n > 1 \end{cases}$$
2. 對於 kd-tree 所消耗的時間 O(d log n) 說明。
   首先能知道會先在第一維度探訪$[a:a]$ 的葉節點，中間經過 log n 個節點最後到葉節點，然後在其相對應的 y 軸 tree 中查找$[b:b]$ 也是 log n。因此是$O(\sum{i = 1}^{d} log n) = O(d log n)$

5.11

Let S1 be a set of n disjoint horizontal line segments and let S2 be a set
of m disjoint vertical line segments. Give a plane-sweep algorithm that
counts in O((n+m) log(n+m)) time how many intersections there are
in S1 ∪ S2.

給 n 個不相交的水平線段、m 個不相交的垂直線段，在 O((n+m) log (n+m)) 的時間內找到焦點個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Algorithm:
    1. sort all x-coordinate ----- O((n+m) log (n+m))
    2. sweep x from small to large, maintain a segment tree or range tree.
    for x = -oo to oo
        for each horizontal line (sx, y)-(ex, y) in x
            if sx = x
                1Drangetree.add(y) 				----- O(log (n+m))
        for each vertical line (x, sy)-(x, ey) in x
            ret += 1Drangetree.query(sy, ey) 	----- O(log (n+m))
        for each horizontal line (sx, y)-(ex, y) in x
            if ex = x
                1Drangetree.remove(y) 			----- O(log (n+m))
    return ret

Chapter 6

6.1

Draw the graph of the search structure D for the set of segments depicted
in the margin, for some insertion order of the segments.

雖然沒有加入順序的考量，但是手爆一個 17 個線段、平面空間 29 個的建造 … 也許有點瘋狂，用最簡單的由上而下掃描，造成一個傾斜的樹也是各種不容易。

6.2

Give an example of a set of n line segments with an order on them that
makes the algorithm create a search structure of size Θ(n2) and worst-case
query time Θ(n).

找到一個最慘空間$\Theta(n^{2})$，最慘詢問時間$\Theta(n)$。

n 個線段，將其中 n/2 放置在同一個水平線上，對於剩餘 n/2 個：

每次加入的順序 s1, s2, …, si，每次的線段的 x 值會包含前一個線段$s_{i}.lx < s_{i-1}.lx, s_{i}.rx > s_{i-1}.rx$，美加入一個線段，會增加 n/2 個內部節點，並且最大深度增加 1。總計加入 n/2 次，增加的節點數量 O(n/2 x n/2) = O(n^2)，深度 O(n/2) = O(n)。

6.5

Given a convex polygon P as an array of its n vertices in sorted order along the boundary. Show that, given a query point q, it can be tested in time O(logn) whether q lies inside P.

由於詢問次數相當多，必須將複雜度降到 O(log n)，採用的方式將凸包其中一個點當作基準，則如果在凸包的點而言，一定會落在某個以基點拉出的三角形內部中，為了方便計算，則可以拿外積的正負邊界上。得到可能的三角形後，從邊界中可以藉由外積計算是否同側。

採用射線法 O(n) 肯定是吃大虧的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

double 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 inside_convex(const Pt &p, Pt ch[], int n) {
    if(n < 3)
        return false;
    if(cross(ch[0], p, ch[1]) > eps)
        return false;
    if(cross(ch[0], p, ch[n-1]) < -eps)
        return false;
    
    int l = 2, r = n-1;
    int line = -1;
    while(l <= r) {
        int mid = (l + r)>>1;
        if(cross(ch[0],p, ch[mid]) > -eps) {
            line = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return cross(ch[line-1], p, ch[line]) < eps;
}

Chapter 3

3.2

A rectilinear polygon is a simple polygon of which all edges are horizontal or vertical. Let P be a rectilinear polygon with n vertices. Give an example to show that$\left \lfloor n/4 \right \rfloor$ cameras are sometimes necessary to guard it.

正交多邊形是其中一種多邊形，邊與邊之間不是平行就是垂直。至少需要 n/4 個攝影機才能監視每一個角落。

The rectilnear polygon would contain$\left \lfloor n/4 \right \rfloor$ parallel “alleys”. At least$\left \lfloor n/4 \right \rfloor$ cameras are needed because no cameras can see more than one alleys.

正交多邊形，可以產生$\left \lfloor n/4 \right \rfloor$ 個平行的走廊，每一個攝影機只能顧及一個走廊，因此得到一個最簡單的例子需要$\left \lfloor n/4 \right \rfloor$ 個攝影機。

3.7

Let P be a simple polygon with n vertices, which has been partitioned into monotone pieces. Prove that the sum of the number of vertices of the pieces is O(n).

證明一個 n 個節點的簡單多邊形，拆成多個 monotone pieces，節點總數仍然是 O(n)。

一個簡單多邊形可以三角化成 n - 2 個三角形，每個三角形都是一個 monotone piece，因此節點個數總和$3 * (n - 2) = O(n)$

證明一個簡單多邊形有 n 個頂點，可以切成 n - 2 個三角形。

• n = 3 時，T(3) = 1, 符合 T(n) = n - 2 成立
• 當 n = k 時，k >= 3, 且符合 T(n) = n - 2
• n = k + 1 時，T(n + 1) = T(n) + 1 = (n - 2) + 1 = n - 1，

切割的證明為，找到多邊形的最左側點，然後他一定是凸的，將相鄰兩點拉一條線，如果構成的三角形內部沒有其他點，則直接變成 n - 1 個節點的多邊形，如果裡面有點，則挑一個最靠近最左側點的那個點，將最左側那個點與其相連，這時劃分成兩個多邊形，保證算法一樣。

3.11

Give an efficient algorithm to determine whether a polygon P with n
vertices is monotone with respect to some line, not necessarily a horizontal
or vertical one.

請參考 [ACM 題目] 單調測試 的解法。

主要解法複雜度為 O(n log n)，採用角度掃描。

Chapter 4

4.2

Consider the casting problem in the plane: we are given polygon P and a 2-dimensional mold for it. Describe a linear time algorithm that decides whether P can be removed from the mold by a single translation.

1. 對於 P 的任一面$f_{i}$ 的法向量$\vec{n_{i}}$，找到一個移動向量$\vec{d}$，使其$\vec{n_{i}}$ 和$\vec{d}$ 張角全大於 90 度。也就是內積小於 0。

2. 給 {(n1x, n1y), (n2x, n2y), …}
   nix * dx + niyy * dy <= 0

3. 如果不單純派 dy = 1，調用 2DRANDOMIZEDBOUNDLP 判斷是否有解即可，不必最佳化其結果。

4.8

The plane z = 1 can be used to represent all directions of vectors in 3-dimensional space that have a positive z-value. How can we represent all directions of vectors in 3-dimensional space that have a non-negative z-value? And how can we represent the directions of all vectors in 3-dimensional space?

1.$z = 0 \cup z = 1$
2.$z = -1 \cup z = 1 \cup x = -1 \cup x = 1 \cup y = -1 \cup y = 1$，有人問說單純$z = -1 \cup z = 1$ 不就包含了所有方向嗎？但是我思考了一下收斂問題，這之間到底有沒有連續？極限上是相同，但是包不包含呢？這一點我比較擔憂，總之找一個方法將原點包起，保證原點拉到任一個面都能產生出所有方向，我附的答案是六面體，最簡單的四面體都然也可以，但是不太好寫。

4.16

On n parallel railway tracks n trains are going with constant speeds v1, v2, . . . , vn. At time t = 0 the trains are at positions k1, k2, . . . , kn. Give an O(nlogn) algorithm that detects all trains that at some moment in time are leading. To this end, use the algorithm for computing the intersection of half-planes.

• 公式$X_{i}(t) = K_{i} + V_{i} * t$
• 對於所有 polyhedral set$H = {(t, x) : \forall i; X \geq X_{i}(t)}$

之後將這些半平面做交集，看交集結果的邊屬於哪一個半平面的邊界，哪一個火車就曾經領先過。套用半平面求交集只需要 O(n log n)

請參考 [ACM 題目] 少女與戰車

Chapter 1

1.1

The convex hull of a set S is defined to be the intersection of all convex sets that contain S. For the convex hull of a set of points it was indicated that the convex hull is the convex set with smallest perimeter. We want to show that these are equivalent definitions

a. Prove that the intersection of two convex sets is again convex. This implies that the intersection of a finite family of convex sets is convex as well.
b. Prove that the smallest perimeter polygon P containing a set of points P is convex.
c. Prove that any convex set containing the set of points P contains the smallest perimeter polygon P.

a. 證明兩個凸包交集仍然是凸包
假設凸包分別為$C1, C2$，題目所求$C = C1 \bigcap C2$
已知：A set$K$ is convex if each$u \neq v$, the line-segment$\bar{uv}$ is contained in$K$,$\bar{uv}\subseteq K$
假設$C$ 不是凸包，則存在$\bar{uv} \nsubseteq C$，根據定義$u, v \in C1, C2$，得到$\bar{uv} \nsubseteq C1, C2$，矛盾得證$C$ 一定是凸包。

b. 證明最小周長的多邊形 P 包含所有點集 S 一定是凸包
假設$P$ 是最小周長的非凸包多邊形，令$x, y \in P, and \bar{xy} \nsubseteq P$，則$\bar{xy}$ 會交$P$ 於至少兩點$x', y'$$P'$ 是將$\bar{x^{'}y^{'}}$ 連起所產生的新多邊形，顯然地$P'$ 的周長更小。矛盾得證。

c. 證明任何一個凸多邊形 C 包含點集 S 的同時也一定會包含最小周長的多邊形 P。
假設有 vertex$v \in P, but v \notin C$，同時 v 不會在 S 範圍中，因為 C 已經包含了 S$v1, v2$ 為$C, P$ 交點，則$P'$ 是$v1, v2$ 相連產生的多邊形，則 P’ 藉由 (b) 一定是多邊形，v1 到 v2 的距離更短，找到一個周長更小的多邊形。矛盾得證。

1.3

Let E be an unsorted set of n segments that are the edges of a convex polygon. Describe an O(nlogn) algorithm that computes from E a list containing all vertices of the polygon, sorted in clockwise order.

Algorithm:

1. 得到所有點${(x1, y1), (x2, y2), ..., (xn, yn)}$，並且附加是屬於哪兩個邊的端點對點作排序。map< point, vector<seg> > R - O(n log n)
2. 挑最左下的角當作$(x1, y1)$ 的其中一邊

   1 2 3 4 5 6 7

   A[0] = (x0, y0) = R.begin().first; for (int i = 0; i < E.size(); i++) { for (seg s : R[A[0]]) { if (s.p0 == A[i] && (i == 0 || s.p1 != A[i-1])) A[i+1] = s.p1; } }

3. 檢查是否為順時針，否則反轉序列 - O(n)

1.8

The O(nlogn) algorithm to compute the convex hull of a set of n points in the plane that was described in this chapter is based on the paradigm of incremental construction: add the points one by one, and update the convex hull after each addition. In this exercise we shall develop an algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total. Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.
b. Use the algorithm from part a to develop an O(nlogn) time divide-andconquer algorithm to compute the convex hull of a set of n points in the plane.

D&C 的 O(n log n) 凸包算法

a. 將兩個沒有相交的凸包，用 O(n) 時間內合併凸包$P1 \cup P2$。

假設兩個凸包儲存方式都是逆時針順序，並第一個節點為最左下的節點。
Algorithm:

1. 將最左側的凸包另為 P1，反之 P2。
2. 代碼如下，找到下凸包 - O(n)

   1 2 3 4 5 6 7 8 9 10 11

   vector C C[m = 0] = P1[0] for (i = 1, j = 0; i < P1.size(); i++) { if (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0) break; C[m++] = P1[i] } for (; j < P2.size(); j++) while (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0) m--; C[m++] = P2[j];

3. 仿 2. 反過來作，找到上凸包 - O(n)
4. 上下凸包合併 - O(n)

b.
Algorithm:

1. 將所有點按照 x 做升排序 - O(n log n)

2. 1 2 3 4 5 6 7

   convex DC(int l, int r, point p[]) { if (l == r) return convex(p[l]) convex leftconvex = DC(l, (l + r)/2, p); convex rightconvex = DC((l+r)/2 + 1, r, p); return merge(leftconvex, rightconvex); }

Prove$T(n) = 2 T(n/2) + O(n)$,
by master theorem:$a = 2, b = 2, c = 1, log_{a}b = c, \Rightarrow T(n) = \theta (n^{c} log n) = \theta (n log n)$

Chapter 2

2.1

Let S be a set of n disjoint line segments whose upper endpoints lie on the line y=1 and whose lower endpoints lie on the line y=0. These segments partition the horizontal strip [−∞ : ∞]×[0 : 1] into n+1 regions. Give an O(nlogn) time algorithm to build a binary search tree on the segments in S such that the region containing a query point can be determined in O(logn) time. Also describe the query algorithm in detail.

參閱實作 b321: 河道分界

Algorithm: (build)

1. sort 線段 (根據上方的 (x, 1) 進行由小排到大 ) - O(n log n)
2. 靜態建造，動態建造請參閱可平衡的 BST。因為任切一條 y = k 的線，保證相交的 x 值得順序不會變 (跟排序結果的順序相比)，因此一開始挑 y = 1 來做排序依據。

   1 2 3 4 5 6 7 8 9 10 11 12 13

   root = dfs(0, n - 1, segments) - `O(n)` node dfs(int l, int r, segment segs[]) { if (l == r) return new node(segs[l]); else if (l < r) int mid = (l + r)/2; node ret = new node(segs[mid]); ret.lson = dfs(l, mid - 1, segs); ret.rson = dfs(mid + 1, r, segs); return ret; else return NULL; }

Algorithm: (query)

1. 令 lbound = null, rbound = null
2. 走訪 BST

   1 2 3 4 5 6 7 8 9 10

   void query(node u, point p) { if u == NULL return; if p leftside by u.seg rbound = u dfs(u.lson, p) else lbound = u dfs(u.rson, p) }

3. output (lbound, rbound)

2.5

Which of the following equalities are always true?
$$(1) Twin(Twin(\vec{e})) = \vec{e} \\ (2) Next(Prev(\vec{e})) = \vec{e} \\ (3) Twin(Prev(Twin(\vec{e}))) = Next(\vec{e}) \\ (4) IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e})) \\$$

(1)(2)(4) are always true. (3) may not be true.

2.6

Give an example of a doubly-connected edge list where for an edge e the faces$IncidentFace(\vec{e})$ and$IncidentFace(Twin(\vec{e}))$ are the same.

已知$IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e}))$ always true，讓$Next(\vec{e}) = Twin(\vec{e})$ always true。

2.14

Let S be a set of n disjoint line segments in the plane, and let p be a point not on any of the line segments of S. We wish to determine all line segments of S that p can see, that is, all line segments of S that contain some point q so that the open segment pq doesn’t intersect any p not visible line segment of S. Give an O(nlogn) time algorithm for this problem that uses a rotating half-line with its endpoint at p.

參閱實作 b325: 人格分裂

Algorithm:

1. 對於所有的端點相對 p 做極角排序，並且知道相對應的角度上會存有那些線段的端點。

   1 2 3 4 5 6 7

   map<double, vector<int, int> > angle; for (int i = 0; i < n; i++) { double v1 = atan2(D[i].s.y - pos.y, D[i].s.x - pos.x); double v2 = atan2(D[i].e.y - pos.y, D[i].e.x - pos.x); angle[v1].push_back(make_pair(i, 0)); angle[v2].push_back(make_pair(i, 1)); }

2. 藉由出現的角度，使用極角掃描，一開始必須將碰的線段加入。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   double c; CMP::base = pos; double ftheta = angle.begin()->first; pair<int, int> u = angle.begin()->second[0]; Pt fpt; if (u.second == 0) fpt = D[u.first].s; else fpt = D[u.first].e; for (int i = 0; i < n; i++) { if (cross(pos, fpt, D[i].s) * cross(pos, fpt, D[i].e) < 0) S.insert(D[i]); } CMP::sin = sin(ftheta); CMP::cos = cos(ftheta); for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin(); it != angle.end(); it++) { CMP::sin = sin(it->first); CMP::cos = cos(it->first); for (int i = 0; i < it->second.size(); i++) { pair<int, int> u = it->second[i]; if (u.second == 0) c = cross(pos, D[u.first].s, D[u.first].e); else c = cross(pos, D[u.first].e, D[u.first].s); if (fabs(c) > eps) { if (c > 0) S.insert(D[u.first]); else S.erase(D[u.first]); } } if (S.size()) { visual[S.begin()->label] = 1; } }

心得

出題目，出題目，萌萌哒