计算几何作业1：凸包性质与证明

"该文件是Computational Geometry的作业1，包含算法和证明题，讨论了凸包的概念及其性质。文件以doc文档的形式呈现，主要探讨了凸包的定义、交集的性质以及最小周长多边形的问题。" 在计算几何领域，凸包(Convex Hull)是一个关键概念，它被定义为所有包含给定点集S的凸集合的交集。这个定义等价于：凸包是包围S的所有多边形中具有最小周长的那个。在作业的解答中，提到了几个关键证明： 1. **交集的凸性**： 如果有两个凸集合C1和C2，它们的交集C3也是凸的。这是因为如果C1和C2中的任意两点a和b形成的线段上的任何点c都不在C1或C2之外，那么C3将包含这条线段。如果c不在C3中，这将违反C1和C2是凸集的假设，所以交集C3必须是凸的。这意味着有限个凸集合的交集也是凸的。 2. **最小周长多边形的性质**： 要证明最小周长的多边形P是凸的，可以考虑在P中选取任意两点a和b，连接a和b形成一条边。如果这条边不在P内，那么可以通过这条边形成一个新的多边形P'，其周长小于P。因为我们要找的是最小周长的多边形，所以P必须是凸的，这样所有可能的内部边都已经包含在内。 3. **凸包与最小周长多边形的关系**： 凸包包含了点集P中的所有点，而且具有最小的周长。如果存在一个不是凸的多边形也能包含所有的点，那么根据之前的证明，它的周长将会更大，这与最小周长多边形的定义矛盾。 作业还提到了一个未排序的n条边构成的凸多边形的边集E。为了处理这样的问题，通常需要设计一个时间复杂度为O(nlogn)的算法来构建凸包。经典的算法如Graham扫描、Andrew's Monotone Chain算法或者QuickHull算法都可以达到这个时间复杂度，它们首先对边进行排序，然后逐步构建凸包，确保在处理过程中保持一定的单调性，从而避免了重复的工作并保证了正确性。 这些算法的基本思想是逐步构造凸包，从最底部的边开始，每次添加新的边时都确保不会破坏已构建部分的凸性。通过这种方式，可以在对边进行一次排序后，以近似线性的时间复杂度找到所有点的凸包。在实际应用中，这些算法对于处理大量数据的几何问题非常有用，例如在碰撞检测、路径规划等领域。