CSE 680, Computational Geometry
Class Time : 12:00--12:50 pm, MWF.
Class Room : 218 Norton
Professor-in-Charge : Jinhui Xu
Office : 315 Davis Hall
Phone : (716) 645-4734
E-mail :jinhui@buffalo.edu
Office Hours : 1:00--2:00pm, Wed.
General Description:
This course introduces students to the essentials of
Computational Geometry and presents an in-depth study of the
fundamental geometric structures and techniques used in this field.
Topics to be covered include geometric searching, convex hulls,
proximity computations, intersections, arrangement and duality,
visibility graph, and other special topics. Applications to
problems from other fields such as Computer Graphics, Computer Vision,
Databases,
Robotics, and VLSI design will also be discussed.
Main Objective:
- Grasp the fundamental structures and techniques in
computational geometry.
- Strengthen students' ability of algorithms design and
analysis.
- Understand how to model problems in a geometric fashion.
- Training students to use geometric structures and
techniques to solve simple or moderately difficult problems.
Texts:
- (Required) M. de Berg, M. Van Kreveld, M.
Overmars, and O. Schwarzkopf, Computational Geometry:
Algorithms and Applications (3rd Edition), Springer.
- F. Preparata and M. Shamos, Computational Geometry: An
Introduction, Springer-Verlag, 1985.
- K. Mulmuley, Computational Geometry: An
Introduction Trough Randomized Algorithms, Prentice-Hall, 1994.
Topics to Be Covered (Tentative):
- Convex hull
- Line segment intersection,
- Triangulation
- Linear programming
- Range search
- Point location
- Voronoi diagram
- Arrangement and duality
- Visibility graph
- Well separated pair decomposition
- VC-dimension, epsilon-apprximation, and epsilon-nets
More Course Information
Syllabus
Slides (from Marc van Kreveld)
Homeworks
Projects
|