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, SpringerVerlag, 2000. ISBN # 3540656200.
In addition, we will study papers from various journals and conferences; these will be made available electronically.

Weekly Schedule, Readings, Assignments, Notes.
Date  Lecture Notes 
Scope  Assignments 
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 
handouts  TBA 
Dec 13  Project 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
 ...
Grading
 Quizzes or CS culture assignments
(please use this form) 5%
 Assignments 45%
 Project presentations 15%
 Final project report 35%
Policies
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 onepage 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.
