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

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