第65讲 凸集与凸包(原)

《第65讲 凸集与凸包(原)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第65讲凸集与凸包本节主要内容是：凸集、凸包的概念以及用凸集凸包来解有关的题．凸集：平面上的点集，如果任何两点在这个点集内，则连这两点的线段上的所有的点也在此点集内，就说该点集是一个凸集．线段、射线、直线、圆及带形、整个平面等都是凸集．两个凸集的交集还是凸集；任意多个凸集的交集也仍是凸集．凸包：每个平面点集都可用凸集去盖住它，所有盖住某个平面点集的凸集的交集就是这个平面点集的凸包．或者可以形象地说：如果把平面上的点集的每个点都插上一根针，然后用一根橡皮筋套在这些针外，当橡皮筋收紧时橡皮筋围出的图形就是这个点集的凸包．平面点集的直径平面点集中的任意两点距离的最大值称为

2、这个平面点集的直径．例如，圆的直径就是其直径，有无数条；线段的直径就是其本身；正三角形的三个顶点组成的点集的直径就是其边长，有三条；平行四边形的直径是其较长的对角线；…．A类例题例1定理任何一个平面点集的凸包是存在且唯一的．分析存在惟一性的证明，即证明满足某条件的集A存在且惟一存在．通常先证明存在性，即证明有满足条件的集合A．再用反证法证明惟一性，即若满足条件的集A不惟一，或说明会引出矛盾，或得出其余集均必需与A相等的结论．证明由于全平面是一个凸集，故任何平面点集都可用全平面盖住，即能被凸集盖住，从而盖住该凸集的所有凸集的交集存在，即凸包存在．而如果某个凸集A有两个

3、凸包M1与M2，则M1∩M2也能盖住凸集A16，且M1∩M2ÌM1，但M1是A的凸包，故M1ÌM1∩M2，故M1∩M2＝M1．同理M1∩M2＝M2．即M1＝M2．例2定理如果一个点集M是由有限个点组成，且其中至少有三个点不共线，则M的凸包是一个凸多边形．分析可以构造一个寻找凸包的方法，来说明命题的正确性．证明由于M为有限点集，故存在一条直线l，使M中的一个或几个点在l上，其余的点都在l同旁(这只要任画一条直线，如果点集M中的点在直线l的两旁，则让直线按与此直线垂直的方向平移，即可得到满足要求的直线)．取l上的两个方向中的一个方向为正向，此时，按此正向，不妨设M中不在

4、l上的点都在l的左边．在l上沿其正向找出M中的最后一个点A1，把l绕A1逆时针旋转，直到遇到M中的另外的点，又找出此时l上的M中的最后一个点A2，此时再让l绕A2逆时针旋转，依此类推，直到最后绕Ak旋转又遇到A1为止(由于M是有限点集，故这样的旋转不可能一起下去)．这时，凸多边形A1A2…Ak即为M的凸包．情景再现1．证明圆面(圆及圆内所有的点组成的集合)是凸集．2．平面上任意给定5个点，其中任三点不共线，则可选出4个点，这四点能构成一个凸四边形的四个顶点．B类例题例3海莱定理：定理(海莱定理)对于若干个(个数n≥3)凸集，如果任意三个凸集都有一个公共点，那么存在一

5、个点同时属于每个凸集．16分析先证明简单情况，再用数学归纳法证明本定理．证明对于n＝3，显然成立．当n＞3时，先取4个这样的凸集．F1，F2，F3，F4．设点P1∈F2∩F3∩F4，点P2∈F1∩F3∩F4，点P3∈F1∩F2∩F4，点P4∈F1∩F2∩F3．若P1、P2、P3、P4中有两个点重合，例如P1=P2，则P1∈F1∩F2∩F3∩F4；设此四点互不相同．⑴若此四点中有三点共线，例如P1、P2、P3共线，且P2在P1、P3之间，则P2∈F1∩F2∩F3∩F4；⑵若此四点中无三点共线，由上可知ΔP1P2P3ÌF4，ΔP1P2P4ÌF3，ΔP1P3P4ÌF2，Δ

6、P2P3P4ÌF1，此时，①若P1、P2、P3、P4的凸包为凸四边形，则此凸四边形对角线交点K∈此四个三角形；②若P1、P2、P3、P4的凸包为三角形，例如凸包为ΔP1P2P3，则P4∈此四个三角形．总之，存在点K∈F1∩F2∩F3∩F4．即对于n＝4定理成立．当n＞4时，易用数学归纳法证明．说明请读者完成用数学归纳法证明一般情况．例4平面上任给5个点，以λ表示这些点间最大的距离与最小的距离之比，证明：λ≥2sin54°．（1985年全国联赛）分析这类问题总是先作出凸包，再根据凸包的形状分类证明．这样分类证明问题可以使每一类的解决都不困难，从而使问题得到解决．证明⑴

7、若此五点中有三点共线，例如A、B、C三点共线，不妨设B16在A、C之间，则AB与BC必有一较大者．不妨设AB≥BC．则≥2＞2sin54°．⑵设此五点中无三点共线的情况．①若此五点的凸包为正五边形．则其五个内角都＝108°．五点的连线只有两种长度：正五边形的边长与对角线，而此对角线与边长之比为2sin54°．②若此五点的凸包为凸五边形．则其五个内角中至少有一个内角≥108°．设∠EAB≥108°，且EA≥AB，则∠AEB≤36°，∴＝≥＝2cosE≥2cos36°＝2sin54°．③若此五点的凸包为凸四边形ABCD，点E在其内部，连AC，设点E在△ABC内部，则