平面有限點集的空凸分劃問題.pdf

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

2、內部不含P的點，記為CH(Si)≌φ(P)，則稱此分劃為P的空凸分劃，這里允許CH(Si)與CH(Sj)相交. 令Nπк(P)表示P的分劃π中凸k-邊形的個數(shù)，k為正整數(shù)；Nπ(P)表示P的分劃π中凸多邊形的個數(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}相關文獻對這些計數(shù)函數(shù)作了廣泛的研究，并獲得了若干重要結果.本文引入下列記法：gκ(P)=：max{Nπκ(P)：π是P的空凸分劃}，Gk(n)=：min{gκ(P)：|P|=n}.并得到了一些頗有意義的結果：G4(13)=3. Q(n)≥「7n/30」.G4(n)≥4n-1/17(n=17·2k-1-4，k≥1).對于15-點集P，若|V(P)|