Homework #7 (Solutions)

Assigned: Wednesday, 11/12Due: Friday, 11/21

start of lecture

This assignment covers textbook material in Chapter33

(Computational Geometry).

  1. (75 points) Textbook, p. 964, Problem 33-5.

a)

SOL) by Jianhui

Assume we have two convex polygons A and B. The vertices are in clockwise and n1 vertices in A and n2 vertices in B.

Algorithms

1. Computer the vertices with minimum y-coordinate for both A and B. If more than one exist, take the vertices with greater x-coordinate. P(i) for A, Q(j) for B. P and Q are points present with (x,y)

2. Construct two horizontal lines (L1 and L2, L1 for A, L2 for B) parallel with the x-axis.

3. Find the smaller angle of {L1 to (P(i),P(i+1)) ,L2 to (Q(j),Q(j+1))} in clockwise.

4. Check if P(i-1) ,P(i+1), Q(j-1), Q(j+1) lie to the same side of the line (P(i),Q(j)). If so, then we will add a side (P(i),Q(j))

5. There are two situation

1. If the smaller angle is L1 to P(i+1), L1 become the line (P(i),P(i+1). i=i+1, L2 become the parallel line with L1 through Q(j)

2. If the smaller angle is L2 to Q(j+1), L2 become the line (P(j),P(j+1). j=j+1, L1 become the parallel line with L2 through P(i)

6. Continue 3 until L1 or L2 reach the first point again.

*I got the base idea from: Shamos MI(1978)Computational Geometry, Ph.D.thesis, YaleUniversity.

Running Time:

From step3 to Step 6, we will calculate Step4 n1+n2 times. So the running time will be O(4*(n1+n2))=O(n1+n2)

Example

Givetwo polygons:

UML CSAnalysis of Algorithms 91.503 (section 201) Fall, 2003

b) by Vicky Xiang

SOL)

we can store the n points in an array A. Then we recursively find the convex hulls of the first n/2 points and the second n/2 points, and then combine the result with the same method as( a)

  1. FIND-HULL(A, p, r)
  2. if (p-r>=3)
  3. then
  4. FIND-HULL(A, p, q)
  5. FIND-HULL(A, q+1, r)
  6. MERGE-HULL(A,p,q.r)

It’s easy to see , T(n)=2T(n/2)+O(n’), n’ is the sum of the size of the first part convex hull and the size of the second part convex hull. Because the n points are are drawn independently according to a sparse-hulled distribution, the expected size of the convex hull is . Because , we can get ..

By mastertheorem case 1:

a=2, b=2, , .

  1. (25 points) In Theorem 3 of the paper “Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs”, carefully justify in detail the theorem’s claim that bottom-up hierarchical clustering can be performed in total time O(n2) for any cluster distance function computable in constant time from the distances between subclusters.

SOL)Vicky Xiang

We can perform bottom-up hierarchical clustering by the following algorithm:

  1. given n points, we can construct quadtree data structure presented in paper section 4 in O(n2) time according to the paper;
  2. find the closest pair (from the paper, we know we can always find the closet pair in O(1) time, just need to calculate );
  3. delete the pair (two clusters), and insert a new object repsenting the new merged cluster, this will cost O(n) time(O(n) for insertion and O(n) for deletion);
  4. go to step 2, repeat until we just have one cluster.

We know at most we need to do step 2, 3, 4 n times( in case every time we just merge one more point). Hence the running time is O(n2)(step 1) + n*(O(n) + O(1))=O(n2).

page 1 of 4