Computational Geometry
CIS5930 Spring 2005
Course Information Handout: [pdf]
Instructor
Piyush Kumar
Lecture Time and Place
Monday, Wednesday at 5:15pm to 6:30pm at Love 0301.
Office Hours: Monday, 6:30 to 7:30pm.
You will be able to find the lecture notes/slides here.
Class Mailing List
Announcements for the course, homeworks,
reading assignments, programming projects will be available using
the blackboard (http://campus.fsu.edu). Make sure you check both the course web site and the
blackboard at least once in two-three days throughout the semester.
Course Description
This is an introductory course to
computational geometry and its applications.
Here is a short summary of the topics that we will cover in the course
(not necessarily in this order)
- Convex hulls and an introduction to convexity.
- Geometric approximation algorithms. Intorduction to
VC-Dimension and $\epsilon$-nets.
- Voronoi diagrams and Delaunay triangulations.
- Geometric data structures like range searching data structures, quadtrees, interval
trees.
- Level of detail and visibility data structures for game programming.
- Motion planning.
Learning Objectives
The objective of this course is to
encourage you to learn how to :
- design and implement `new' geometric algorithms.
- map problems to computational geometric problems.
- read and understand algorithms published in journals.
- develop writing skills to present your own geometric algorithms
- collaborate and work together with other people to design new
geometric algorithms.
Prerequisites
A Grade of B or better in COP 4531 or CGS
5427 or an equivalent course. Come and talk to me if you do not have
the prerequisite and you still want to take the course.
I will try to keep the
prerequisites to a minimum and will review material as needed. You
will find basic concepts of combinatorics (counting, graphs,
recursion) to be very useful. Finally, it is useful to have experience with C, C++, or
Python. (You should at least be able to code in either of C or C++.)
Some of the homeworks will ask you to write code.
Textbooks
Roughly
60% of the material is covered in Computational Geometry:
Algorithms and Applications
by deBerg, Kreveld, Overmars, Schwarzkopf. My lectures will often draw from
the following (optional) texts.
- Lectures on Discrete Geometry by J. Matousek.
- Computational Geometry: An Introduction Through Randomized
Algorithms by K. Mulmuley
- Robert Sedgewick, Computational Geometry in C by J. O'Rourke.
I have requested the above material to be put
on reserve in the library. The text book is available at the
FSU bookstore.
Useful Links
Cheat
Sheet
Advanced
Computational Geometry
Some
more material
The
LEDA Book
How
to Present a Paper in Theoretical Computer Science, by Ian Parberry.
