《Computational Geometry》Course Syllabus
Course Name | Computational Geometry |
Instructor | Prof. Gang Lu | Course Type | Elective Course |
Prerequisites Courses | C/C++/Java/Python, Data Structures, Algorithm Design Discrete mathematics Linear algebra | Discipline | Computer Science and Technology |
Learning Method | Lecture, Seminar |
Semester | 1st semester | Hours | 40 | Credits | 2 |
| | | | | |
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,
Line segments Intersection
Polygon Triangulation
Orthogonal Range Searching
Point Location
Convex hulls
Voronoi Diagrams
Delaunay Triangulations
Boolean operations on polygons
Robot Motion Planning
Visibility Graphs
Simplex Range Searching
Robust Issues
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%