平面有限点集的空凸分划问题

摘要

令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)的内部不含P的点，记为CH(Si)≌φ(P)，则称此分划为P的空凸分划，这里允许CH(Si)与CH(Sj)相交. 令Nπк(P)表示P的分划π中凸k-边形的个数，k为正整数；Nπ(P)表示P的分划π中凸多边形的个数，记：f(P)=：min{Nπ(P)：π是P的不交凸分划}，F(n)=：max{f(P)：|P|=n}；g(P)=：min{Nπ(P)：π是P的空凸分划}，G(n)=：max{g(P)：|P|=n}；fκ(P)=：max{Nπк(P)：π是P的不交凸分划}Fκ(n)=：min{fκ(P)：|P|=n}相关文献对这些计数函数作了广泛的研究，并获得了若干重要结果.本文引入下列记法：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)|=i(8≤i≤15)，则g5(P)≥2.同时我们给出了两个著名结果F(7)≤2，G(11)≤3的新的简捷的证明.

目录

文摘

英文文摘

§1引言

§2平面有限点集中空凸四边形的计数问题

§315-点集存在两个空凸五边形的充分条件

§4 F(7)≤2与G(11)≤3的新证明

参考文献

插图目录

索引

致谢