CIS 4930 003 Introduction to Computational Geometry, Fall 2011


Instructor: Prof. Sudeep Sarkar (,

Classes: Tuesdays and Thursdays, 3:30 pm to 4:45 pm, PHY 13

Office Hours: Tues/Thurs: ENB 315, 2pm to 3pm or any other time with appointment.

TA: Ravi Kiran Krishnan (, Mon/Wed, 11am to 12:30pm, ENB 327.

Pre-requisites for the course: Data Structures, Algorithms, Experience in C programming, and Willingness to work hard.

Textbook: Computational Geometry in C by Joseph O'Rourke, Cambridge University Press, Second Edition.  (Website for the book)

  1. Penalty for unethical activity is a FF or expulsion from the department

  2. In the event of an emergency, it may be necessary for USF to suspend normal operations.  During this time, USF may opt to continue delivery of instruction through methods that include but are not limited to: Blackboard, Elluminate, Skype, and email messaging and/or an alternate schedule. It's the responsibility of the student to monitor Blackboard site for each class for course specific communication, and the main USF, College, and department websites, emails, and MoBull messages for important general information.

  3. If you miss an examination due to a valid, documented reason, considerations for prorated grading will be considered, i.e. weights of the missed exam will be distributed over the remaining ones. Please get in touch with Dr. Sarkar as soon as possible regarding this.

  4. Students who anticipate to be absent from class due to religious observance should inform Dr. Sarkar by email by second class meeting.

  5. All unauthorized recording of lectures is prohibited. You do not have the right to sell notes or tapes of lectures generated from this class.


  1. Computational geometry is the study of efficient algorithms to solve geometric problems, such as Given N points in the plane, how do you compute the smallest convex polygon that encloses all the points?, Given N points in a plane, what is fastest way to find the nearest neighbor of a point? Given N straight lines, find the lines which intersect with each other.

  2. The methods studied in this course will allow you to design and analyze algorithms for the efficient solution of numerous geometric problems that arise in other application areas such as astronomy, geographic information systems, CAD/CAM, data mining, graph drawing, graphics, medical imaging, metrology, molecular modeling, robotics, signal processing, textile layout, typography, video games, vision, VLSI, and windowing systems. It is a vital arsenal in your resume in today's world. See David Eppstein's Geometry in Action page for more info.

  3. We plan to cover the following topics: Polygonal Triangulations, Polygon Partitioning, Convex Hulls, Convex Hulls in 3D, Voronoi Diagrams, Arrangements, Search and Intersection, and Motion Planning.

Course Objectives:

  1. Project and presentation (35%).

  2. Proposal (5%)

  3. Phase I report (5%)

  4. Presentation (5%)

  5. Phase II report (15%)

  6. Attendance during presentations (5%)

  7. Two Programming Assignments (25%)

  8. Homeworks (10%)

  9. Three Exams (30%): Two best grades out of three examinations to gauge your progress.

Evaluation Criteria

  1. Help with postscript commands is available HERE

  2. CGAL: Computational Geometry Algorithms Library. GUI Code:

  3. Old Exams

  4. Old exam 1

  5. Old exam 2

  6. Old exam 3

  7. Geometry Algorithms Archive (Excellent web site for proximity and intersection types of problems. It has code and a great section on the history of geometry.

  8. Voronoi diagrams

  9. Animation of Fortune’s Algorithm for Voronoi Diagram

  10. Interactive addition of points to Voronoi diagram

  11. Source code for Fortune’s Voronoi diagram algo.

  12. The complete collection of algorithm animations

  13. Java Demos for the Textbook are Linked Here

  14. Java Demo of Convex Hull

  15. Computational Geometry Software on the Internet 

  16. Java Demo of Point/Line Duality

Useful Links