HMC Math 189A: Computational Geometry (Spring, 2002)
Homework


KEY: (1st edition) (2nd edition)

Assignment #5 (due Thu. 3/7):

1: Degree of NNG (5.5.6.1, pg 192) (5.5.6.1, pg 177)
2: Number of triangles in a triangulation (5.5.6.4, pg 192) (5.5.6.4, pg 178)
3: Space partiotions (6.2.2.2, pg 212) (6.2.2.2, pg 198)
4: Dual of regular polygons (6.5.3.2, pg 218) (6.5.3.2, pg 205)
5: Polar dual properties (6.5.3.3, pg 218) (6.5.3.3, pg 205)
6: Even number of points [easy] (6.7.7.1, pg 229) (6.7.7.1, pg 218)

Assignment #4 (due Tue. 2/26):

1: Regular polygon [easy] (5.3.3.1, pg 178) (5.3.3.1, pg 164)
2: Unbounded regions (5.3.3.2, pg 178) (5.3.3.2, pg 164)
3: Nearest neighbors (5.3.3.3, pg 178) (5.3.3.3, pg 164)
4: High-degree Delaunay vertex (5.3.3.4, pg 178) (5.3.3.4, pg 164)
5: D(P) => V(P) (5.4.5.1, pg 182) (5.4.5.1, pg 168)

Assignment #3 (due Tue. 2/19):

1: Shortest path below (3.2.3.8, pg 76) (3.2.3.8, pg 68)
NOTE: In the 1st edition, the problem reads, "...find the shortest path from a to b that goes below S" (as opposed to "avoids the interior of S"). The two are clearly similar, but do the "below" version from the 1st edition.
2: Recurrence relation with O(n^2) merge (3.8.4.1, pg 107) (3.8.5.1, pg 95)
3: Recurrence relation with O(n log n) merge (3.8.4.2, pg 107) (3.8.5.2, pg 95)
NOTE: For problems 2 and 3, you may use the Master Theorem, if appropriate, or simply attempt a direct solution as shown in class or the text.
4: Merge without sorting (3.8.4.4, pg 107) (3.8.5.4, pg 95)
5: Cuboctahedron [easy] (4.1.6.4, pg 121) (4.1.6.4, pg 108)
6: Topology of shadow boundary (4.2.2.4, pg 127) (4.2.3.4, pg 114)
NOTE: When it says "construct", I mean that literally... you are required to build a 3-D model (out of cardboard, or whatever you like... comic book backing boards or styrofoam might work well) and submit it with your homework. BTW, the "Goodrich" that the problem is credited to is the guy I had for Computational Geometry!

Assignment #2 (due Tue. 2/12):

1: Diagonals => triangulation (1.2.5.7, pg 17) (1.2.5.8, pg 16)
NOTE: problem differs between editions. Your algorithm needn't be O(n), but may be for extra credit.
2: Convex polygons [easy] (1.6.8.8, pg 47) (1.6.8.2, pg 42)
3: Worst case (1.6.8.9, pg 47) (N/A)
NOTE: The 2nd edition gives the O(n^2) "triangulation via otectomy (ear deletion)" algorithm in the text. So do the following based on the O(n^3) algorithm from class:
"Find a generic polygon that forces the triangulation code to use "Big Theta"(n^3) time."
4: Affine hulls [easy] (3.2.3.4, pg 75) (3.2.3.4, pg 68)

2A: Recall the "GIFTWRAPPING" algorithm for convex hulls requires us to find the minimum angle theta from the "current" edge of the hull. It is usually desirable, if our input points are integer-valued, to avoid floating-point (i.e non-integer) arithmetic for speed and precision reasons. Describe how you could implement the GIFTWRAPPING algorithm so that "theta" need never be explicitly calculated, and only integer arithmetic is used (no division!).

Assignment #1 (due Thu. 2/7):

Section 1.1 (pg 10): 1
Section 1.2 (pg 16): 1, 2, 4
Section 1.6 (pg 46): 1
NOTE: Yes, 1.2.4 is hard. But fun. See how far you get with it.
BTW, I don't have a closed form yet (if I'm even doing it right... ;-)
Extra Credit: #1.1.4.4 (pg 10)
Or see the whole assignment here.

Return to: Math 189A Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu