《Computational Geometry》Course Syllabus
Author:管理员 Time:2017-04-11 Hit:173

《Computational Geometry》Course Syllabus

Course Name

Computational Geometry


Prof. Gang Lu

Course Type

Elective Course

Prerequisites Courses


Data Structures,

Algorithm Design

Discrete mathematics

Linear algebra


Computer Science and Technology

Learning Method

Lecture, Seminar


1st semester






1. Objective & Requirement

Computational geometry is the study of the algorithms for solving geometric problems on computer. The field of computational geometry is about forty years old if one takes M.I.Shamos’s thesis (1978) as its inception.

There many brands of geometry and what we referred to as the computational geometry in this course is primarily discrete and combinatorial geometry. The major concerns about the computational geometry are convex hull, Voronoi diagram and the Delaunay triangulation, polygon partitioning, geometric searching, motion planning, line segments intersection, proximity graphs and so on, and the algorithms for problems in these fields play a fundamental role in many application domains such as geographic information systems (GIS), computer graphics, robotics, and others.

The general theme of the course will be on algorithmic and application oriented issues related to computational geometry. New and emerging topics in both theoretical research and applications will be presented as well.

The goals of the course are using geometric algorithms to address practical issues which can be reduced to some geometry related problems and also understanding them.

2. Topics to be covered

Topics Covered in this Course Include,

    1. Line segments Intersection

    2. Polygon Triangulation

    3. Orthogonal Range Searching

    4. Point Location

    5. Convex hulls

    6. Voronoi Diagrams

    7. Delaunay Triangulations

    8. Boolean operations on polygons

    9. Robot Motion Planning

    10. Visibility Graphs

    11. Simplex Range Searching

    12. Robust Issues

    13. Open Algorithmic Library

      3. Textbook

      [1] Computational Geometry--Algorithms & Applications (3rd Ed), by Mark de Berg, et al., Springer, 2008.

      [2] Computational Geometry An Introduction, by Franco P Preparata, et al., 1985.

      4. Reference Books

      [1] Computational Geometry in C (2nd Ed), by Joseph O'rourke, Cambridge University press, 1998.

      [2] A book and a bunch of papers from recent conferences such as ACM/IEEE Transactions on Graphics, ACM Computing Surveys, IEEE Transactions on Visualization and Computer Graphics, ACM SIGGRAPH.

      5. Course Evaluation (Tentative)

      Reaction paper      50%

Project            50%