極限法——解決幾何最優化問題的捷徑【關鍵字】最優值極限無窮小微調【概述】在平面幾何問題中我們經常會遇到一些求極值的問題。在這些問題中，自變量和目標函數可能涉及到坐標、斜率、長度、角度、周長、面積等等一些復雜的量，而且往往自變量還有一些復雜的約束條件，因此直接用函數求極值的方法是行不通或極其復雜的。這些問題中，變量往往有無窮多種取值方案（比如說點的取值范圍可能是整個平面或在某條直線上），所以無法枚舉每一種取值方案來找最值，這時往往能夠通過極限法證明：自變量取某些非特殊情況值時目標函數不可能是最優的——因為這時經過微調一個無窮小量比如旋轉一個無窮小的角度、微移一段無窮小的距離。在本文中，微量這一名詞就是指無窮小量：只要改變得足夠小（無窮小），就能使點的相對位置、線段的相交情況等不發生改變。能夠使得目標函數的值變得更優，從而剩下有限種特殊的取值情況可能成為最優解，通過枚舉所有特殊情況就能找到目標函數的最優解了。比如旋轉一個無窮小的角度、微移一段無窮小的距離。在本文中，微量這一名詞就是指無窮小量：只要改變得足夠小（無窮小），就能使點的相對位置、線段的相交情況等不發生改變。極限法的本質也就是對目標函數求導，如果導數不為0并且自變量不在定義域的邊界則不可能為最優值。這正是采用“極限法”來命名的原因。在另一些同類問題中，本來就可以通過枚舉有限個取值情況求出最優解，但是枚舉的量很大，時間復雜度較高，我們也可嘗試通過極限法來大大減少需要枚舉的情況，從而降低時間復雜度。以上就是極限法的大致思想，它的作用簡而言之就是化無限為有限，變有限為少量。正文極限法的應用實例非常的多，比如經典的最小矩形覆蓋平面上有n個已知點，求一個面積最小的矩形，使得所有已知點都在矩形的內部。問題，就是通過極限法證明了：最小矩形的某條邊必須過兩個已知點，平面上有n個已知點，求一個面積最小的矩形，使得所有已知點都在矩形的內部。然而極限法用起來的確有較大的困難，有時候證明起來非常困難，可能情況比較復雜，也可能不知道如何調整，需要用到三角函數之類的比較復雜的數學知識，因此真正掌握它需要扎實的數學功底，極強的觀察力以及必要的經驗是必不可少的。下面就來用極限法解決一些典型問題，從實例的分析中一步一步深入地認識極限法的用途和用法。例題一、巧克力問題描述：糖果廠有一種凸起的N（4≤N≤50）邊形巧克力，Kiddy和Carlson湊錢買了一塊，想把它用一刀割成兩半。兩半的大小必須相等，找出用以分割巧克力的分割線的最短長度。數學模型：已知N個點(Xi,Yi)1≤i≤N構成一凸包P{已知量}，求一條劃分線L，使得分割線兩側的面積相等{約束條件}，并且使L的長度{目標函數}最小。ASRBLSLSL=SR問題分析：設分割線的兩個端點分別為A、B，A、BASRBLSLSL=SRA在P的頂點上（或B在P的頂點上，此時交換AB）：顯然可以枚舉P中的一個頂點作為A，由分割線兩側面積相等這一約束條件直接確定B的位置，如圖1。圖1A、B都在P的邊上：枚舉A、B所在的兩條邊，設這兩條邊相交于C，如圖2：圖1AA’BCα+θγβαθθβ-θLAB’L’圖2設∠C=γ，∠CAB=α，∠CBA=β。當α≠β時，可以證明：把分割線L稍微旋轉一個無窮小量θ到L’并保持L’兩邊的面積相等，能夠使L’的長度小于L。證明如下：不妨設α>β，旋轉后L’仍與原來的兩邊相交（因為僅旋轉了一個無窮小量），交點為A’、B’，∠CA’B’=α+θ，∠CBA=β-θ。在三角形ABC中，有正弦定理：在三角形A’B’C中，有正弦定理：由于L和L’都是分割線，所以SABC=SA’B’C，即圖3所以L2>L’2，即L’<L。如果A、B所在的兩邊平行（即C在無窮遠處），也有相同的結論（如圖3）圖3因此若β>α時，L不可能為最短的分割線。同理，當β<α時，L也不可能是最短的。若L是不過P的頂點的最短的分割線，那么L與P的兩個夾角必然相等。這就是我們希望得到的，因為枚舉L兩個端點所在的邊后，L的斜率就確定了，再根據L的兩邊面積相等，就可以直接算出L的位置。得到了這些結論后，已能夠設計出O(N2)的算法。小結：通過此題，我們已經初次接觸到了極限法，并利用它得到了一個極其簡單的結論。使得自變量的取值范圍從無窮多條直線減少到了有限條，從而通過簡單的窮舉法解決。例題二、太空站SPACE(2003集訓討論試題之0039)問題描述：平面上有n(3≤n≤10000)個互不重合的點，要求一條直線，使得所有點到這條直線的距離和最小。數學模型：已知n點的坐標分別為：V1(x1,y1),V2(x2,y2),…Vn(xn,yn)。直線l(ax+by+c=0(ab≠0))的f值定義為，求min{f(l)}。試題分析：最容易想到的做法是枚舉所有的直線，得到最優值。但平面中的直線有無窮多條，怎樣的直線才有可能是我們要找的那一條呢？⑴可以規定直線l經過某一個已知點。因為：若l不經過任何一個已知點，則l兩側肯定有一側的點數不少于另一側，設多的一側有a個點，少的一側有b個點，將l往點多的那側平移一個微量△到l’，則f(l’)-f(l)=b△-a△=(b-a)△≤0，故f(l’)≤f(l)。（如圖4）ll’’圖4這樣不斷的往同一個方向平移，直到遇到第一個已知點，移動到l’’。可知f(l’’)≤ll’’圖4lα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2圖5⑵可以再規定直線l經過兩個已知點。原因如下：根據⑴，設llα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2圖5設直線繞V1逆時針旋轉一個很小的角度α(α0+)到l’，l順時針旋轉相同的角度α到l’’。（如圖6）只要α足夠小，就能使旋轉過程中不碰到其它已知點。如果αi=0，那么不論直線旋轉到l’還是l’’，Vi到直線的距離都嚴格減小了。(如圖7)αi≠0，則旋轉后的夾角分別變為αi+α，αi–α。由于lαlαl'l''α圖6所以

