论文部分内容阅读
令P表示平面上处于一般位置,即无三点共线,的平面点集。对于P的子集H,令Ch(H)表示H的凸包,V(H)表示Ch(H)(或H)的顶点集,I(H)表示Ch(H)内部所包含的P中的点构成的集合,简称为内点集,|H|表示凸包Ch( H )中所包含的集合P中点的个数。如果|V(H)|=k且I(H)为空集,则我们称H为P的一个k-hole,即k-洞。对任意的两个hole:S , T ,如果Ch ( S )与Ch (T )的交为空,我们就称这两个hole为 holedisjiont ,即不交洞。本论文研究计数函数n(k1, k2 ,..., kt ) ,即确定最小正整数n(k1, k2 ,..., kt ) ,使得平面上任何处于一般位置,且至少含有n(k1, k2 ,..., kt )个点的集合P ,总能找到两两不交的k1-hole , k2-hole ,…, kt-hole。本文研究的重点是讨论最小计数函数n(k1, k2 , k3 ) ,并且给出了一些颇有意义的结论:
1) n(4, 4, 5)≤16 ,即对于任意处于一般位置且至少含有 16 个点的平面点集P ,总能找到两两不交的两个4-hole和一个5-hole;
2) n(3, 3, 5)=12 ,即12是最小的正整数,使得任意处于一般位置且至少含有12个点的平面点集P ,总能找到两两不交的一个5-hole和两个3-hole;
3) n(3, 4, 5)=13 ,即13是最小的正整数,使得任意处于一般位置且至少含有13个点的平面点集P ,总能找到两两不交的一个3-hole ,一个4-hole和一个5-hole。为了本结论的证明,我们给出了下述定理:即任何处于一般位置的平面 9 点集Q,当|V(Q)|≥5时,总能找到不交的一个3-hole和一个5-hole。