Skip to main content

TsinghuaX: 计算几何 | Computational Geometry

In this introductory computer science course, explore geometry, develop geometric thinking, and learn geometric algorithms.

计算几何 | Computational Geometry
16 weeks
6–8 hours per week
Self-paced
Progress at your own speed
Free
Optional upgrade available

There is one session available:

10,664 already enrolled! After a course session ends, it will be archivedOpens in a new tab.
Starts Mar 27
Ends Sep 1

About this course

Skip About this course

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.

At a glance

  • Institution: TsinghuaX
  • Subject: Computer Science
  • Level: Advanced
  • Prerequisites:
    • C++ programming
    • Fundamentals of Data Structures & Algorithms
  • Language: 中文
  • Video Transcript: English
  • Associated skills:Research, Computational Geometry, Geographic Information Systems, Algorithms, Computer-Aided Design, Problem Solving, Voronoi Diagram, Information Systems, Computer Science, Algorithm Design, Computer-Aided Manufacturing, Ancient Greek, Teaching, Divide And Conquer, Geometry

What you'll learn

Skip What you'll learn
  • Awareness of Computational Geometry theory that will help students incorporate Computational Geometry into their future research
  • Comprehensive understanding on fundamental paradigms/strategies for solving geometric problems, incremental construction, plane sweeping
  • Essential geometric structures and algorithms such as polygon decompositions, Voronoi diagrams, Delaunay triangulations

Who can take this course?

Unfortunately, learners residing in one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. edX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.

Interested in this course for your business or team?

Train your employees in the most in-demand topics, with edX For Business.