《算法技术手册》一1.3.4 近似算法

1.3.4 近似算法

即使有了这些优化，计算凸包算法所固有的下界性能问题仍未有突破。不过，与其计算出精确解，也许近似解就足够了——近似解不但可以很快地计算出来，而且误差也是能够精确测定的。
Bentley-Faust-Preparata算法可以通过将点集切分成多个纵向区域来构建一个近似凸包（Bentley et al.，1982）。在每个区域中，可以很容易找到最大点（根据y坐标决定）和最小点（即图1-6中用框圈起来的点），然后将每个区域中的这两个点以及点集的最左点和最右点连起来，就得到一个近似凸包。当然，这样做有可能会漏掉实际上应该在凸包中的点P1，如图1-6所示。

图1-6：通过近似计算得到凸包