基于決策樹模型的求凸包算法下界的證明.ppt

基于決策樹模型尋找凸包算法運行時間下界的證明,證明思路,樹的高度至少為找到足夠多的葉子(張)構(gòu)造出能到達這些葉子的輸入怎么構(gòu)造？,證明步驟,構(gòu)造出種具有特定性質(zhì)的不同輸入為每種輸入關(guān)聯(lián)樹中的一片葉子到達這片葉子的輸入具有某些特性不同的輸入不能關(guān)聯(lián)同一片葉子得到張葉子，即可證明樹的高度,構(gòu)造輸入,構(gòu)造輸入,構(gòu)造輸入,關(guān)聯(lián)葉子,選用合適的方法為每種類型的輸入關(guān)聯(lián)樹中的一片葉子,引理一,定義,剛才定理中找到的葉子就是，也就是與輸入相關(guān)聯(lián)的葉子,證明,利用決策樹對輸入集合進行劃分，將其劃分為有限個非空集合，每個集合對應(yīng)于一片葉子其中至少有一個集合測度不為0，因為的測度不為0集合可以寫為:,證明,考慮集合：上面集合中的等式必須對于是平凡的，不然會成為中的零測集。,證明,考慮集合：由中僅有不等式對有效故為開集。引理一的證明完成,思考,什么樣的輸入正好可以到達這片葉子？到達這片葉子的輸入需要滿足的條件究竟是什么？,猜測,需要滿足的條件中那些等式其實就是對一些三角形面積的關(guān)系的限制也就是對于，的一些限制,引理二,設(shè)是一個次數(shù)不超過二的多項式。若有對于所有的成立，那么就有其中均為常數(shù)。,證明,把寫為合適的形式由與之對應(yīng)的的性質(zhì)（在一個開集上始終為0）推出中的一些系數(shù)進一步推導(dǎo)出可以寫為我們想要的形式,證明,證明,證明,進一步的猜想,到達這個葉子的條件其實就是就是那些三角形的面積都得為0才可以,引理三,對于任意的一個輸入,如果到達了葉子節(jié)點,那么這個輸入一定會滿以下關(guān)系：對任意的,證明,輸入要到達這個葉子需要滿足的條件為：,證明,輸入要到達這個葉子需要滿足的條件為：,證明,輸入要到達這個葉子需要滿足的條件為：記這個式子為,左邊的常數(shù)矩陣為,證明,若,則等價于證明完成,證明,若,則等價于我們要構(gòu)造一個輸入，這個輸入滿足所有的這些限制條件（因此這個輸入會到達這個葉子，但是這個輸入的凸包的頂點集合卻不是前n個點，由此得到矛盾,證明思路,在原來的輸入上做修改，讓新輸入既滿足三角形的面積關(guān)系，又滿足那些不等式滿足不等式只要和原來的輸入距離足夠近要滿足的面積關(guān)系只是一種比例關(guān)系，控制好各三角形的面積之比就可以了,證明,證明,證明,證明,證明,顯然構(gòu)造的這個輸入的凸包頂點集合不為前n個點但是這個輸入滿足到達這個葉子的所有條件，那么它應(yīng)該和其他到達這個葉子的輸入一樣，得到凸包為前個點的結(jié)論矛盾！所以那個矩陣的秩必須為引理三由此得到證明,引理四,若,那么就有,證明,若,且有那么由這兩個排列按照引理三會推出兩種到達這個葉子的輸入需要滿足的條件一種排列推出的需要滿足的條件是與另外一種排列對應(yīng)的輸入