《第65講 凸集與凸包(原)》由會員分享，可在線閱讀，更多相關《第65講 凸集與凸包(原)（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、word第65講 凸集與凸包本節(jié)主要內(nèi)容是：凸集、凸包的概念以與用凸集凸包來解有關的題凸集：平面上的點集，如果任何兩點在這個點集內(nèi)，如此連這兩點的線段上的所有的點也在此點集內(nèi)，就說該點集是一個凸集線段、射線、直線、圓與帶形、整個平面等都是凸集兩個凸集的交集還是凸集；任意多個凸集的交集也仍是凸集凸包：每個平面點集都可用凸集去蓋住它，所有蓋住某個平面點集的凸集的交集就是這個平面點集的凸包 或者可以形象地說：如果把平面上的點集的每個點都插上一根針，然后用一根橡皮筋套在這些針外，當橡皮筋收緊時橡皮筋圍出的圖形就是這個點集的凸包 平面點集的直徑 平面點集中的任意兩點距離的最大值稱為這個平面點集的直徑例如
2、，圓的直徑就是其直徑，有無數(shù)條；線段的直徑就是其本身；正三角形的三個頂點組成的點集的直徑就是其邊長，有三條；平行四邊形的直徑是其較長的對角線；A類例題例1定理 任何一個平面點集的凸包是存在且唯一的分析 存在惟一性的證明，即證明滿足某條件的集A存在且惟一存在通常先證明存在性，即證明有滿足條件的集合A再用反證法證明惟一性，即假如滿足條件的集A不惟一，或說明會引出矛盾，或得出其余集均必需與A相等的結論證明 由于全平面是一個凸集，故任何平面點集都可用全平面蓋住，即能被凸集蓋住，從而蓋住該凸集的所有凸集的交集存在，即凸包存在而如果某個凸集A有兩個凸包M1與M2，如此M1M2也能蓋住凸集A，且M1M2M1
3、，但M1是A的凸包，故M1M1M2，故M1M2M1同理M1M2M2即M1M2例2 定理 如果一個點集M是由有限個點組成，且其中至少有三個點不共線，如此M的凸包是一個凸多邊形分析 可以構造一個尋找凸包的方法，來說明命題的正確性證明 由于M為有限點集，故存在一條直線l，使M中的一個或幾個點在l上，其余的點都在l同旁(這只要任畫一條直線，如果點集M中的點在直線l的兩旁，如此讓直線按與此直線垂直的方向平移，即可得到滿足要求的直線)取l上的兩個方向中的一個方向為正向，此時，按此正向，不妨設M中不在l 上的點都在l的左邊在l上沿其正向找出M中的最后一個點A1，把l繞A1逆時針旋轉，直到遇到M中的另外的點，
4、又找出此時l上的M中的最后一個點A2，此時再讓l繞A2逆時針旋轉，依此類推，直到最后繞Ak旋轉又遇到A1為止(由于M是有限點集，故這樣的旋轉不可能一起下去)這時，凸多邊形A1A2Ak即為M的凸包情景再現(xiàn)1證明圓面(圓與圓內(nèi)所有的點組成的集合)是凸集2平面上任意給定5個點，其中任三點不共線，如此可選出4個點，這四點能構成一個凸四邊形的四個頂點B類例題例3 海萊定理：定理(海萊定理) 對于假如干個(個數(shù)n3)凸集，如果任意三個凸集都有一個公共點，那么存在一個點同時屬于每個凸集分析 先證明簡單情況，再用數(shù)學歸納法證明本定理證明 對于n3，顯然成立當n3時，先取4個這樣的凸集F1，F(xiàn)2，F(xiàn)3，F(xiàn)4設點
5、P1F2F3F4，點P2F1F3F4，點P3F1F2F4，點P4F1F2F3假如P1、P2、P3、P4中有兩個點重合，例如P1=P2，如此P1F1F2F3F4；設此四點互不一樣 假如此四點中有三點共線，例如P1、P2、P3共線，且P2在P1、P3之間，如此P2F1F2F3F4；假如此四點中無三點共線，由上可知P1P2P3F4，P1P2P4F3，P1P3P4F2，P2P3P4F1，此時， 假如P1、P2、P3、P4的凸包為凸四邊形，如此此凸四邊形對角線交點K此四個三角形； 假如P1、P2、P3、P4的凸包為三角形，例如凸包為P1P2P3，如此P4此四個三角形總之，存在點KF1F2F3F4即對于n
6、4定理成立當n4時，易用數(shù)學歸納法證明說明 請讀者完成用數(shù)學歸納法證明一般情況例4平面上任給5個點，以表示這些點間最大的距離與最小的距離之比，證明：2sin541985年全國聯(lián)賽分析 這類問題總是先作出凸包，再根據(jù)凸包的形狀分類證明這樣分類證明問題可以使每一類的解決都不困難，從而使問題得到解決證明 假如此五點中有三點共線，例如A、B、C三點共線，不妨設B在A、C之間，如此AB與BC必有一較大者不妨設ABBC如此22sin54 設此五點中無三點共線的情況 假如此五點的凸包為正五邊形如此其五個內(nèi)角都108五點的連線只有兩種長度：正五邊形的邊長與對角線，而此對角線與邊長之比為2sin54 假如此五點
7、的凸包為凸五邊形如此其五個內(nèi)角中至少有一個內(nèi)角108設EAB108，且EAAB，如此AEB36，2cosE2cos362sin54 假如此五點的凸包為凸四邊形ABCD，點E在其內(nèi)部，連AC，設點E在ABC內(nèi)部，如此AEB、BEC、CEA中至少有一個角120108，由上證可知，結論成立 假如此五點的凸包為三角形ABC，如此形內(nèi)有兩點D、E，如此ADB、BDC、CDA中必有一個角120，結論成立 海爾布朗(Heilbron)問題：設平面上給定n個點，每兩點間距離的最大值與最小值的比為n，求n的下確界現(xiàn)在得到的結論有：4；52sin54；62cos72，l8，猜想n2cos例5 每個有界平面點集，都
8、有且只有一個蓋住它的最小圓如果這個集合是凸集，那么在這個圓上或者有此凸集的兩個點，這兩點是此圓的一條直徑的兩個端點；或者有此集的三個點，此三點為頂點的三角形是銳角三角形分析 由于“有界平面點集這一概念涉與點集廣泛，所以要就一般情況來討論但仍可采取從簡單到復雜的方法，先解決簡單的情況，以此為根底再解決一般情況證明 首先，假如M是平面有界點集，故可以作一個半徑足夠大的圓把它蓋住在所有蓋住M的圓中有且只有1個最小圓，如果有兩個最小圓O1、O2蓋住M(顯然這兩個圓半徑應該相等)，此二圓不重合，且都蓋住了M，于是其公共局部也蓋住了M以此二圓的公共弦為直徑作圓O，如此此圓蓋住了兩圓的公共局部，于是也蓋住了
9、M，但此圓比O1、O2小現(xiàn)證明此結論的后面局部：1 首先，蓋住有界凸集M的最小圓與M如果沒有公共點(圖1)，保持圓心O不動，縮小其半徑，直到與M有公共點為止，此時，蓋住M的圓半徑的半徑變小2 如果蓋住M的圓與M只有唯一的公共點(圖2)，如此沿半徑方向稍移動圓，又得13 如果M上有兩個點A、B在圓上，這兩點不是同一條直徑的端點，且優(yōu)弧上沒有圓上的點，如此沿與AB垂直的方向移動圓即可得到1例6設G是凸集，其面積用g表示，且其邊界不包括直線段與尖點即過其邊界上每一點都有一條切線且每條切線與G的邊界只有一個公共點設PQRS是G的外切四邊形中面積最小的一個，A，B，C，D分別是它的四條邊與G的邊界的切點
10、如此ABCD是面積大于的平行四邊形分析 利用微調(diào)來說明此題證明 先證明一個引理：假如A是PQ上的切點，如此A為PQ的中點反設A不是PQ的中點，不妨設APAQ，現(xiàn)把點A向P微移到A，切線PQ移動為PQ(如圖)，只要A足夠靠近A，就仍有APAQ設PQ、PQ交于點O，如此O、A、A三點充分靠近OPOQ，OPOQ于是SOPPSOQQ此時SPQRSSPQRSSOQQSOPPSPQRS，即得出比PQRS面積還要小的外切四邊形與PQRS最小的假設矛盾于是得A為PQ中點同理B、C、D分別為相應邊的中點因順次連結四邊形各邊中點得到的是平行四邊形即ABCD是平行四邊形而SPQRSg，所以SABCDSPQRSg說明
11、 此題的證明含有連續(xù)與極限的思想情景再現(xiàn)3在平面上有n(n4)個點組成的點集M，如果任取其中4個點都是凸四邊形的四個頂點，如此此n個點是一個凸n邊形的頂點4平面上任意給出6個點，其中任意三點不在一條直線上，證明：在這6個點中，可以找到3個點，使這3個點為頂點的三角形有一個角不小于1205在由n(n3)個點組成的點集M中，如果有一個點至少是三條直徑的端點，如此M中必有一點至多是一條直徑的端點6是否任意一個凸四邊形都可用折線分成兩局部，使每局部的直徑都小于原四邊形的直徑？C類例題例7設A、B是平面上兩個有限點集，無公共元素，且AB中任意三點都不共線，如果A、B中至少有一者的點數(shù)不少于5個，證明存在
12、一個三角形，它的頂點全在A中或全在B中，它的內(nèi)部沒有另一個集合中的點IMO25預選題分析 抓住5點組來討論證明 設集合A中的點不小于5個，從中選出5個點A1、A2、A3、A4、A5，使這5點的凸包內(nèi)沒有其他A的點，否如此可用其內(nèi)部的點來代替原來的某些點 假如此凸包為五邊形，取A1A2A3、A1A3A4、A1A4A5，假如這三個三角形中的任何一個內(nèi)部無集合B中的點，如此此三角形即為所求，假如此三個三角形內(nèi)都有B中的點如此在每個三角形內(nèi)取一個B中的點，這三點連成的三角形內(nèi)部沒有A中的點 假如此凸包為四邊形A1A2A3A4，內(nèi)部有一個點A5，如此可連得4個三角形：A5A1A2、A5A2A3、A5A3
13、A4、A5A4A1，假如任一個內(nèi)部沒有B中的點，如此此三角形即為所求，假如每個三角形內(nèi)部都有B中的點，如此每個三角形內(nèi)取一個B中的點，連成兩個互不重疊的三角形，其中至少有一個三角形內(nèi)部沒有A中的點，即為所求 假如此凸包為三角形，內(nèi)部有兩個點，如此可把凸包分成5個三角形，如果每個三角形內(nèi)都有B中的點如此5個點分布在直線A4A5兩側，必有一側有其中三個點，這三點連成的三角形內(nèi)就沒有A中的點說明 題中有“不少于5點的條件，所以就只要研究5個點的情況例8平面上任給5個點，其中任3點不共線，如此在以這些點為頂點的三角形中，至多有7個銳角三角形證明 5個點中任取3個點為頂點的三角形共有10個 假如這5點的
14、凸包為凸五邊形，這個五邊形至少有兩個角非銳角(因五邊形內(nèi)角和為540，假如五邊形的內(nèi)角中有4個銳角，如此此4個角的和360，于是另一個角180)這兩個非銳角相鄰或不相鄰假如兩個非銳角相鄰，如圖中A、B非銳角，連BE，如此四邊形BCDE至少有一個角非銳角，于是圖中至少有3個角非銳角，即至少有三個非銳角三角形從而至多有7個銳角三角形假如兩個非銳角不相鄰，如圖中A、C非銳角，如此EAB、BCD非銳角三角形連AC，如此四邊形ACDE中至少有一個非銳角，于是圖中至少有三個非銳角三角形，即至多有7個銳角三角形 假如這個凸包為四邊形ABCD，E在形內(nèi)如此四邊形ABCD至少有一個內(nèi)角非銳角，AEB、BEC、C
15、ED、EDA中至少有一個非銳角(否如此四個角的和少于360)，AEC、BED中至少有一個非銳角(否如此BEC180)，于是圖中至多有7個銳角三角形，假如凸包為三角形ABC，D、E在形內(nèi)，如此ADB、BDC、CDA中至多有一個銳角，AEB、BEC、CEA中至多有一個銳角，即圖中至多有6個銳角三角形綜上可知，結論成立說明 利用五點組的特點解決問題此題即是下面情景再現(xiàn)第7題的引理情景再現(xiàn)7平面上任給100個點，其中任3點不共線，如此在以這些點為頂點的三角形中，至多有70%的三角形是銳角三角形(IMO126)8設G是凸集，其面積用g表示，且其邊界不包括直線段與尖點即過其邊界上每一點都有一條切線且每條切
16、線與G的邊界只有一個公共點ABCD是G的所有內(nèi)接四邊形中面積最大的一個，過A，B，C，D作G的切線得到四邊形PQRS證明：PQRS是G的面積小于2g的外切平行四邊形習題651 證明：平面點集M的直徑等于它的凸包M的直徑 由n(3n120(也可連AC、AD把五邊形分成三個三角形來證) 假如這6個點的凸包為六邊形，由于六邊形的內(nèi)角和為4180720，故至少有一個內(nèi)角1205證明 設M的直徑為d，且AB、AC、AD是三條直徑，且AB在CAD內(nèi)部分別以A、B為圓心d為半徑作圓如此M必在二圓的公共局部中，如果從點B還能引出一條直徑BE(EA)，不妨設E與C在AB的同側，于是四邊形ADBE為凸四邊形，從而
17、ABDEADBE得DEd這與直徑定義矛盾6解：設凸四邊形ABCD中，DABC為正三角形，邊長為d點D到A、B、C的距離都AB，如此此四邊形有三條直徑一條折線無論把ABCD分成怎樣的兩局部，A、B、D三點中總有兩點在同一局部于是這一局部的直徑仍為d7解 100個點中，共可組成C個三角形，每次取5個點共有C個五點組每個五點組中都至多有7個銳角三角形而每個三角形都在C個五點組中，因此，銳角三角形至多個，故銳角三角形至多占70%8證明 根據(jù)以下一個顯然的事實：A、B為G的弧上兩個定點，C為弧上一動點，當G的在點C處的切線MNAB時，ABC的面積取得最大值設ABCD是凸集G的內(nèi)接四邊形中面積最大者連AC
18、，固定A、C，如此當且僅當點B處的切線平行于AC時ACB的面積最大于是知當且僅當B、D處的切線都平行于AC時ABCD的面積才能最大，同理連BD，仍有A、C處的切線平行于BD時，ABCD的面積最大，即PQRS是平行四邊形SPQRS2SABCD2g“習題67解答：1證明：M的直徑為d，而M的直徑為d設A、B是M中距離等于d的兩個點M蓋住M，由于MM，故A、BM于是dd；又假如dd，即凸包上有兩點A、B，使ABd，于是必存在點CAB，使AC上沒有M的點于是可以用更小的凸集蓋住M，與凸包定義矛盾 證明：n3時，3個點的點集最多連出3條線段，即至多有3條直徑，而正三角形的三個頂點所成的集合恰有3條直徑即
19、kn成立設有n1個點的點集的直徑數(shù)n1對于n個點的點集，假如點集中的每個點引出的直徑數(shù)2，如此直徑數(shù)2n2n假如有某點引出的直徑數(shù)3，如此必有一點，該點引出的直徑數(shù)為1去掉此點，如此由歸納假設，余下n1點的直徑數(shù)n1，故原來的直徑數(shù)n故證2證明：設AB、CD是平面凸集的兩條不相交的直徑如此A、B、C、D的凸包為線段，這不可能A、B、C、D的凸包假如為三角形ABC，D在DABC內(nèi)，有BDmaxBC、BAAB矛盾假如A、B、C、D的凸包為四邊形ABCD，如此ACBDABCD，于是AC、BD中至少有一個AB，與AB為直徑矛盾3證明：n3時命題顯然成立，對于n4O1、O2、O3、O4的半徑都為r，O1
20、蓋住P2、P3、P4；O2蓋住P1、P3、P4；O3蓋住P1、P2、P4；O4蓋住P1、P2、P3現(xiàn)以P1、P2、P3、P4為圓心，作半徑為r的圓于是O1在P2、P3、P4內(nèi)，從而P2、P3、P4有公共點，由此可知，P1、P2、P3、P4中任意三個都有公共點，由海萊定理，為四個圓有一個公共點設此點為Q，由于點Q在四個圓內(nèi)，故Q到P1、P2、P3、P4的距離都不超過r，從而以Q為圓心，r為半徑作圓可把P1、P2、P3、P4蓋住以上證明對于n個點也成立4證明：假如凸集F只有1條對稱軸l，如此lL，但l也是自己的對稱軸，故lS于是LS假如F的對稱軸不只1條，任取其一條對稱軸l1，如此l1L，只要證明
21、l1S即可即只要證明對于F的任一對稱軸l2，其對稱直線l3也是F的對稱軸取F的任一點P，PF，由于l1是F的對稱軸，如此P關于l1的對稱點P1F同理，P1關于l2的對稱點P2F，P2關于l1的對稱點 P3F但P3與P關于l3對稱即l3是F的對稱軸故證5解： 最多可以連出10個鈍角三角形(如圖，以AB為直徑作半圓面，內(nèi)取一點C，以BC、AC為直徑作半圓面，三個半圓面的交的內(nèi)部取點E，以BE、AE為直徑作半圓，五個半圓面的交內(nèi)取點D，如此10個三角形都是鈍角三角形例中已證至少3個鈍角三角形(如圖可畫出只有3個鈍角三角形的情況)6證明 設所求比為 如果其中有三點共線，例如A、B、C三點共線，不妨設B
22、在A、C之間，如此AB與BC必有一較大者不妨設ABBC如此2 如果此四點中無三點共線，如此此四點的凸包為四邊形或三角形 假如此凸包為三角形，凸包三角形是直角三角形，三邊滿足abc如此c2a2b22a2，從而凸包三角形是鈍角三角形，三邊滿足abc，如此c2b2a22abcosCb2a22a2，得凸包三角形是銳角三角形ABC，如此形內(nèi)有一點D，如此DAB、DBC、DCA中，ADBBDCCDA360，故此三角不可能都90，否如此此三角之和270，矛盾即此三個三角形中至少有一個是鈍角三角形由上證知，結論成立 假如此四點的凸包為四邊形，ABCD，如此ABC、BCD、CDA、DAB不可能都是銳角即至少有一
23、個角非銳設ABC90，如此由上證知，結論成立 當此四點的凸包為正方形時，顯然有綜上可知成立7解：正方形的m41，其余的情況m44對于5點問題，假如凸包為三角形ABC，取形內(nèi)的一點D，如此DDAB、DDBC、DDCA中必有一個DABC的面積的于是所求比3凸包為四邊形同此假如凸包為五邊形ABCDE，取面積最小的三角形，如此必有兩邊為五邊形的兩邊(假如只有一邊，可知此五邊形為凹)，設面積最小的三角形為DABEAB、AE為邊如此其余兩頂點在EAB內(nèi)部，又作BMAE，ENAB，交于K，如此其余兩個頂點在MKN內(nèi)部或邊上(DABE面積最小) 先研究兩個頂點在邊上的情況，假如點C、D在角的邊上，其中D與BE
24、距離較小，作DCBE，交KN于C，如此點C所得的面積比不超過C所得的面積比DCDB、DCDE面積DABE面積，類似構造五條對角線都分別與不相鄰的邊平行的五邊形，不妨設SDABE1，如此SDABCSDBCDSDCDESDDEASDACF1，設SAEFx，如此SDEF1xSDCDFx，于是 但，即 于是得 x2 +x10解得滿足題意的根為 x于是 此五邊形的m5對于C、D不在MKN邊上的情況，可轉化為以上情況8證明： 1 假如ABC是非銳角三角形，如此r(A、B、C)max，max，r(A，B，C(蓋住ABC的最小圓是以最長邊為直徑的圓，而ABC可能為銳角三角形，也可能是鈍角三角形或直角三角形)2 假如ABC與ABC都是非鈍角三角形，蓋住它們的最小圓都是其外接圓于是必存在一對角(例如A與A)，滿足90AA，假如不存在這樣的一對角，如此AA，BB，CC，與三角形內(nèi)角和定理矛盾于是r(A，B，C)r(A，B，C)3假如ABC是銳角三角形，ABC非銳角三角形不妨設C90，現(xiàn)作一個輔助ABC，使CBCB，ACB90，如此r(A，B，C)r(A，B，C)ABC是銳角三角形，AB2AC2CB2AC2CB2AC2CB2AB2即ABAB但ABC與ABC都是非鈍角三角形，由2可知r(A，B，C)r(A，B，C)r(A，B，C)r(A，B，C)綜上可知，所證成立文檔
第65講 凸集與凸包(原)