將每點所作的改變量相加可以得出：；而由直線l的最優性可以知道：，，矛盾。αααVαααV1Vi圖7至此，待枚舉的直線就變為了有限條，因此我們可以得到一個有效的算法了：min∞枚舉兩個點①根據兩個點確定直線h②計算直線nowf(h)③若now<min則lh,minnow通過極限法，我們已經將需考慮的直線從無線條轉化為了有限的n2條，從而能夠設計出一個有效算法解決本題。此算法的時間復雜度為O(n3)，需要進一步減少，也就是需要減少枚舉無用的直線。⑶定義a(l)為直線l上方（若直線豎直則為右方）的點數；b(l)為直線l上面的點數；c(l)為直線l下方（若直線豎直則為左方）的點數。ll’A圖8若l是最優的，那么必有a(l)+b(l)>c(l)且c(l)+b(l)ll’A圖8證明：若a(l)+b(l)≤c(l)且c(l)+b(l)≤a(l)，先把它往點較多（可能相等）的一側平移一個微量到達l’（如圖8），顯然根據⑴的相同證法有f(l’)≤f(l)。由于移動的是一個微量，所以l’上沒有其它已知點，在l’上任取一點A，把A看成結論⑵中的V1，繞A微調，用⑵的類似的證明方法有結論：f(l’)不可能為最優解，因此：f(l)也不可能為最優解。滿足結論⑴⑵⑶的直線集合設為E。可證|E|為n級，用旋轉法方法可以使得從E中的一條直線找下一條直線花O(n)的時間復雜度（旋轉一周后便能把所有的E中的直線找到），計算一條直線的f值也只需O(n)的時間復雜度，所以總的時間復雜度只需O(n2)。詳細的證明和算法請參閱我2003年的集訓作業詳細的證明和算法請參閱我2003年的集訓作業—0039解題報告。小結：本題的幾個證明過程并不復雜，從本質上說，這三個結論的證明方法都是和極限法緊密相關的：⑴通過平移一個微量證明某一類直線不可能為最優解，將l的取值范圍從所有平面中的直線降為過一個已知點的直線；⑵通過旋轉一個微量證明剩下的直線中的某一類不可能為最優解，從而使自變量l的取值范圍進一步減少到有限條。⑶通過先平移一個微量再旋轉一個微量將待考慮的直線條數從n2降到了n。從本題可以看到解決平面最優化問題的一般規律：遇到問題后容易產生這樣的猜想：即最優解是不是滿足某種性質？如果滿足，是不是滿足更特殊的性質？……這樣不斷地提出猜想并且嘗試證明，使得自變量的取值范圍不斷縮小，直至不能再小或者達到我們滿意的地步，剩下的工作就只需通過枚舉和計算解決了。提出的這些猜想有時是正確的、有的存在反例，有的是顯然的、有些證明卻很難。怎么形成猜想呢？最簡單有效的方法就是通過一些簡單的例子尋找一些規律，要靠認真地觀察才能得到直覺和靈感。怎么證明猜想呢？最容易的方法是拿幾個例子進行驗證，如果有反例，那么猜想失敗，需要部分的修改猜想或者提出全新的猜想。如果找不到反例呢？這并不代表猜想就是正確的。需要進行嚴密的分析來完整地證明，而極限法正是一個簡單、實用的分析工具。前面兩道題比較簡單，都直接提出了一種正確地猜想，并且證明的方法也很容易，但平時解決問題常常不是那么一帆風順，此時應該怎么做呢？讓我們來完整的考慮一個較為復雜的實際問題。例題三、導彈防御系統（自創試題）問題描述：某國的國界是一個凸多邊形，為了防衛，國王打算派工程部隊修建4座防御塔。戰爭爆發后敵人可能會偷襲其中的一座防御塔，而一旦遭偷襲、其余3座防御塔就會進入臨戰狀態，并且把由它們兩兩相連構成的三角形區域完全封鎖，狡猾的敵人會使封鎖的區域面積盡量小，而精明的國王則希望被敵人破壞后啟動的這個區域面積盡量大。數學模型：函數f(A,B,C,D)=min{S△ABC、S△ABD、S△ACD、S△BCD}平面上有一個凸n邊形P，請你在P的內部（可以在邊界）選擇4個點ABCD，使得f(A,B,C,D)最大。問題分析：首先，f函數是求4個量中的最小值，這很不好處理，究竟4個三角形中哪個最小呢？考慮平面上任意四點A、B、C、D，它們有下列3種排列情況：1、某三個點成一直線，此時f(A,B,C,D)=0；2、任意三點都不在同一直線上，但是某個點在另三個點圍成的三角形內，不妨設D在三角形ABC內部，此時f(A,B,C,D)=min{S△ABD,S△ACD,S△BCD,S△ABD+S△ACD+S△BCD}=min{S△ABD,S△ACD,S△BCD}，由于S△ABD+S△ACD+S△BCD=S△ABC，所以f(A,B,C,D)≤S△ABC/3，又由于ABCD任意選取，所以不妨選D為△ABC的重心，此時f(A,B,C,D)=S△ABC/3。因此某個點在另三個點構成的三角形內這類情況最大的f值，等于P中面積最大的三角形ABC的面積的1/3{①}。3、A、B、C、D是某個凸四邊形的四個頂點：ABCDA’圖9不妨設f{A,B,C,D}=S△BCD,那么分別過D、B作BC、DC的平行線交于A’ABCDA’圖9證明：如圖9，S△BCA’=S△BCD≤S△BCAA、B在A’D異側；S△A’CD=S△BCD≤S△ACDA、D在A’B異側，故結論成立)因此A’也在P內部，由于平行四邊形4個端點的f值=這個平行四邊形面積的一半，而A’BCD是平行四邊形，因此f(A’,B,C,D)=SABCD/2=S△BCD=f(A,B,C,D)，也就是說在可以把ABCD調整為P內某個平行四邊形的頂點而不使f值改變。因此f值最大的凸四邊形的f值=面積最大的平行四邊形的面積的一半！因此四個點構成凸四邊形這類情況的最大f值，等于P中面積最大的平行四邊形面積的1/2{②}。經過上面的轉化，我們把原來的最小值最大問題轉化為了某個特定值最大的問題，新的問題明顯比原問題更容易考慮。先來看①的求解，因為看起來它似乎比②簡單一些（實際上要簡單得多），首先假設A、B、C已經確定，看看它應滿足什么樣的條件。ABCA’圖10A、B、C可以都取P的頂點，而不會使面積減少。（換言之，A、B、CABCA’圖10如圖10，過A做BC的平行線l，則在l上或l的遠離BC的一側必然存在P一個的頂點A’。而A’到BC的距離≥A到BC的距離，所以S△A’BC≥S△ABC。故可以將A移至某個頂點而使得面積變大或不變。可以用O(N3)的算法枚舉P的3個頂點A、B、C，并求它們構成的三角形的面積的最大值S，S/3就是問題①的解。三角形的情況的確容易，因為可以讓A、B、C恰好為P的三個頂點，那么平行四邊形是否可以能用同樣的方法呢?這顯然是錯誤的，因為有可能P的任意4個頂點都不構成平行四邊形，如果真的A、B、C、D都是頂點那豈不是無解？如果不轉化為平行四邊形，而直接枚舉P的頂點做A、B、C、D如果不轉化為平行四邊形，而直接枚舉P的頂點做A、B、C、D計算f(A,B,C,D)也不會是最優的。比如下面這個例子：n=6,p={(-9.60,0.95)(-7.123.15)(-0.744.72)(7.330.98)(4.26-2.41)(-6.37-.152)}。最優解是26.35，而枚舉4個頂點算出來的f的最大值為19.40。首先還是要考慮縮小A、B、C、D的取值范圍。一、A、B、C、D都在P的邊界上（不一定是頂點！）。AABCDA’D’A’’BA’D’D’’C圖11證明：若A、B、C、D中某點不在P的邊界上，不妨設為A點。將AD沿著DA方向平移一個微量小到使A’D’都在P內部（不包括邊界）到A’D’（如圖11左），此時SA’BCD’=SABCD，并且A’、D’都不在邊界上。再把A’D’邊沿著BA’方向平移一個微量小到使A’’D’’都在P內部（不包括邊界）到A’’D’’（如圖11右），有小到使A’D’都在P內部（不包括邊界）小到使A’’D’’都在P內部（不包括邊界）二、A、B、C、D之一可以取P的頂點，而不會使面積減少。（換言之，A、B、C、D之一是P的頂點的平行形的面積的最大值=P內的平行四邊形面積的最大值）終于到了極限法該隆重登場的時候了！不過在證明這個命題之前先要介紹幾個新的概念：lgg'DBE圖12若直線l和g不平行，點E不在l和（或）g上，如果某個點B處在l上，另一個點D處在g上，并且BD關于點E中心對稱，那么稱線段lgg'DBE圖12引理一：(l,g,E)的平分線是唯一確定的。證明如下：如圖12，把g繞E旋轉180度到g’，g和g’關于E中心對稱，設l和g’相交于B（由于l和g相交、g和g’平行，故l和g’相交），設D為B關于中心E的對稱點。由于B在g’上所以D在g上，又因為B在l上，所以BD是(l,g,E)的平分線。另一方面，直線l與g’的交點只有一個，很容易知道不存在其它的BD是（l,g,E）的平分線。D''D'DB(B')(B'')E''EE'gl圖13引理二：若E’,E’’關于E中心對稱且EE’是微量，BD、B’D’、BD''D'DB(B')(B'')E''EE'gl圖13①EE’E’’平行于g（如圖13）。則B,B’,B’’重合，所以B’B’’關于B對稱，同時由中位線知識容易看出：DD’=2EE’=2EE’’=DD’’,而DD’D’’都在g上，所以D’D’’關于D中心對稱。②EE'E''平行于l。同理可證。③EE’E’’不平行于g和（或）l。由于E’E’’關于E中心對稱，所以E’E’’=2EE’’。設x=H(E’’,g)H(V,l)表示點V到直線l的距離H(V,l)表示點V到直線l的距離glDBED'B'E'D''B''E''圖14H(B’’,g)=glDBED'B'E'D''B''E''圖14H(B’,g)=2(x+2y)，所以BB’’=BB’。而B、B’、B’’都在同一直線l上，故B’B’’關于B對稱。考慮垂直于l的方向的距離可證DD’’=DD’，所以D’D’’關于D對稱。總結①②③得引理二得證。BCADB’A’圖15下面分兩種情況BCADB’A’圖15<1>某兩個頂點在同一條邊上（不妨設A、B在同一條邊上），根據圖15容易看出，因為存在一個面積不變的平行四邊形A’B’CD，使得某個點在P的頂點上。ABCDabcdE圖16<2>任意兩個頂點都不在同一條邊上，即A、B、C、D在P的4條不同的邊上，如圖16：設A在a上，B在b上，C在c上，D在d上，并且都不是邊的端點。aABCDabcdE圖16<2>-I、a//c并且b//d。bdDB圖17B1D1B2D2F此時E的位置是確定的。SABCD=4SABE=2AE*H(B,AC)保持AC邊不變，調整BD：過B點做AC的平行線e，b的某個端點V一定在e的遠離E的一側或在直線e上，此時把B往V方向移動一個微量到B’，同時D往反方向移動到D’。顯然有H(B’,AC)≥H(B,AC)，所以SAB’CD’不會比bdDB圖17B1D1B2D2FaabcdEACBabcdEACVDDV圖17<2>-II、若或者,情況就要復雜多了。不妨設，如圖17所示：設bd的延長線交于F，b的兩個端點為B1,B2（B1在F和B2之間），d的兩個端點為D1,D2（D1在F和D2之間），定義紅色區域為射線B2B1,D2D1與線段B1D1圍成的三角形區域，定義黃色區域為射線B1B2,D1D2與線段B2D2圍成的無限區域。由于A、B、C、D都在凸包P上，所以A和C有且僅有一個點（不妨設為C）在紅色區域中，另一個（不妨設為A）在圖中黃色區域中。接下來證明：固定A點、調整BCD使平行四邊形的面積增大若固定若固定C點，調整ABD將不能證明后面的結論!cclgbB''D''B'AD'E''E'C''BDECC'圖18設B所在邊b所在直線為l,D所在的邊所在的直線為g。在線段c上取兩個點C’C’’關于C對稱，并且CC’的距離趨近于0，設E’,E’’分別為AC’、AC’’的中點，設B’D’和B’’D’’分別是(l,g,E’)、(l,g,E’’)的平分線。根據對角線互相平分的四邊形是平行四邊形得：AB’C’D’和AB’’C’’D’’都是平行四邊形，E’和E’’分別是它們的中心。只要我們能夠證明SAB’C’D’+SAB’’C’’D’’>2SABCD，那么AB’C’D’和AB’’C’’D’’中至少有一個面積比SABCD大，也就證明了結論。而SABCD=4SADE；SAB’C’D’=4SAD’E’；SAB’’C’’D’'=4SAD’’E’’；因此可以證明等價的結論：SAD’E’+SAD’’E’’>2SADE。因為E’E’’關于E中心對稱，由引理二可以知道：D’D’’關于D中心對稱。另外，由于EE’平行于g，而g與c相交，因此EE’與DD'相交，不妨設它們交于X，如圖19：1、1、圖19所示的為ADX為逆時針順序時的情況；2、當ADX為順時針方向時，同理可證；3、當D、X重合時亦可證明（如圖20），方法略。cgE'D'XAE''EDD''圖19D''D''E''DAEE'D'圖20SAD’E’+SAD’’E’’=(SAD’’XE’-SAD’D’’-SD’E’E’’-SXE’’D’)+(SAD’’XE’-SAE’E’’-SE’’D’D’’-SXE’’D’)=2SAD’’XE’-2SXE’’D’-SAD’D’’-SAE’E’’-SD’E’E’’-{SE’’D’D’’}2SADE =2(SAD’’XE’-SADD’’-SAEE’-SD’EE’’-SEDD’-SXE’’D’)=2SAD’’XE’-2SXE’’D’-SAD’D’’-SAE’E’’-SD’E’E’’-{SED’D’’}SAD’E’+SAD’’E’’-2SADE=SED’D’’-SE’’D’D’’>0故SAD’E’+SAD’’E’’>2SADE所以有SAD’E’>SADE或SAD’’E’’>SADE，因此有SAB’C’D’>SABCD或SAB’’C’’D’’>SABCD，也就是說當ABCD在P的邊界上但都不是P的頂點時，ABCD的面積肯定不是P中平行四邊形的面積的最大值。綜合上述證明得：A、B、C、D之一可以取P的頂點，而不會使面積減少。下面簡單的說明為什么不能固定C點調整ABD，因為此時D''DD'的相對位置發生了改變，如圖21，此時SAE'D'+SAE''D''并不是恒大于2SAED的。小結：結論二比結論一的得到困難了許多，回顧證明的過程：首先我們不得不分了許多種情況來一一證明，好在大多數情況都是較為特殊的，證明較為容易。情況<2>-II是一般的，也是最難證的：證明過程中，先選擇固定A點，然后在C的兩側取兩個距離無限小的對稱點，最后往兩個方向分別調整ABCD到AB’C’D’和AB’’C’’D’’。引理二告訴我們一個簡單的性質：B’B’’、D’D’’分別關于B和D對稱，利用這一簡單的性質用就能得到SAB’C’D’+SAB’’C’’D’’>2SABCD。<2>-II的證明是個比較復雜的極限法，此次調整的量是距離而不是角度，因為很明顯調整距離時各個量的改變都容易得到，而如果采用角度，恐怕就會有更為復雜的數學式子了！這說明了觀察能力在極限法中的重要作用。另外，證明中和例題2一樣采用了是2次調整做和，為什么不能直接調整1次呢？有兩個主要原因：我們并不知道往哪一側調整后能使目標函數更優（并不是往任意方向調整都會變優的）；（2次調整后的目標函數的和）與（原函數的兩倍）的差很容易計算，把它們拆成一些三角形的和后大部分的項做差后都被抵消了。如果只調整1次，我們需要計算在什么時候往什么方向調整（而與調整2次相比，這是一項額外的工作），而且證明過程也將更為復雜。2次調整做和方法是極限法證明中經常要用到的手段。總結了這么多，是不是有些太早了？我們僅僅證明了結論二，但是滿足結論二的平行四邊形仍然有無窮多個！我們并沒有完整地解決原問題。不過，你也許馬上就會猜想：規定A、B、C、D中有兩個點是P的頂點，是不是也不影響最優值？看起來似乎的確能夠利用剛才類似的方法進行證明：首先由結論二可設A是P的頂點而B、C、D在P的邊上，由于固定B、C或D時，A可