平面有限點(diǎn)集的空凸分劃問題.pdf

1、令P表示平面上處于一般位置的n-點(diǎn)集.設(shè)T()P，若T的凸包CH(T)中無P的點(diǎn)，則稱CH(T)所確定的凸多邊形為空凸多邊形，簡(jiǎn)稱T為空凸多邊形.|T|≤2時(shí)，我們也認(rèn)為T是空凸多邊形.設(shè)點(diǎn)集P被分劃成t個(gè)不交的子集S1，S2……St，若對(duì)于任意i=1，2……t，CH(Si)是一個(gè)凸|Si|-邊形，稱此分劃為P的凸分劃；這時(shí)，若對(duì)于任意的i≠j，有CH(Si)∩CH(Si)=φ，則稱此分劃為P的不交凸分劃；若對(duì)于任意的i，CH(Si)的

2、內(nèi)部不含P的點(diǎn)，記為CH(Si)≌φ(P)，則稱此分劃為P的空凸分劃，這里允許CH(Si)與CH(Sj)相交. 令Nπк(P)表示P的分劃π中凸k-邊形的個(gè)數(shù)，k為正整數(shù)；Nπ(P)表示P的分劃π中凸多邊形的個(gè)數(shù)，記：f(P)=：min{Nπ(P)：π是P的不交凸分劃}，F(xiàn)(n)=：max{f(P)：|P|=n}；g(P)=：min{Nπ(P)：π是P的空凸分劃}，G(n)=：max{g(P)：|P|=n}；fκ(P)=：max

3、{Nπк(P)：π是P的不交凸分劃}Fκ(n)=：min{fκ(P)：|P|=n}相關(guān)文獻(xiàn)對(duì)這些計(jì)數(shù)函數(shù)作了廣泛的研究，并獲得了若干重要結(jié)果.本文引入下列記法：gκ(P)=：max{Nπκ(P)：π是P的空凸分劃}，Gk(n)=：min{gκ(P)：|P|=n}.并得到了一些頗有意義的結(jié)果：G4(13)=3. Q(n)≥「7n/30」.G4(n)≥4n-1/17(n=17·2k-1-4，k≥1).對(duì)于15-點(diǎn)集P，若|V(P)|