# 計算幾何 - 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)。