月度归档:2017年06月

计算几何(一)——凸包(Convex Hull)

凸包问题是计算几何(Computational Geometry)的一个重点,同样,如何构造凸包也是一个重要的研究方向,生活中许多问题都会用到构造凸包的知识,比如颜料混合,即如何从已有的颜料中通过混合得到未知的颜料。在这篇文章中,我将介绍5种重要的凸包构造算法,分别是极点算法极边算法增量式策略Jarvis MarchGraham Scan等,同时也将通过归约得到凸包构造算法时间复杂度的下界。

继续阅读