CS 633 Fall 2007
Computational Geometry

Time: Thur, 4:30 pm - 7:10 pm
Location: Innovation Hall 206
Course webpage: http://cs.gmu.edu/~jmlien/teaching/07_fall_cs633/

Instructor: Jyh-Ming Lien
Office hours: TBA
Contact: jmlien@gmu.edu, (703) 993-9546, Office 421 ST II

CS633 is an introductory course to Computational Geometry. Computational Geometry is a study of algorithms and data structures for geometric objects. One important goal of CS633 is to make you become knowledgeable and comfortable enough to deal with any geometric problems.

Required Textbook: Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, second revised edition, Springer-Verlag, 2000. ISBN # 3-540-65620-0.

In addition, we will study papers from various journals and conferences; these will be made available electronically.

Weekly Schedule, Readings, Assignments, Notes.

DateLecture Notes ScopeAssignments
Aug 30 Introduction pdf Chapter 1 TBA
Sep 06 Line segment intersection pdf Chapter 2 TBA
Sep 13 Polygon triangulation pdf Chapter 3 TBA
Sep 20 Linear programming pdf Chapter 4 TBA
Sep 27 Range search pdf Chapter 5 TBA
Oct 04 Point location pdf Chapter 6 TBA
Oct 11 Voronoi diagrams pdf Chapter 7 TBA
Oct 18 Arrangement and duality pdf Chapter 8 TBA
Oct 25 Delaunay triangulation pdf Chapter 9 TBA
Nov 01 Convex hulls pdf Chapter 11 TBA
Nov 08 Binary space partitions pdf Chapter 12 TBA
Nov 15 Motion planning pdf Chapter 13 TBA
Nov 22 Thanksgiving no class
Nov 29 Visibility graph pdf Chapter 15 TBA
Dec 06 Probabalistic motion planning pdf handoutsTBA
Dec 13Project presentations

Related websites (More information will be added)

Scope: In this course, we will learn about the following topics:

  • Line segment intersection
  • Convex hull
  • Triangulations
  • Proximity problems
  • Range searching
  • Point location
  • Voronoi Diagrams
  • Delaunay Triangulations
  • Arrangements and Duality
  • Binary space partitions
  • Robot Motion planning
  • Quadtree/Octree
  • Visibility Graph

(Shortest geodesic paths, created by Jason Cantarella.
Stanford bunny created by Greg Turk and Marc Levoy)

Applications: Computational Geometry deals with many fundamental problems and many exciting applications in the following areas:

  • Computer Graphics and Solid Modeling
  • Robotics and Motion Planning
  • Biological Applications
  • Geometric Information System
  • Manufacturing and prototype design
  • Pattern Recognition
  • Linear Programming
  • Compression and Coding
  • ...


  1. Quizzes or CS culture assignments (please use this form) 5%
  2. Assignments 45%
  3. Project presentations 15%
  4. Final project report 35%


All required assignments must be completed by the stated due date and time. Your assignment score will be halfed every extra day after the due date. The quiz will be a closed book exam - no notes will be allowed. You can also have an opportunity of making up one your missed/failed quiz by turning in a CS culture assignment. A CS culture assignment is a one-page written summary of a talk (please use this form to complete your assignment) from a CS seminar (see http://cs.gmu.edu/~jmlien/seminar/) that you attend during the Fall'07 semester. Please note that all coursework is to be done independently. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you an F in the course. See the GMU Honor Code System and Policies at this page and this page. You are encouraged to discuss the material BEFORE you do the assignment. As a part of the interaction you can discuss a meaning of the question or possible ways of approaching the solution. The homework should be written strictly by yourself. In case your solution is based on the important idea of someone else please acknowledge that in your solution, to avoid any accusations.

Department of Computer Science
Volgenau School of Information Technology and Engineering
George Mason University