CSCI-6962/4963: Geometric Algorithms
Spring 2000

Course Information

Credits: 3 (graduate students) / 4 (undergraduates)
Prerequisites: Data structures and algorithms (CSCI-2300), or permission of instructor
Time: Tuesday and Thursday, 10:00am - 11:50am
Classroom: Sage 3704

Description

Course grading will be on the basis of homeworks, programming assignments, a class project and/or a final exam. Undergraduate students and graduate students will be graded separately.

Syllabus

• Convex hulls, Chap. 1
• Line segment intersections, Chap. 2
• Voronoi diagrams, Chap. 7, 11.5
• Delaunay Triangulations, Chap. 9
• Polygon triangulation, Chap. 3
• Point location, Chap. 6
• Range searching, Chap. 5
• Interval trees and segment trees, Chap. 10
• Arrangements, Chap. 8
• 3D Convex hulls, Chap. 11
• Robot motion planning, Chaps. 13 and 15
• Binary space partitions, Chap. 12
• Quadtrees, Chap. 14

Assignments

• Assignment 1, due January 25. postscript file, pdf file.
• Assignment 2, due February 8. postscript file, pdf file.
  You may find Brian Osman's gnuplot guidelines useful for graphical output.
  The books Graphics Gems II and III (in the reference section of Folsom) contain articles and code on line segment intersections. I've placed copies of three articles on reserve in Folsom.
• Course project proposal is due February 15. postscript file, pdf file. Additional handouts are available outside my office. A binder containing reference papers is available on reserve in Folsom.
• Assignment 3, due February 24. postscript file, pdf file.
• Assignment 4, due March 2. postscript file, pdf file.
• Assignment 5, due March 23. postscript file, pdf file.
• Final course project proposal is due April 6. postscript file, pdf file.
• Final project is due April 18.
• Assignment 6, due April 27. postscript file, pdf file.

Textbook

Note: There is a copy on reserve in the Folsom library. A new edition of this book with corrections is expected in April, and hence copies of the current edition are in short supply. It may be wise not to delay purchasing the book if you are taking the course.

Reference Books

• J. O'Rourke, Computational Geometry in C, Cambridge University Press, New York, 2nd edition, 1998. (Available on Reserve in Folsom.)
• F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Second edition), Springer-Verlag, New York, 1988.
• J-D. Boissonnat and M. Yvinec, Algorithmic Geometry, Cambridge University Press, 1998.
• H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer--Verlag, Heidelberg, 1987.
• K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.
• Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O'Rourke (Eds.), CRC Press, Boca Raton, 1997. (Available on Reserve in Folsom.)
• Handbook on Computational Geometry, Sack and Urrutia, North-Holland, 1998.
• T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.
• G. Farin, Curves and Surfaces for Computer Aided Geometric Design. Fourth ed, Academic Press, Boston, 1998.

Geometry Web Pages

• David Eppstein's Geometry in Action and Geometry Junkyard pages
• Jeff Erickson's Computational Geometry Page
• Geometry Literature Database