Office : 212 Bell Hall
Phone : (716) 645-3180 ext. 132
E-mail :jinhui@cse.buffalo.edu
Office Hours : 1:00--2:00pm, Thu.

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.

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

•  (Required)  M. de Berg, M. Van Kreveld, M. Overmars, and O. Schwarzkopf,  Computational Geometry: Algorithms and Applications (2nd Edition), Springer, 1998. 
• F. Preparata and M. Shamos, Computational Geometry: An Introduction,  Springer-Verlag, 1985.
•   K. Mulmuley, Computational Geometry: An Introduction Trough Randomized Algorithms, Prentice-Hall, 1994.

• Convex hull
• Line segment intersection,
• Triangulation
• Linear programming
• Range search
• Point location
• Voronoi diagram
• Arrangement and duality,
• Visibility graph.

Syllabus