COMP 163/MATH 163 Computational Geometry Fall 2018 
Announcements 
Brief Description 
Computational geometry is concerned with the design and analysis of algorithms for solving geometric problems. Applications can be found in such fields as VLSI design, computer graphics, robotics, computeraided design, pattern recognition, and statistics. The aim of the course will be to introduce some basic problems of computational geometry and discuss algorithms for solving these problems. The ultimate aim will be to identify general paradigms and data structures of particular importance to solving computational geometry problems, and thereby provide the participants with a solid foundation in the field.
Topics Covered: Design and analysis of algorithms for geometric problems. Topics include proof of lower bounds, convex hulls, searching and point location, plane sweep and arrangements of lines, Voronoi diagrams, intersection problems, decomposition and partitioning, farthestpairs and closestpairs, rectilinear computational geometry.
Expected Work: Written homework assignments, a midterm exam, an implementation project, and a final exam.
PREREQUISITE: Computer Science 160 or consent.
Tentative Schedule 
First Class:
Tuesday, September 4, 9:0011:30 a.m., Anderson 312
First Homework Due: Tuesday, 9/18 before class.
NO CLASS: Tuesday, September 25
MAKEUPCLASS for 9/25: Friday, September 21, 9  10:45AM
MAKEUPCLASS for 9/25: Friday, October 5, 910:45am
Second Homework Due: Wednesday, 10/3 by 4:30pm.
Third Homework Due: Wednesday, 10/17 by 4:30pm.
Midterm Exam: Tuesday, 10/23.
Fourth Homework Due: Wednesday, 10/31 by 4:30pm.
Fifth Homework Due: Wednesday, 11/14 by 4:30pm.
Sixth (Last) Homework due: Wednesday, 11/28 by 4:30pm.
Projects Due: Tuesday, December 4, 9:0011:45 am (last class)
Final Exam: Tuesday, December 18, 11:301:30pm.
Homework 
This list will be created during the
semester.
Instructor:Diane L. Souvaine 
Teaching Assistants:Matt Jones

TextBooks and References 
Main textbook 

Joseph
O'Rourke 

Satyan L. Devadoss and Joseph
O'Rourke 

Joseph
O'Rourke and Csaba Tóth 

Franco P. Preparata,
Michael Ian Shamos 


D. P. Dobkin and D. L. Souvaine, Computational Geometry  A User's Guide. Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, J. T. Schwartz and C. K. Yap, eds., Lawrence Erlbaum Associates, 1987, 4393. User Guide 

D. L. Souvaine Lecture Notes in Computational Geometry, 2005: Lecture Notes. 


Resources 



Demos 


List of Computational Geometry Demos maintained by Jeff Erickson, 









Documentation of LEDA book (Thanks to Cory McMahon) 
Other computational Geometry 





Document Preparation with Latex, by Budgen and Nelson. (Excellent) Getting Started with Latex, by Wilkins. (Shorter but good for getting started) 