凸包及最小外围矩形

《凸包及最小外围矩形》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、题目简述：給出一个平面点集S，求一个面积最小的矩形使其包含S所有的点。预备知识：在求解这道题之前我们先要了解一些关于凸包的知识。什么是凸包？简单地说，对于一个平面点集S，我们把完全包含该点集的最小的凸多边形叫做点集S的凸包H。凸包一个很重要的性质就是它“凸”的性质。这个性质对我们理解和计算凸包都有很大的帮助。I）对点集S中任意一点a，当且仅当存在直线p过a点并使得S中除a外所有点均在p的一侧，则a为凸包上的一顶点。II）对点集S中任意两点a,b，当且仅当S中除a,b以外所有点都在过点a,b的直线p的一侧，则线段ab

2、为凸包上的一条边。III）对点集S中任意四点a,b,c,d，当d在三角形abc中（包括边），则d不是凸包上的点。上面的几条关于凸包“凸”的性质为我们计算凸包提供了一个基础。这里我们将介绍两种简单且被广泛运用的算法――Gift-Wrapping和Graham-Scan算法。Gift-Wrapping算法：通过性质（I），我们可以找到一个特殊点，如具有最小y坐标且x坐标尽可能小的点。将它作为计算凸包的第一个顶点。确定了起点后，我们就可以通过Gift-Wrapping算法计算出点集的凸包。下面的步骤很直观的描述了这个算法

3、：1）把点集中所有点都看成是固定在平面上的柱子，想象我们在起始点柱子上系上一根身子。2）把绳子沿水平方向向右拉直，并逆时针旋转，当绳子碰上一根柱子，则对应了凸包上的一点3）继续旋转绳子，每次确定一个凸包上的顶点，直至绳子回到起点。图一：Gift-Wrapping算法计算凸包的过程每次通过旋转绳子找到下一个凸包顶点需要对点集中所有剩余点进行一次比较，所以这一步的时间复杂度是O（n）。每个凸包上的顶点都需要进行一次旋转操作，而最坏情况下，凸包顶点个数可以和点集个数相等，所以整个Gift-Wrapping算法的时间复杂度

4、是O（n2）的。Graham-Scan算法：Gift-Wrapping算法无论从理解还是从实现上来说，它都是十分简单的。但由于它的复杂度并不理想，我们无法利用它来求解大规模的凸包问题。因而，我们将介绍一种高效的计算凸包的算法――Graham-Scan。Graham-Scan算法主要可分成两部分：1）同Gift-Wrapping一样，需要先找出一个起始点。将这个点作为原点，进行夹角排序。2）先将起始点压入堆栈H中，再按照已经排好的顺序对每一个点进行扫描，同时维护堆栈H。这个堆栈表示的是到目前为止，所有已经扫描过的点对

5、应的凸包。每当扫描一个点p的时候：a)如果堆栈的元素少2个或者堆栈顶端的两个点与p构成左转关系，则将p压入堆栈中。b)否则，栈顶元素出栈并继续进行a的判断。当所有点都扫描完后，堆栈H即为我们要求的凸包。图二：Graham-Scan算法的扫描过程（堆栈H储存的即实线连接起来的点）分析Graham-Scan的复杂度：第一步中找出起点并进行极角排序的复杂度是O（nlogn）。第二步中每一个点仅会被扫描一次并相应维护一次堆栈H。而维护堆栈过程中每次访问堆栈H中的点，要么这个点被删除，要么就停止堆栈的维护，所以所有堆栈维护加

6、起来最多只访问了2n次。故这部分的复杂度是O（n）。综合起来，Graham-Scan算法的时间复杂度是O（nlogn）的。算法分析：现在考虑这道题目，题目要我们求出一个最小面积的矩形能够覆盖给定的所有点。易知矩形覆盖所有点当且仅当它覆盖这些点的凸包。故而，问题可以转化为对于一个凸包，求出一个面积最小的矩形来覆盖它。那么这个覆盖凸包的最小矩形有什么性质呢？首先，这个矩形的四条边上必然都有凸包的顶点。这个很容易想清楚，如果矩形的某条边没有碰上凸包的顶点，那么我们一定能把这条边向里压，从而得到一个更小的满足条件的矩形。其

7、次，这个矩形至少有一条边与凸包上的一边重合。这个性质不容易直观地想清楚，需要书面证明一下。由于完整的证明需要分成很多情况来讨论，比较繁琐，所以这里仅选取其中的一种情况来证明，其他情况可以类似地进行证明。利用反证法，我们假设覆盖凸包的最小矩形所有边都没有和凸包的边有重合，也就是说，最小矩形的每条边上仅有一个凸包的顶点。如图三所示，矩形ABCD是覆盖凸包的最小矩形，M、N、P、Q为凸包在矩形四条边上的顶点。我们分别作MM’⊥CD,NN’⊥AD。则矩形ABCD的面积S=MP×Cos(∠PMM’)×NQ×Cos(∠QNN’

8、)。我们将矩形旋转X度（顺时针为正，逆时针为负），仍使矩形覆盖凸包且M、N、P、Q分别在它的四边上。则此时新矩形的面积S=MP×Cos(∠PMM’+X)×NQ×Cos(∠QNN’-X)。我们仅需考虑Cos(∠PMM’+X)×Cos(∠QNN’-X)的单调性。Cos(∠PMM’+X)×Cos(∠QNN’-X)=1/2[Cos(∠PMM’+X+∠QNN’-X)+