COT 4521-001 Introduction to Computational Geometry, Fall 2017


Instructor: Prof. Sudeep Sarkar (,

Classes: Mondays and Wednesdays, 11:00 am to 12:15 pm, ISA 3048

Office Hours: Mon/Wed: ENB 345, 3pm to 4:30pm or any other time with appointment.

TA: Gilbert Rotich, Tuesday and Thursday, 2:00 - 4:00 pm in room ENB 325

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

Textbook: Computational Geometry: Algorithms and Applications 3rd Edition

by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars

  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: Canvas, Skype, and email messaging and/or an alternate schedule. It's the responsibility of the student to monitor Canvas 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. For use of geometry in Microsoft Hololens and augmented reality see here.

  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/Worksheets in class (10%)

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

Evaluation Criteria

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

  2. 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.

  3. The complete collection of algorithm animations

  4. Java Demos for some CGeom Algorithms are Linked Here 

Useful Links