（基础数学专业论文）平面有限点集的空凸分划问题.pdf

河北师范大学硕士研究生学位论文 中文摘要 1 1 令p 表示平面上处于一般位置的住一点集设tcp ，若t 的凸包g 日口) 中无尸的点，则称g h ( t ) 所确定的凸多边形为空凸多边形，简称t 为空凸多边 形例2 时，我们也认为t 是空凸多边形设点集p 被分划成t 个不交的子集 ，岛，& ，若对于任意 = l ，2 ，t ，e 日慨) 是一个凸j & 卜_ 边形，称此分划 为尸的凸分划；这时，若对于任意的i j ，有g h ( & ) ng 日( s ) = 彩，则称 此分划为p 的不交凸分划；若对于任意的i ，g h ( 岛) 的内部不含p 的点，记为 e 日( & ) 兰a ( p ) ，则称此分划为p 的空凸分划，这里允许a h 嗡) 与g 日( 马) 相 交 令0 ( p ) 表示p 的分划”中凸一边形的个数，为正整数；”( p ) 表示p 的分划7 r 中凸多边形的个数，记： ，( p ) = ：m i n ”( p ) ：7 r 是尸的不交凸分划 ， f ( n ) = ：m a x ，( p ) ：i 尸l = n ) ； 9 ( p ) = ：m i n ”( p ) ：”是p 的空凸分划) ， g m ) = ：m a x 9 ( 尸) ：| p f = n ) ； ( p ) = ：m “ ( p ) ：”是p 的不交凸分划) 只( 礼) = ：m i n ( p ) ：l p i = n ) 相关文献对这些计数函数作了广泛的研究，并获得了若干重要结果 本文引入下列记法t 乳( p ) = ：m a x i ( 尸) ：”是p 的空凸分划) ， g k ( 凡) = ：m i n 肌( p ) ：l p i = 几 并得到了一些颇有意义的结果 河北师范大学硕士研究生学位论文 g 4 ( 1 3 ) = 3 g 4 ( n ) 【哿j g ( n ) 等尹= 对于1 5 一点集p 。 1 7 2 一4 ，七1 ) 若i y ( p ) i = t ( 8 i 1 5 ) ，则9 b ( p ) 2 同时我们给出了两个著名结果f ( 7 ) 2 ，g ( 1 1 ) s3 的新的简捷的证明 关键词：一般位置；凸分划；空凸分划；不交凸分划；空凸四边形；完好子集 l l i 塑! ! 堑苎盎堂塑主塑壅皇堂堡垒塞1 ” 英文摘要 l e tpb eas e to f np o i n t s1 ng e n e r a ip o s i t i o ni nt h ep l a n e ，a n dl e tf 尸e 日( r ) i s c a l l e da n 朗妒护p d f j 苫o ”i f n op o i n t so f 尸l i e i nt h ei n t e “o ro f c ( 丁) ，w h e r e “c h ”sc a n d s f o r t h ec o n v e xh u l l ，a n dw es i m p l ys a yr i sa ne m p l yp 0 1 y g o n n o t i c et h a tw ea l w a y s r e g a r d 丁a se m p t yp o l y g o n si ff 丁l 2 ap a r i i c i o no fp1 sc a l l e da m 村p d ，m f o i f pi sd a r t i t i o n e db y 七s u b s e 【ss l ，岛，瓯，s u c ht h a te a c hc h ( & ) i sa nf s l 一9 。n i f c h ( s ) ng h ( s j ) = g ，i j ，l h e nc h ep a r t i f i o n i sc a l l e da 胡连，。加，口f f ，彻0 f p ；i f “o p o i n t so f pi i ei ng ( s ) f o re a c hz ，j e ，c 日( & ) 竺g ( p ) ，w ec a l lt h i sp a n i “o n a np ，妒妒 卢口，7 ，j o 盯o f p ，h e r ee h ( s 。) i sa 1 1 0 w e dt oi n t e r s e c tg h ( s j ) l e t 七b eap o s i i i v ei n t e g e ra n d 置( p ) b et h en u m b e rq f c o n v e x 七唱o n sm ap a r l l l l o “ 丌o f 尸l e t ”( p ) b e l h en u m b e r o f c o n v e xp 0 1 y g o n s i na p a r t i t ；o n 丌o f ) w ed e n o t e ： ( p ) = ：l n a x ( j p ) ：7 ri sad j s j i o n tp a r t i t i o no f p ) ， 尻( n ) = ：m i n a ( 尸) ：i p = n ) ，( p ) = m i n ”( ，) ) ：丌i sad i s j i o n ip a r c i l i o no f p ) f ( ，2 ) = ：l m l x ( 尸) ：l 尸l = n ) 9 ( p ) = ：m i n ”( 尸) ：_ 7 ri sa ne m p t yp a r t i l i o no f p ) g ( 礼) = ：m a x ( g ( p ) ：l p i = n ) t h e s ef u n c t i o n sh a v eb e e ns t u d i e dw i d e ly ，a n ds 。m ei m p o r t a n tr e s u l t sh a v eb e e n o b c a i n e d l nt h i sp a p e r ，w ed e 矗n 8 玑( p ) = ：m a x 暑( p ) ：7 ri sa ne m p l yp a n i t i o no f p g k ( n ) s ：m i l l m ( p ) ：i p i = n ) 河北师范大学硕士研究生学位论文 a n dd b t a i f ls o m ei m p o r t a i l tr e s u l t sa b o u tg ( 佗) g 4 ( 1 3 ) = 3 3 v g 4 ( n ) 【等j g 4 ( n ) 尘铲( n = 1 7 2 一1 4 ，女1 ) p b eas e t o f l 5p o i n t s ，i f i y ( p ) i = i ( 8 i 1 5 ) ，舶( p ) 2 a 1 s o ，w eg i v en e wa n dc o n c i s ep r o o 蠹o fc 锑。缸n o u sr e s l l l 拓f ( 7 ) 2a n dg ( 1 1 ) k e yw o r d s ：g e n e r a lp o s i t i o n ；c o n v e ) 【p a r t i t i o n ；d i s j o i n tp a n i t i o n ；锄p t yp a r t i t i o n ； e m p t ) rq u a d r i l a t e m l ；g o o ds u b s e t 河北师范大学硕士研究生学位论文 1 引言 组合几何涉及的许多问题都有着悠久的历史但“组合几何”这个名称在上世 纪五十年代才被数学家h h a d w i g e r 首次使用p a u le r d 6 s 有时也称组合几何为“组 合与离散几何” 1 8 9 3 年，英国数学家j j s y l v e s t e r 在教育时报杂志( e d u c a t i o n a lt i m e s ) 上提出如下猜想： 若存在平面上的有限多个点的点集，使得每一条过其中两点的直线都过该点集 第三个点，则该点集的所有点全在同一条直线上 这个猜想在随后的四十年中一直未获解决，直到1 9 3 3 年，由e r d 6 s 与k a r 啪a t a 重新提出，t g a l l a i 才成功地给出证明正是从这个时期开始，以p a u le r d 6 s 为代 表的数学家不断提出大量组合几何问题，引起了数学界的越来越广泛的关注，组合 几何作为一个数学分支开始逐步形成到五十年代，l 缸z 1 6f c j e st 6 m ，c a m b r o s r o g e r s 等人开始从组合论角度研究曾被牛顿、高斯、闪可夫斯基及希尔伯特研究过 的经典几何问题，奠定了装填理论、覆盖理论与铺砌理论的基础 组合几何问题在编码理论、组合优化理论、机器人学( r 0 b o t i c s ) 、计算几何 与计算机图形学等诸多领域都有十分重要的应用计算机技术的迅猛发展为组合几 何一离散几何的研究提供了强大的动力与良好的契机，大大推动了组合几何学研 究；而组合几何的研究成果又为计算机科学与数学各个分支的研究提供了重要工 具，它们相互补充，相得益彰，使组合几何学的理论与实际应用价值更为突出正 如b o l t y a n s “等人1 9 9 7 年在他们的专著“e x c u r s i o n si n t oc o m b i n a t o r i a ig e o m e t r y ” 中所指出的，泛函分析、经济数学、优化理论在深入研究进程中必须建立确切的几 何形象或几何模型，组合几何一离散几何一凸几何理论已成为现代应用数学的主 要工具之一 本文所研究的平面有限点集的分划问题是组合几何中的一个前沿课题，最初是 河北师范大学硕士研究生学位论文 2 由e r d 6 s ，s z c k e r c s 等人提出的 1 9 3 5 年e r d 6 s 与s z e k c r c s 在“ac o m b i i l a t o r i a lp r o b l e mi i ig e o m e 时”【9 一文 中提出的下述问题在很大程度上推动了组合几何学的发展； 对任意给定的正整数4 ，是否存在一个最小的整数g ( ) ，使得平面上任何处 于一般位置( 即无三点共线) 的g ( k ) 个点的集合p 必含有一个凸一边形的顶点 集? 现在的结论是；这样的9 ( 女) 确实存在，并且，e r d 6 s 与s z e k e r c s 9 】证明了2 “2 + 1 g ( ) ( 雀；) + 1 1 9 7 8 年e r d 6 s ( 6 】， 7 】，【8 】) 把上述问题结论中的凸一边形加 强为空凸一边形，即： 对任意4 ，是否存在一个最小的整数舶( 女) ，使得平面上任何处于一般位置 的9 0 ( 七) 个点的集合p 必含有一个空凸k 一边形( k 一边形内部不含p 的点) 的顶 点集? 这一问题引起了许多数学家的关注i ( 1 e i n ( 见 9 】) 求得了9 0 ( 4 ) = 5 ，1 9 7 8 年 h a r b o r n l 1 2 】求得了卯( 5 ) = 1 0 1 9 8 3 年h o n o n 1 3 】证得当七7 时，卯( ) 不存 在2 0 0 3 年o v e m a r s 1 4 】利用计算机构造出了不含空凸六边形的2 9 一点集但到 目前为止g o ( 6 ) 的存在性问题仍未解决 由蜘( 后) ( 27 ) 的不存在，a v i s 等人( 1 8 】， 1 9 ) 又考虑一类新的问题： 对任意4 ，是否存在一个最小的整数( 七) ，使得平面上任何处于一般位置 的9 7 ( 七) 个点的集合p 含有一个子集0 ，g h ( 0 ) 的内部恰含p 的女个点? 文献( 1 9 中有结论t9 ”) = l ，9 ( 2 ) = 4 ，但是对于矿( 七) ( 七3 ) 是否有 限没有给出结论 在以上问题研究的基础上，1 9 9 4 年以来，u f a b e 等人在平面点集的分划问题 的研究中获得了一系列引人关注的成果 河北师范大学硕士研究生学位论文3 令p 表示平面上处于一般位置的n 一点集若p 的凸包为七一边形。我们也称p 为七一边形 设r c p ，若丁的凸包g 日( t ) 中的内部p 的点，则称c 日( t ) 所确定的凸多 边形为空凸多边形一个区域d 内部不含尸的点时，称该区域关于p 为空，记为 d 垒o ( 尸) ，若不引起混淆也可记为d 掣o 设点集p 被分划成t 个不交的予集& ，岛，岛，若对于任意i = 1 ，2 ，t ， g 日) 是一个凸j & 卜_ 边形，称此分划是尸的凸分划；这时，若对于任意的 i j ，有g 日( ) n e 日( 毋) = g 。则称此分划为p 的不交凸分划；若对于任 意的i ，有g 日( 最) 竺d ( p ) ，则称此分划为p 的空凸分划 图l 是说明不交凸分划与空分划区别的示意图，左图表示的是给定7 点集的 一个不交凸分划，右图表示的是同一7 点集的空凸分划 图l ：说明不交凸分划与空凸分划的区别的示意图 令”( p ) 表示尸的分划中凸多边形的个数， 翟( _ p ) 表示p 的分翊7 r 中凸 一边形的个数，七为正整数记 ，( p ) = ：m i n 。( p ) ：”是p 的不交凸分划) f ( n ) = ：m a x ，( p ) ：l p i = n g ( p ) = ：m i n ”( p ) ：7 r 是p 的空凸分划 河北师范大学硕士研究生学位论文 4 g ( n ) = ：m a x 妇( p ) ：l 尸i = n ) ( p ) = ：m a x ；( 尸) ：”是尸的不交凸分划) 风( n ) = ：r n j n a ( p ) ：ip i = n 文献【l 】， 2 。【3 ， 4 】， 1 5 】，【1 7 ， 1 8 】对这些计数函数都作了广泛的研究， 并获得若干重要结果，如： n 竽1 f ( n ) 嚣 f ( n ) 3 等量，其中n = 1 l 2 。一1 4 ( 七1 ) 孚1 g ( n ) s 簧 g ( n ) 鱼舻，其中n = 1 9 2 一1 4 ( 1 ) r ( n ) 【器j r ( 礼) 警，其中n = 1 3 2 扣1 4 ( 七1 ) 本文引入如下定义： 9 k ( p ) = ：m a x 吾( p ) ：7 r 是p 的空凸分划 g k ( 礼) = ：m i n 玑( p ) ：i p i = n ) 得到一些有意义的结果 同时本文对文献【2 】中的两个重要结果给出了新的更为简捷的证明 河北师范大学硕士研究生学位论文 2 平面有限点集中空凸四边形的计数问题 在相关文献的基础上，本文获得了如下结果 定理2 1g 4 ( 1 3 ) = 3 定理2 2g a ( 礼) l 哿j 定理2 3g ( n ) 4 铲( n = 1 7 2 n 1 4 ，1 ) 以下是证明需要的若干引理 引理2 1 田：局( 9 ) = 2 引理2 2f 盯；f 4 ( 5 ) = 1 由引言中g * ( n ) 与兄( n ) 的定义易知 引理2 _ 3 ：g 4 ( 9 ) = 2 引理2 4 ：g 4 ( 5 ) = 1 在证明这些结论之前给出必要的记法和定义( 参见 4 ) 本节约定p 恒表示1 3 一点集，y ( p ) = ”1 ， 2 巩) 表示p 的凸包g h ( p ) 的顶 点集， l ，现仇依次按逆时针方向排序 丽表示以o ，6 为端点的线段，。b 表示过点o ，6 的直线特别地，对任意t ，可两石 表示g 日( p ) 的边，下标的加法为模t 由法 定义2 l 设p lcp ，如果p l 与p p 1 的凸包的交为空，则称p p l 为完好子集 5 河北师范大学硕士研究生学位论文 6 由于图3 中的1 2 - 点集p 7 ，使得9 4 ( p ，) = 2 ，故有g 4 ( 1 2 ) = 2 ，如果对于任意 1 3 - 点集p ，我们都能找到3 个空凸4 边形，则有玑( p ) 3 ，而显然对于任意1 3 一 点集p ，有m ( p ) 3 ，于是有9 a ( p ) = 3 ，从而得到g 4 ( 1 3 ) = ：m 血 9 4 ( p ) ：i 尸i = 1 3 ) = 3 ，即定理2 1 图3 ：i p ，l = 1 2 ，9 4 ( 尸7 ) = 2 定理2 1 的证明； 证明：由上讨论可知只需证明：对于任意1 3 一点集p ，有鳓( a 3 _ f 0 j ， 1 河北师范大学硕士研究生学位论文 7 1 3 一点集p 的顶点集y ( p ) = u l ， 2 仇 所构成的多边形中，若某址一l q ”l + 1 为空，则地一1 砘仇+ l a ( 地+ l ；矾一l ，让一2 ) 为空凸四边形，剩余9 点为完好子集由 6 r 4 ( 9 ) = 2 ，从而可找到3 个空凸四边形以下设任意地一l 仇地+ l 均不空 = l ，2 t ) ，令a = 以( 仇+ l ；珥，地一1 ) ，这时如果g ( 饥；p l ，让十1 ) 不空，则a 仇地+ l a 慨； 仇+ 1 ，轨+ 2 ) 为空凸四边形，剩余9 点为完好子集以下设g 慨；a ，地+ 1 ) 为空这时腓 与鼽一l 不同事实上，如果弘= a 一1 ，g 池一1 ；轨，仉) 也空。则q 一1 饥a a 慨；吡“地一2 ) 为空凸四边形，剩余9 点为完好子集故可设a 一1 = a 心一1 ；4 ，a ) ，同理e m ；n “ 地一1 ) 为空因此得： 假设2 1 对g ( 尸) 的每条边让毡+ l ，总存在p 中的点凤= a ( + 1 ；毽，钦一1 ) 。使得 g ( 吨；胁，地+ 1 ) u g ( 地+ 1 ；鼽，仉) 为空，且p l ，p 2 ，- 一，p f 互异 图4 ：g 似；a ，饥+ 1 ) u g ( 扯+ l ；鼽，仇) 为空区域 由假设2 1 知四边形q = a 佻+ l 姚一1 a l 为凸四边形，胁与a l 均在让一1 吡仇+ 1 中，如果q t 空，则所剩9 点集为完好子集，因此得到， 假设2 2 每个凸四边形q i = 鼽仇仇一l 鼽一1 均不空 对每个i 。考虑由地+ l a ，忱一1 a i 与丽构成的三角形，记为丑，如果正空。而 由假设2 2 知q 不空，则可找到q 中距丽最近的点q ，从而仇p q p t l 为空凸 四边形，且剩余9 点为完好子集据此得。 河北师范大学硕士研究生学位论文 假设2 3 三角形区域正均不空 图5 ：。 与丑均为非空区域 由假设2 1 ，假设2 2 ，假设2 3 知，l p l 3j y ( p ) l + 避塑见图6 图6 ：i p i 3 l y ( p ) + 世乒 因此，f y ( 尸) i 3 ，故只需讨论i y ( p ) i = 3 的情况 仍由以上假设可知：存在某个丑，不妨设为丑，恰含尸的一个或两个点 显然，如果在上述假设下能在p 中找到一个空凸四边形，剩余9 点为完好子 集；或能找到两个空凸四边形，剩余5 点为完好子集则m ( p ) 3 情形一噩仅含尸的一个点，记为仉 1 我们推断；g 池；p l ，舶) ug ；p l ，船) 仅含吼 由对称性知，只需说明g 沁；p l ，船) 仅含口l 即可见图7 8 河北师范大学硕士研究生学位论文 9 图7 ：e ( 2 ；p l ，p 3 ) 只含g l 尸 ( a ) g 池；p l ，q 1 ) 为空事实上，如果p q 1 ，p = a 池；p l ，q 1 ) ，则可找到空 凸四边形 l p i p a 0 ，；，p 3 ) ，剩余9 点为完好子集 ( b ) g ( u 2 ；q l ，p 3 ) 为空事实上，若口= a 池；g l ，p 3 ) ，进而，若q 在c ( ”1 ；p 1 ，m ) 中，则u - p l 口口l 为空凸四边形，且剩余9 点为完好子集。若q 不在 c ( l ；p l ，m ) 中，即在g ( 1 ；口l ，船) 中，如果此时a ( 口1 ；地，g ) 为空，则 g l p l 2 口为空凸四边形，且剩余9 点为完好子集；若g ( 口l ；地，g ) 不空， 则看e ( m ；p l ，q ) 是否为空 e 3 ；p l ，g ) 不空，则执u l g l a ( p 3 ；p 1 ，g ) 与u 2 p 1 吼a ( g ；w 2 ，仇) 为空凸 四边形，且剩余5 点为完好子集 c ( 船；p l ，g ) 空，则看g ( g ；p 3 ，啦) 是否为空 g ( g ；执，如) 不空，则船q ( 舛船，) 与u 2 p l q l a ( g ；啦，p 2 ) 为空凸 四边形，且剩余5 点为完好子集 g ( q ；p 3 ，地) 为空，若有口在g l ；m ，地) 中，则u lg l 蚋为空凸 四边形，且剩余9 点为完好子集；若口在g 加l ；地，纯) 中，记啦= 以( 舛u 3 ，p 2 ) ，看q 2 的位置见图8 9 2 在g ( u 1 - 口】船) 中，则肌 l 9 9 2 与u 2 p l g l a ( g ； 2 ，砌) 为空凸四边 形，且剩余5 点为完好子集 河北师范大学硕士研究生学位论文 1 0 图8 ：啦在g ( u 1 ；q ，p 1 ) 中 啦在g ( u 1 ；g ，p 1 ) 中，则p 3 q 2 q 与g l l p l a ；g 忱) 为空凸四边 形，且剩余5 点为完好子集 如此即得g ( 啦；p l ，m ) 仅含口l ， 2 令r = a ( 9 1 ；啦，仡) ，看g ( “l ；p l ，9 1 ) 是否为空：若a ( u l ；p l ，9 1 ) 为空，则 q l p l 吨r 为空凸四边形，且剩余9 点为完好子集；若g ( 1 ；p l ，口1 ) 不空，即 它包含r ，如图9 ： 图9 ：g ( 钆；p l ，9 1 ) 为非空区域 这时看g ( r ；9 1 ，翔) 是否为空： 若e ( r ；q l ，阳) 不空，令s = a ( r ；钆m ) ，进一步，若s 在g ( 1 ；q l ，r ) 中，则p l 也r s 与船 l q l a ( s ；u l ，船) 为空凸四边形，且剩余5 点为完好子 河北师范大学硕士研究生学位论文 集；若s 在g ( l ；g l p 3 ) 中，如图l o 所示，则p l 2 r q l 与p 3 l s a ( s ； 1 ，p 3 ) 为 空凸四边形，且剩余5 点为完好子集； 图l o ：s = a ( r ；口l ，p 3 ) 在g ( l ；口l ，r ) 中 若e ( r ；9 1 ，m ) 空，则看e ( u 2 ；p 3 ，r ) 是否为空，若不空，记t = a ( 2 ；p 3 ，r ) ， 进一步，若在a ( ”l ；口l ，r ) 中，则p l u 2 n 与船 1 q l a ( t ；u 1 ，p 3 ) 为空凸四边 形，且剩余5 点为完好子集若t 在c ( l ；口1 ，p 3 ) 中，见图1 1 则p l u 2 r 口l 与p 3 l a ( s ； l ，p 3 ) 为空凸四边形，且剩余5 点为完好子集； 图1 1 ：t = a ( 啦；船，r ) 在a ( 口l ；口l ，p 3 ) 中 由上讨论可知图1 2 中阴影部分除p l ，q l ，船三个点外不含p 的其它点 因此以下讨论g 她；m ，r ) 为空的情形即可 河北师范大学硕士研究生学位论文 1 2 图1 2 ：阴影部分不含p 的其它点 3 由对称性可知，在g ( 1 ；g l ，地) 中也存在r l = a ( 9 1 ；u 3 ，胁) ，使得g ( u 3 ；p 1 ，r 1 ) 与e ( 9 1 ； 3 ，r 1 ) 均空易知 r ，r l ，吨，地 与 p l ，船，g l ，r ，r 1 均处于凸位置 考虑口1 r r l 是否为空 若g l r r l 不空，令u = a ( r ；p 3 ，r 1 ) ，由对和陛，不妨设u 在c ( u 1 ；p l ，9 1 ) 中，则u 3 p 3 9 l n 与“u l p l r 为空凸四边形，且剩余5 点为完好子集； 若q l r r l 空，此时看e 0 - ；u 2 ，r ) 是否为空 若g ( p l ；啦，r ) 不空，则”l q l r l m 与r p l 也a ( r ；也，p 1 ) 为空凸四边形，且 剩余5 点为完好子集； 同理g 慨；t 乜，n ) 不空时，也可找到两个空凸四边形，且剩余5 点为 完好子集 因此只需考虑e 扫l ；吨，r ) 与c 。；口3 ，n ) 均空的情形，如图1 3 所示，其中 阴影部分不含p 的其它点，记钍为r r l 以r 为中心沿顺时针方扫描遇到的第一 个点，不妨设u 在c ( 1 ；p l ，甄) 中，则均船g l r l 与u u l p l r 为空凸四边形，且剩 余5 点为完好子集 情形二t 丑恰含p 两个点，记为p 。口令p = a 池；p l ，船) 。q = a ；p 3 ，p 1 ) ， 如果p 不在瓦中，则 - p ，p a u 1 ，p 3 ) 为空凸四边形，且剩余5 点为完好子 河北师范大学硕士研究生学位论文 图1 3 ：阴影部分不含尸的其它点 1 3 集；如果p 在五中，同样，口也在置中，若p = 口，则”i p l 叩或。1 p 即3 为空 凸四边形，且剩余9 点为完好子集p 为孔中另外一个点) 若p q ，q 必在 g ( p l ；p ，”1 ) 或g 慨；p ，p 1 ) 中，则有空凸四边形 1 p l 弼或 l p q m ，且剩余9 点 为完好子集因此，坤1 p 3 q 处于凸位置 由对称性知若噩或乃中恰含一个点，则仿情形一的推理可得结论，即1 3 一 点集p 可以划分为3 个空凸四边形故疋，死中至少有两个点，而尸共有1 3 个点，故只剩两种情况t ly ( ，( 尸) ) 卜1 0 ，或ly ( j ( p ) ) j - 9 1 jy ( ( 尸) ) f = 1 0 ，见图1 4 ( a ) 这时唯一可能的构形如图1 4 ( a ) 所示，印l ”2 q l ，p 3 口q 5 3 与口2 靠仇g d 为 空凸四边形 2 1y ( j ( 尸) ) i = 9 ，见图1 4 记剩余的一个点为s ，若s 在c ；p ，9 1 ) 中，则g 1 9 2 p 2 9 3 与咙n p s 为 空凸四边形，且剩余5 点为完好子集 若s 在g ( u 2 ；q l ，p 2 ) 中，见图1 5 ( a ) s 在c ( 啦；q 1 ，叮3 ) 中， i s 在g ( 口；q 4 ，p ) 中( 且s 不在g ( 2 ；p ，q 1 ) 中) ，则忱p l 瑚l 与s q 2 仇9 3 河北师范大学硕士研究生学位论文 1 4 图1 4 ：l ( o ) ：矿( j ( p ) ) i = 1 0 ；( ：y ( ，( p ) ) j _ 9 为空凸四边形，且剩余5 点为完好子集 i i _ s 在g ( g ；如，p 3 ) 中，则9 2 p 2 啦9 4 与啦p l 瑚l 为空凸四边形，且剩余 5 点为完好子集 图1 5 ：ly ( j ( p ) ) l = 9 ( b ) s 在e ( 9 2 ；啦，p 2 ) 中，则9 3 口1 p l p ， 2 口2 # 阮为空凸四边形，且剩余5 点 为完好子集 以上我们证明了乳( p ) 3 ，从而有定理2 1 成立 证明定理2 2 需要用到文献 2 】中的引理； 口 河北师范大学硕士研究生学位论文 引理2 5 ，刀? 平面上处于一般位置的2 m + 4 一最集，总能划分为3 个不交的凸子集 一个子集为空凸四边彤，另外两个子集均为 p 点集 1 5 定理2 2 的证明； 证明：据定理2 1 及引理2 5 ，易知3 0 = 1 3 2 + 4 个点中一定有7 个空凸四边形， 而用平面扫描法可知，平面上任意伽点集可划分为品1 个不交的子集，其中，嚅j 个子集含3 0 个点，其余点所成子集包含的点的个数在o 到2 9 之间再由定理2 1 与引理2 1 、引理2 ，2 可知，任意扎一点集至少有【裔j 个空凸四边形 口 定理2 3 的证明： 用归纳法：当= l 时，n = 1 3 ，即要证g 4 ( 1 3 ) 3 由定理2 1 可知结论成 立 令a ( ) = 1 7 2 一4 ，卢( 七) = 4 2 “1 一l - 假设一1 时结论成立，即 有g 4 ( 。一1 ) ) 卢( 自一1 ) 而q ( 女) = 2 a ( 一1 ) + 4 ，每口( 女) 个点可分为3 个 不交凸区域，其中两个含。( 一1 ) 个点，另一个为空凸四边形因此g 4 ( q ( ) ) 2 卢( 七一1 ) + l = 卢( 凫) 口 评注2 1 ；我们推想按类似的方法可以证明g 4 ( 1 7 ) = 4 ，进而猜想g 4 ( 4 n + 1 ) = n 成立 河北师范大学硕士研究生学位论文 31 5 点集存在两个空凸五边形的充分条件 1 6 文献 1 】指出b ( 1 5 ) = 1 图1 6 ( n ) 给出了f p i = 1 4 ，i y ( p ) l = 4 ，夕5 ( p ) = 1 的图示，由此知g 5 ( 1 4 ) = 1 因此可猜想g 5 ( 1 5 ) = 2 ，但如图1 6 ( 6 ) 所示，存在点集 p ，i p i = 1 5 ，i y ( p ) i = 4 ，蜘( p ) = l ，因此有g 5 ( 1 5 ) = 1 图1 6 ：( a ) ：卯( p ) = 1 ；( b ) ：船( p ) = 1 对于1 5 一点集p ，注意到图1 6 ( 6 ) 中l y ( p ) f = 4 ，当i y ( p ) i 4 时，关于卯( p ) 我们获得了如下结果 定理3 1 给定1 5 一点集p ，若f y ( 尸) l = t f 8 isl 印，则舶( p ) 2 记q = p y ( p ) 通常用仇表示y ( p ) 中的点，柳表示y ( 0 ) 中的点 以下是证明定理3 1 必需的若干引理及定义 引理3 1 胆，风( 1 0 ) = l 由凡m ) 与g ( 哟的定义，易得 引理3 。2g 5 ( 1 0 ) = 1 河北师范大学硕士研究生学位论文 1 7 定义3 1 如果有一条直线z 将p 中的一个5 点集u 与其它j d 个点分离，其中 g 日( 矿) 是空凸五边形。则直线z 称为p 的一条五边形分割线，这里直线z 可能过p 中的点 定义3 2 历凸多边形的一条边。6 所在的直线z 将平面分为两个开半平面，其中不 包含此凸多边形的开半平面称为直线 的外侧，有时也简称为边如的外侧记为 n b 记v ( o b ) = f y ( p ) n 。6 j ，即p ( 0 6 ) 表示边n b 外侧所含y ( p ) 的点的个数 由引理3 1 易得如下结论 引理3 3 若p 有五边形分割线，则9 5 ( p ) 2 用( + 1 ) 表示如下性质； 存在g ( q ) 的边0 6a 社，使得( 0 6 ) 3 ( + 1 ) 引理3 4 若 u 成立，则乳( p ) 2 证明：如果( 1 ) 成立，则显然尸存在五边形分割线，由引理3 3 即得结论 口 引理3 5 若y ( p ) i 2 f y ( q ) i ，则卯( p ) 2 证明；假设0 1 ) 不成立。即c 日( q ) 的任意边的外侧至多有y ( 尸) 的两个点，则 l 矿( 尸) | 2 i y ( q ) f ，与已知条件矛盾所以( t 1 ) 成立，由引理3 4 即得结论 口 定理3 1 的证明： 由引理3 4 ，证明中始终假定( 1 ) 不成立 情形1 ，l y ( p ) l = 1 5 河北师范大学硕士研究生学位论文 1 8 这时显然有两个不交的空凸五边形 情形2 1 y ( p ) i = i ( 1 1 i 1 4 ) 这时l y ( q ) i = j0 1 ，2 ，3 ，4 ) ) ，均有l y ( p ) i 2 i 矿( q ) l ，由引理3 5 即得结 论 情形3 i y ( p ) i = 1 0 这时l q i = 5 。由引理3 。5 只须考虑i y ( q ) l = 5 的情形又由于( 幸1 ) 不成立，故 只考虑如图1 7 情况：显然可以找到两个空凸五边形 图1 7 ：f y ( p ) l = 1 0 情形4 i y ( p ) f = 9 这时i q i = 6 ，由引理3 5 只须考虑j y ( q ) l = 6 ，5 的情形 情形4 1i y ( q ) l = 6 由于( $ 1 ) 不成立，我们考虑g 日( q ) 各边外侧所含y ( p ) 的点的个数( 1 或2 ) ， 可得长度为j c 曰旧) 的由1 ，2 组成的序列。为叙述方便，我们称这种序列为“外侧 点数序列” 不同的外侧点数序列对应p 的不同构形情形4 1 中所有可能的外侧点数序 列为t 2 ，2 2 ，1 ，1 ，1 ) ， 1 ，2 ，l ，2 ，1 ，2 ) ， 2 ，1 ，2 ，2 ，1 ，1 ) 。 2 ，2 ，1 ，2 ，l ，1 ) 河北师范大学硕士研究生学位论文 1 9 图1 8 表示 2 ，2 ，2 ，l ，1 ，1 ) 与 1 ，2 ，1 ，2 ，l ，2 ) 所对应的构形，其中两个空凸五边 形按阴影部分所示 类似地， 2 ，1 ，2 ，2 ，1 ，1 ) 与 2 ，2 ，1 ，2 ，l ，l 对应的构形中也有两个空凸五边形 图1 8 ：i y ( p ) i = 9 。i y ( q ) i = 6 情形4 2i y ( o ) i = 5 这时c 日( q ) 各边的外侧点数序列只有一种 2 ，2 ，2 ，2 ，l ，这时设q 的唯一内 点为。，考虑2 所在区域，见图1 9 ： = 在9 2 勋z 4 中。则u l 咖如z 4 z l 与地”4 z 勋为空凸五边形 三在z 2 2 3 2 4 外，则 l 9 2 5 勰l 与抛饥茁3 2 4 0 2 为空凸五边形 情形5 1 y ( p ) i = 8 这时q l = 7 由引理3 5 知须考虑l y ( q ) l = 7 ，6 ，5 ，4 的情形 情形5 1j y ( q ) i = 7 这时g 日( q ) 各边的外侧点数序列只有一种情况； l ，l ，1 ，l ，l ，l ，2 ) ，很容易 能找到两个空凸五边形 情形5 2l y 旧) i = 6 阿北师范大学硕士研究生学位论文 v 图2 0 ：f y ( p ) j = 8 ，i y ( 0 ) i = 6 。在z l z 2 2 6 中，则。札与 7 2 6 2 2 地。3 为空凸五边形 z 在四边形$ 2 七3 7 茁6 中，则地$ 5 。3 2 4 与 l z l z 2 $ 6 地为空凸五边形 2 0 河北师范大学硕士研究生学位论文 2 1 z 在四边形观z 3 蜥z 5 中，则。5 z 锄与。l 。2 。3 嘶为空凸五边形 情形5 - 3i y ( q ) l = 5 这时有两种序列 2 ，2 ，l ，2 ，1 ， 2 ，2 ，2 ，1 ，1 ，只列举第一种情形 设q 的内点为，沈仍考虑= 1 ，缸所在区域，如图2 l ； v 图2 1 ：i y ( p ) i = 8 ，l y ( q ) i = 5 2 l ，施均在。2 勘孔中，不防设z 1 距0 2 如近，则也挑z 3 2 1 2 2 与u l 也z 1 砘。5 为 空凸五边形 。l ，砘在四边形。1 。2 。4 。5 中，不防设施距$ l $ 5 近，则仍是弧如。1 。2 与 l 也z l 施z 5 为空凸五边形 z l ，砘在z 2 。4 的两侧，不防设施在勘勘z 4 中，则仍是地他z 3 。1 。2 与”1 砚。i 砘如 为空凸五边形 情形5 4i 矿( q ) i = 4 此时只有一种情况，e 日( q ) 各边的外侧点数序列为 2 ，2 ，2 ，2 设q 的内点为忽，恐，约仍考虑这三点所在区域，见图2 2 。由于此图除三 河北师范大学硕士研究生学位论文 v 图2 2 ：i y ( p ) i = 8 ，y ( q ) i = 4 点z 1 ，幻，砘之外关于z 2 。4 对称，故我们只考虑z 2 。3 。4 中含一个点，不含点 两种情况： 。2 。4 中含一个点，记为2 l ，则u 7 啦。4 z l z 3 与抛讥z 2 忽z l 为空凸五边形，其 中恐为距o l z 2 近的点 勋铂茁4 中不含点，则在四边形z 1 嚣2 嚣3 2 4 中总存在两个不交的三角形，不妨记 为z 1 。2 砘与z 3 吼z 1 ，则两个空凸五边形为魄z 1 如施与铆魄z 3 姐z 1 口 河北师范大学硕士研究生学位论文 评注3 i 当i y ( p ) = 7 时，我们也得到了结论珊( p ) 2 由于情形较多而方法类似，此 处从略 由图刀所示，正八边形的占个顶点及其内部邻近各边中点位置的8 个点所构成 的1 6 一点集p ，可得g s ( p ) = 2 ，从而有g 5 ( 1 6 ) 2 由于( ( 1 5 ) = 1 ，于是 我们猜想( 毛( 1 6 ) = 2 成立 图2 3 ：靠( p ，) = 2 对任意n ，g 5 ( n ) 的值尚有待研究 河北师范大学啊士研究生学位论文 4f ( 7 ) 2 与g ( 1 1 ) 3 的新证明 m a s a 协u g i lu 瑚l b e 在文献【2 】中已证得两个重要的结论t f ( n ) 挚1 ，g ( 礼) s 晋1 其证明中要用到以下两个定理： 定理4 1 脚f ( 7 ) 2 定理4 2 口，g ( 1 1 ) 3 而本文给出以上两个定理新的证明 4 1f ( 7 ) 2 的证明 设p 为平面上处于一般位置的7 一点集，j ( p ) 表示尸的内点的集合用( t ) 表 示如下陈述； ( $ ) t 存在过g 日( j ( p ) ) 中两点的直线f ，f 将平面分划所得两个半平面中，一 个半平面包含空凸i 边形0 4 ) 引理4 1 若p 满足( 十) 式，则，( p ) 2 证明t 若( + ) 成立，则显然尸可以分划为一个空凸四边形和一个三角形，从而 ，( p ) 2 口 引理4 2 若矿( p ) y ( j ( p ) ) ，则，( 尸) s2 证明：若( + ) 不成立，则过c 日( ，( 尸) ) 中任两点的直线外侧都有一个g 日( 尸) 的点， 则显然有y ( p ) y ( ，( p ) ) ，与已知y ( p ) y ( j ( p ) ) 矛盾故( ) 成立，从而 ，( p ) 2 口 河北师范大学硕士研究生学位论文 定理4 1 的证明t 考虑p 的凸包a 日( p ) 为n 边形，礼= 7 。6 ，5 ，4 ，3 由引理4 1 和引理 4 2 知。若n = 7 ，6 ，5 ，4 则，( p ) 2 成立，故以下我们只需讨论n = 3 的情 形，即g h ( p ) 为三角形，设顶点依次为 - ，啦，如 1 g 日( ，( p ) ) 为四边形，记为p l p 2 船p 4 不妨设p l ，耽分别为距边 l 地。地地最近 的点，如图2 4 所示。再看四边形u l t l 2 m 芦l 是否为凸 图2 4 ： l 抛p 2 p l 为凸区域 ( a ) 若”1 砚仡p 1 为凸四边形见图2 4 。如果强p 妒1 为空则由引理4 1 知 ，( p ) 2 成立如果 2 p 2 p l 不空，令q 为p 2 p l 中距离p l 抛最近的 点，则过p l g 的直线满足( ) ，仍由引理4 1 知，( p ) 2 成立 若 l 2 m p l 不是凸四边形，设u 1 吨p 2 包含p 1 同( a ) 的讨论，看”2 u 3 p l 强是否为凸 若为凸，则，( p ) 2 成立若t j 2 吨p i 胁不为凸，则p l p 2 同时与u l 耽， u 2 相交记仉p l 与地您交于t 点，p 1 与”1 交于f l 点，吨仡与 l 地交 于t 2 点若u 印1 t ，地印2 ，”l p l 以，t 印2 地有一个为空，则由引理 4 1 知，( p ) 2 成立 河北师范大学硕士研究生学位论文 图2 5 ：仅阴影区域非空 故以上四个三角形均为空，因此构形只能是