Com S 418/518 - Assignments

Assignments

	Due Date	Solutions
Assignment 1	Jan 21	Solution 1
Assignment 2	Jan 28	Solution 2
Assignment 3	Feb 4	Solution 3
Assignment 4	Feb 11	Solution 4
Assignment 5	Feb 18	Solution 5
Assignment 6	Feb 25	Solution 6
Assignment 7	Mar 11	Solution 7
Assignment 8	Mar 25	Solution 8
Assignment 9	Apr 1	Solution 9
Assignment 10	Apr 8	Solution 10
Assignment 11	Apr 15	Solution 11
Assignment 12	Apr 22	Solution 12
Project	Apr 25	Grading sheet Sample runs (courtesy of Joseph Altmaier): 1a (VD, DT) 1b (VD, DT) 2a (VD, DT) 2b (VD, DT) 3 (VD, DT) 4 (VD, DT) 5a (VD, DT) 5b (VD, DT)

Homework policy

The homework must be submitted at the beginning of the lecture on the due date. Any homework turned in after this time will be considered late. Late homework will be accepted until 5pm on the due date for a penalty of 25%. Homework will not be accepted beyond that time.

Essay for Graduate Credit

The essay for graduate credit is due on Thursday April 22.

The objective of the essay is to study a geometric structure or algorithm not covered in the lectures, and to present it clearly to the reader (who presumably didn't know the topic). The essay will require approximately 10 to 15 hours of self-study and writing and make up 5% of the total graduate grade. It should demonstrate certain level of understanding.

The essay should have at least 4 pages (with figures included).

You have the freedom of choosing any related topic to write about. Below are just some suggestions:

incremental construction of convex hulls
divide-and-conquer convex hull algorithm
divide-and-conquer construction of the Voronoi diagram
Voronoi diagram in three-dimensional space
Voronoi diagrams for points and line segments
Euclidean minimum spanning trees
the closest pair problem
hidden surface removal
the chain method for point location
visibility graphs
robot motion planning in the plane
mesh generation
robustness and precision issues in geometric computation
ray tracing
application to Geographic Information Systems (e.g., map data modeling and processing)

Some suggested reference books:

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. ISBN 0-387-96131-3.
J. O'Rourke. Computational Geometry (2nd edition), Cambridge University Press, 1998. ISBN 0521-64976-5.
J.-R. Sack and J. Urrutia (ed.). Handbook of Computational Geometry, North-Holland, the Netherlands, 2000. ISBN 0-444-82537-1.

You may also search these journals for interesting topics:

Computational Geometry: Theory and Applications
Discrete and Computational Geometry
International Journal of Computational Geometry and Applications
ACM Transactions on Graphics