# 計算幾何 - HW05

## 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.

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.

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)

### 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.

$$O(\sum_{i = 1}^{H} i \times 2^{H-i}) = O(1 \times 2^{H-1} + 2 \times 2^{H-2} + ... ) \\ = O((2^{H-1} + 2^{H-2} + ... + 1) + (2^{H-2} + 2^{H-3} + ... + 1) + ...) \\ = O(2^{H} + 2^{H-1} + ... + 1) = O(2^{H+1}) = O(n)$$

### 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.)

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

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

b. 使用 inteerval tree 處理 interval。

preprocessing time : O(n log n)
query time : O(log2 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) 的包含結果。

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

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.

(=>)$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 p1p2, which must be a subset of every convex set containing p1, p2.
• Suppose: $n \le k$ 均成立，當 n = k + 1 $\lambda_{k+1} = 0$ 必定成立。
\begin{align} & q = \lambda_{1} p_{1} + \lambda_{2} p_{2} + ... + \lambda_{k} p_{k} + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) \left [ \frac{\lambda_{1}}{1 - \lambda_{k+1}} p_{1} + \frac{\lambda_{2}}{1 - \lambda_{k+1}} p_{2} + ... + \frac{\lambda_{k}}{1 - \lambda_{k+1}} p_{k} \right ] + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) ({\lambda_{1}}' p_{1} + {\lambda_{2}}' p_{2} + ... + {\lambda_{k}}' p_{k}) + \lambda_{k+1} p_{k+1} \\ & \text{where } {\lambda_{i}}' = \frac{\lambda_{i}}{1 - \lambda_{k+1}}, \lambda_{1} + \lambda_{2} + ... + \lambda_{k} = 1 - \lambda_{k+1} \\ & \sum_{i = 1}^{k} {\lambda_{i}}' = \sum_{i = 1}^{k} \frac{\lambda_{i}}{1 - \lambda_{k+1}} = \frac{1}{1 - \lambda_{k+1}} \sum_{i = 1}^{k} \lambda{i} = 1 \end{align}

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

$q = (1 - \lambda_{k+1}) {q}' + \lambda_{k+1} p_{k+1}$

every convex set containing p1, p2, …, pk, q’. Since it also contains pk+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 p1, p2, p3. This partitions the triangle into tree smaller ones.

$$\left\{\begin{matrix} \triangle p_{1} p_{2} p_{3} = A \\ \triangle q p_{2} p_{3} = A_{1} \\ \triangle q p_{1} p_{3} = A_{2} \\ \triangle q p_{1} p_{2} = A_{3} \\ A = A_{1} + A_{2} + A_{3} \end{matrix}\right. \Rightarrow q = \frac{A_{1}}{A} p_{1} + \frac{A_{2}}{A} p_{2} + \frac{A_{3}}{A} p_{3}$$

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

### 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 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，將 hconflict(e) 移除掉 intersection(e, hconflict(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 ]$－所有的花費。

$$E[c(S_{i}, h_{i})] = \frac{1}{n-i} \sum_{h \in S \setminus S_{i} } c(S_{i}, h) \\ \Rightarrow \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ) = \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{E(S_{i}, h_{i-1})} \right ) \\ = \sum_{i = 1}^{n} \left ( \frac{2}{i} (n - i) E(S_{i}, h_{i-1}) \right ) = \sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{the number of of vertices destroy ed at i+1}] \right )$$

$$\sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{the number of vertices destroy ed at i+1}] \right ) \\ = \sum_{v} \frac{2(n - td(v) + 1)}{td(v) - 1} \le \sum_{v} \frac{2(n - tc(v)) + 2}{tc(v)} \\ \le \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} E[\left |v \mid tc(v) = i \right |] \\ = \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} \times 2 = O(\sum_{n}^{i=1} \frac{n}{i} - 1) = O(n ln n)$$

# 計算幾何 - HW04

## 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

### 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.

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 (相鄰)。假設儲存邊的順序為順或逆時針，則邊的順序等價排序結果。

### 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?

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)$

• 由於$\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 algorithmO(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

$d(p, q) \leq \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)).$
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.

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. (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.

• 對於多維度範圍查找用 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 值仍然要算相同，利用偏斜的效果不利於操作。

# 計算幾何 - HW03

## Master Theorem

$$T(n) = \begin{cases} aT(n/b) + n^{c} & \text{ if } n > 1 \\ d & \text{ if } n = 1 \end{cases}$$

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

$$T(n) = \begin{cases} aT(n/b) + f(n) & \text{ if } n > 1 \\ d & \text{ if } n = 1 \end{cases} \\ E = log_{b}(a)$$

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 個節點。

## 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. 利用 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.

# 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.

## 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).

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

## 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.

# 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.

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.

## 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 = 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，

## 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.

# 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 setH = {(t, x) : \forall i; X \geq X_{i}(t)} 之後將這些半平面做交集，看交集結果的邊屬於哪一個半平面的邊界，哪一個火車就曾經領先過。套用半平面求交集只需要 O(n log n) Read More + # 計算幾何 - HW01 # 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 setK is convex if eachu \neq v, the line-segment\bar{uv} is contained inK,\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。

## 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)$ 的其中一邊
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)
3. 仿 2. 反過來作，找到上凸包 - O(n)
4. 上下凸包合併 - O(n)

b.
Algorithm:

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

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.

Algorithm: (build)

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

Algorithm: (query)

1. 令 lbound = null, rbound = null
2. 走訪 BST
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.

Half-edge Orign Twin IncidentFace Next Prev
$\vec{e_{1, 2}}$ $v_{1}$ $\vec{e_{2, 1}}$ f1 $\vec{e_{2, 1}}$ $\vec{e_{2, 1}}$
$\vec{e_{2, 1}}$ $v_{2}$ $\vec{e_{1, 2}}$ f1 $\vec{e_{1, 2}}$ $\vec{e_{1, 2}}$

## 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.

Algorithm:

1. 對於所有的端點相對 p 做極角排序，並且知道相對應的角度上會存有那些線段的端點。
2. 藉由出現的角度，使用極角掃描，一開始必須將碰的線段加入。