Computational Geometry

  • 申立勇
  • Created: 2014-12-08
Computational Geometry

 

Course No.S070104ZJ009

Course CategoryProfessional Basic Course

Period/Credits40/2

PrerequisitesCalculus, 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 pathconstruct 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

AuthorLiyong Shen (School of Mathematical Sciences, GUCAS)

DateJune, 2009