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