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. 證明兩個凸包交集仍然是凸包

b. 證明最小周長的多邊形 P 包含所有點集 S 一定是凸包

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. 藉由出現的角度，使用極角掃描，一開始必須將碰的線段加入。