Course No.:S070104ZJ009
Course Category:Professional Basic Course
Period/Credits:40/2
Prerequisites:Calculus, Ordinary differential equation.
Aims & Requirements:
This is a basic course is for applied mathematics, computer-aided design and so on. This course introduces the geometric problems developed in the disciplines of computer graphics, geographic information systems and robotics, CAD / CAM and other computational geometry problems, as well as the common design of geometric algorithms. Through this course, students can learn the calculation of the geometry the basic concepts, algorithms and techniques.
Primary Coverage:
Chapter 1 Introduction
Computational geometry and its applications.
Chapter 2 Intersections of line segments and triangulations
Intersections of line segments, Boolean algorithm, galley theorem, triangulations, the area of polygon.
Chapter 3 Database query and point location
KD-tree,BSP-tree, multilayer division tree, point location, randomized incremental processing.
Chapter 4 Voronoi diagram
Definition, properties and its application of Voronoi diagram, Delaunay triangulation, axis line.
Chapter 5 Convex hull
Definitions, fast convex hull, efficiency of the convex hull, polytope.
Chapter 6 Motion planning of robots
Point robot, translational action plan, the shortest path,construct the visibility map.
References:
[1] M. de Berg et al, Computational geometry-algorithm and application, Tsinghua University Press, 2005-09.
[2] M. I. Shamos et al, Computational geometry, Science Press, 1993
Author:Liyong Shen (School of Mathematical Sciences, GUCAS)
Date:June, 2009