# 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 set$H = {(t, x) : \forall i; X \geq X_{i}(t)}$