邓老师在他的数据结构课堂就安利了他的这门计算几何课程，这个课程是数据结构课程的延申，可以说是数形结合版的数据结构和算法课。

趁着疫情在家，写毕业论文的同时也听了邓老师的这门课。收获颇多：
计算几何自上世纪七十年代由Shamos和Hoey发表的一篇计算平面点集Voronoi图的论文开始，现在已经发展为了独立的学科。
计算几何研究中最主要的目的就是开发出高效的算法以及数据结构来解决一些关于基本几何基元(geometric primitives)：点，线段，多边形，多面体等的问题。其中一些问题看起来是如此的简单，以至于它们直到计算机出现后才被认为是个问题。例如二维中典型的相交问题：给定平面上n条直线段，确定所有的相交点。如果暴力的逐个计算所有$n(n一1)／2$对线段对它们两两之间的相交，其计算复杂度是$O(n^2)$。幸运的是，计算几何中的经典算法可以将复杂度降到$O(nlogn)$。需要注意的是，计算复杂度是计算几何中的核心问题。尤其是在现实中，假如一个数据集中有上百万条线段，计算复杂度为$O(n^2)$和$O(nlogn)$的算法对比，他们的求解时间是几周和几秒之间的区别。典型的计算几何问题可以根据不同的标准划分成不同的种类。其中静态问题(static problem)指的是给定输入，需要构造或者找到输出的一类问题，一般包括以下经典问题：

  • 凸包：给定点集，找到能够包含所有点的最小的凸包二维多边形或者三维多面体：如turnleft算法；
  • 线段求交：给定线段集合，找到集合里所有线段的相交点，以及相交生成的新的线段，最朴素的就是$O(n^2)$的复杂度；
  • CGAL库里面的arrangement：点、线段、面对于平面空间的划分，双边数据结构；(这个算数据结构)
  • 多边形的三角剖分：给定平面多边形边界，将其内部全部划分成三角形表示的网格:如“earcut”方法；
  • 点集的三角化：delaunary三角化，最小角最大化；
  • 对偶的维诺图：给定平面点集，将平面划分成不同的块，块内的任一点到到给定点的距离最近。

以上是静态的计算几何问题，还有动态的点区域查询问题，更为复杂。

计算几何的核心就是计算复杂度，$O(n^2)$到$O(nlogn)$到$O(n)$到$O(logn)$之间的时间差异非常之大。邓老师最开始就讲到了算法与算法间复杂度的规约方法，感觉这个规约是这门课分析算法复杂度的灵魂，后面一直会提到。对每个问题一般会先讲最朴素的暴力求解，一般是高阶的多项式时间，然后一步步的讲到最优的时间复杂度算法。和数据结构课程一样，每个案例都配备了非常详细的动画展示，清晰易懂，一目了然。

很幸运可以找到这样的网课，本来每个大章节都想写一些笔记，后来百度的时候发现已经有前辈写了，写的还很好，珠玉在前，我就不班门弄斧了。上链接：https://www.zhihu.com/column/c_162517931。