Proof. There are infinite number of vertices and all these vertices are arranged and get picked up one at time by order, so the algorithm always terminates. □
Exercise 2.9. Let the diameter of a point set S be the largest distance between any two points of S. Prove that the diameter of S is achieved by two hull vertices.
Proof. If one of the ends of the line segment that characterises the diameter is a point inside conv(S), the line can be extended to a point on an edge, and dragging the point to one of the two adjacent vertices will definitely enlarge the diameter. □
Exercise 2.10. Prove that if S is the set of n points sampled from a uniform distribution in a unit space, then the expected number of points on the hull of S is of order O(log n).
Proof. This would be a very sketchy and flawed proof. As the particular chapter this exercise is for is considered, it's a good guess to think that it can be proved by going through the process of the algorithm. We can roughly track the possibility of introducing a new convex point for each point we pick from the uniform distributed set and add to the convex hull in the same order as specified by the algorithm. When the hull is growing in the direction parallel to Y coordinate, the possibility is about 1/k where k is the number of points that are already in the convex hull. After the four monotonously growing hull sections being merged, the total expected number will approximately be,
βn
α Σ 1 + ε
k=1 k
where α and β are generally constant coefficients that will not affect the final result in terms of order, and ε is also a negligible quantity compared to the terms in the front which as a harmonic series amounts to log n. (A program that simulates the process is expected to be present here shortly) □
No comments:
Post a Comment