计算几何 | Computational Geometry

Geometry can be traced back to ancient Greece, but Computational Geometry evolved less than 40 years as a branch of computer science. The Computational Geometry taught in this course is derived from classical discrete/combinatorial geometry and modern computer science.

Computational Geometry first appeared on the horizon when M. I. Shamos presented his Ph.D. dissertation in 1978. Since then, this phrase has been used to refer to algorithmic study on discrete and combinatorial geometric structures and can also be regarded as the geometric version of Algorithm Design and Analysis. Computational Geometry is now considered the basis of robotics, computer aided design and manufacturing (CAM and CID), and geographic information systems (GIS).

As we all know, the history of geometry can be traced back to at least the ancient Greek times, but different people have different understandings of "computational geometry". The computational geometry discussed in this course originates from the combination of classical discrete/combinatorial geometry and modern computer science. The doctoral thesis completed by MI Shamos in 1978 marked the birth of this branch of the discipline. Since then, "computational geometry" has often referred specifically to the study of algorithms for discrete and combinatorial geometric structures. In short, it can also be considered as the geometric version of algorithm design and analysis.

The teaching objectives of this course are threefold:

First, an overall understanding of computational geometry theory. This understanding will provide you with a geometric perspective in future research work.
Second, a comprehensive understanding of geometric problem solving paradigms and strategies, including incremental construction, plane scanning, divide and conquer, Layering, approximation and randomization, etc.
Finally, a thorough grasp of basic geometric structures and algorithms, including convex hull, polygon subdivision, Voronoi diagram, Delaunay triangulation, as well as geometric intersection, point location, range search, interception window query etc.