（应用数学专业论文）平面有限点集中空凸多边形的计数问题.pdf

河北师范大学硕士研究生学位论文 中文摘要 令p 为平面上无三点共线的n 一点集，即尸处于一般位置称区域r 为空区 域，若r 内部不含p 的点，记为r 兰d 设t c p ，若e 日( t ) 兰d ，则称e h ( t ) 所确 定的凸多边形为空凸多边形，记为t 竺0 若”将p 分划为个子集s 1 ，岛，& ， 且名lf & = 礼，使得对任意i l ，2 ，) ，g 日( & ) 均为空凸i & 卜_ 边形，则称7 r 为尸的一个空凸分划 令为正整数， ( 尸) 表示p 的分划n 所确定的空凸 一边形的个数，记 玑( 尸) = ：m o 。 0 ( 尸) ：7 r 为p 的空凸分划 g k ( n ) = ：m i n 9 k ( p ) ：i p i = n ) 本文获得了以下结果： g t ( 札) 【器j ； g 4 ( 礼) 曼篆量；其中n = 2 1 2 一1 4 ( 七1 ) 对于3 ，设n ( ，f ) 为最小整数，使得任意处于一般位置的n ( ，z ) 一点集均 包含两个不同的子集q l 与，c h ( q 1 ) 为空凸一边形，g 日( 0 2 ) 为空凸z 一边 形，且它们的凸包不相交，即g h ( q - ) ng 日( q 。) = o 1 8 中证明了n ( 3 ，4 ) = 7 ， 2 0 中证明了n ( 4 ，5 ) 1 4 本文给出这两个重要结 论的直接证明，比【1 8 和 2 0 中的证明方法更为简洁 关键词：空凸分划；空凸多边形；不交分划；凸位置；一般位置 河北师范大学硕士研究生学位论文 a b s t r a c t l l l l e t pb eas e to f np o i n t s i n t h ep l a n e w i t hn o m r e ec o l l i n e 甄廿l 砒i s ，i ng e n e m l p o s i t i o n ar e g i o nri sc a l l e de m p t yi fi t si n t e o rc o n t a i n sn op o i n to f 尸，d e n o t e db y r 皇仍i ff o rtcp ，e h ( r ) 型0 ，t h ep o l y g o nd e t e h n i n e db yc h ( t ) i sc a l l e de m p t y c o n v e x p 0 1 y g o n w e c a l la p a n i t i o n o f p a i le m p t y c o n v e x p a n i t i o n i f 尸i s p a n i t i o n e d i n t o s u b s e t s 最，s 2 ，s ；：女i & l2 n ，s u c h t h a t g 日( & ) i 8 罂。m p t yc o n v c x i & i g o n f o re a c h t 1 ，2 ，t ) l e t 后b eap o s “i v ei n t e g e r8 n d 罩( 尸) b em en u m b e ro f e f n p t yc o n v e x 南一g o n si na n e m p t yc o n v e xp a r t i t i o n 丌o f 尸，w ed e n o t e 乳( 尸) = ：m o z 毒( 尸) ：7 ri sa ne m p t y c o n v e xp a n i t i o no f p ) g k ( 礼) = ：m t 礼 肌( p ) ：l 尸i = 礼) i l lt h i sp a p e r w eo b t a i nm ef o l l o w j n gr e s u l t s ： g 4 ( n ) l 嚣j ； g 4 ( n ) 5 簧，f o rn = 2 1 2 。一1 4 1 ) f o r 七3 ，l e t 礼( 惫，f ) b em es m a l l e s ti m e g e rs u c ht l l a ta 1 1 ys e to f n ，z ) p o i n t si nt h e p l a n e ，n ot h r e ec o l l i n e a lc o m a i n st w od i 行色r e n ts u b s e t s0 la n dq 2 ，s u c ht h a tg h ( q 1 ) i s a ne m p t yc o n v e x 尼一g o n ，g 日( 0 2 ) i sa ne m p t yc o n v e xf g o n ，a n dg h ( q 1 ) n g h ( q 2 ) = 0 w h e r e g hs t a l l d s f o r m ec o n v “h u l l a l s o ，w eg i v ed i r e c tp m o f so ft w of a m o u sr c s u l t sn ( 3 ，4 ) = 7 18 】a i l dn ( 4 ，5 ) 1 4 【2 0 1 ( e yw o r d s ：e m p t y n v e xp a r t i t i o n ；e m p t yc o n v c xp o i y 9 0 n ；d 吲o i n tp a n i t i o n ；c o n - v e xp o s i t i o n ；g e n e r a ip o s i t i o n 河北师范大学硕士研究生学位论文 1 引言 组合几何这个名称起源于1 9 5 5 年h h a d w 塘e r 的一篇重要论文e r d 6 s 有时也 称其为“组合与离散几何”组合几何研究的内容非常广泛，主要包括装填0 a c k i n g ) 、 覆盖( c o v e r i n 曲及铺砌( t i l i n 曲的相关问题、h e l l y 型问题、平面点集的分划问题、 相对长边和相对短边问题、重复距离问题等诸多问题这些问题的研究结果在实际 中有广泛的应用价值事实表明，许多组合与离散几何问题在编码理论、组合优化 理论、机器人学( r o b o t i c s ) 、结晶学、计算几何与计算机图形学等诸多领域都有十 分重要的应用计算机科学与技术的迅猛发展大大推动了组合几何的研究，使其应 用价值更为突出组合几何已成为现代数学的主要工具之一 分划问题是组合几何中的一个经典问题平面点集的分划问题自其提出之日 起就以独特的魅力吸引了众多数学家从事该问题的研究，取得重大进展( 1 7 】，【1 8 】， 【2 l 】， 2 2 】，【1 9 】) 19 31 年青年女数学家e s t l l e f e i n 提出如下著名的组合几何问题：对任意给 定的正整数n24 ，是否存在最小的整数( n ) ，使得平面上任意处于一般位置( 即 无三点共线) 的( n ) 一点集必含有一个凸n 一边形的顶点集? 若这样的数( n ) 存在，如何确定其值?1 9 3 5 年e r d 6 s 与s z c k e r c s 证明了( n ) 的存在性，猜想 ( n ) = 2 ”2 + l ，并于1 9 7 9 年证明了2 ”2 + 1 ( n ) ( 之2 ) + 1 1 9 7 9 年e r d 6 s 【1 3 提出了如下著名的“空凸多边形”问题设t c p ，若? 的凸 包g h ( t ) 中无尸的点，则称e h ( t ) 所确定的凸多边形为空凸多边形，简称r 为 空凸多边形对任意3 ，求最小的整数n ( ) ，使得任意处于一般位置的n ( 七) 一点 集p 含有一个子集q ，其中q 为空凸一边形k l e i n 1 4 】证明了n ( 4 ) 一5 ，1 9 7 8 年 h a r b o m l 1 5 】证得n ( 5 ) = 1 0 ，1 9 8 3 年h o 哟n 1 6 】证得当七7 时，n ( ) 不存在， + 见a u s g e w i i l l i t ee i n z e i p f o b l e m ed e rk o m b j n 粕n s c h e ng e o m n r i ei nd e fe b e n e 。l e n s e i g n e m e n t m a l h e m a t i q u e ( 1 9 5 5 ) 河北师范大学硕士研究生学位论文 2 n ( 6 ) 是否存在的问题至今仍未解决 目前，此类问题被推广到高维的情形设n 与d 表示正整数，n d 2 求 最小整数9 ( n ，d ) ，使得中任意处于一般位置的g ( n ，d ) 一点集s 均包含一个空凸 多胞形尸，即sni n t g 日( p ) = 0 t i b o rb i s z t r i c z k y 与h e i k oh a r b o n t l 在 2 3 】中证得 9 ( d + ，d ) = d + 2 一1 ，其中1 【 j + 1 以上这类问题统称为e r d 6 s s z e k c r c s 型问题k h o s o n o 与m u r a b e 等人近年 来着重研究e r d 6 s s z e k c r e s 型问题中平面有限点集的凸分划、空凸分划、不交分 划相关的计数问题，下面是本文拟讨论的几个相关问题 问题l ：对于固定的正整数，平面有限点集中存在多少个不交空凸一边形? 设p 表示平面上处于一般位置的n 一点集若”将p 分划为t 个不交的子集 毋，s 2 ，且：，| 最f = 礼，使得对任意t = 1 ，2 ，t ，a h ) 均为空凸i s 卜 边形。且当e j 时，有g 日( s ) n e 日( 毋) = 0 ，则称”为尸的一个不交分划 令为正整数，：( p ) 表示p 的不交分划7 r 所确定的空凸一边形的个数，记 ( p ) = ：m n 。 z ( 尸) ：”为p 的不交分划) r ( n ) = ：m i n ( ( p ) ：i p i = n ) 1 7 】主要研究七= 4 的情形，证得日( 9 ) = 2 ，日( n ) 【嚣j 问题2 ：设p 表示平面上处于一般位置的n 一点集，表示不交分划”所 确定的尸中空凸多边形的个数，记 ，( p ) = ：m 饥 ：”为p 的不交分划) f ( n ) = ：m 嚣 ，( p ) ：i p l = n 【1 8 】中证明了孚1 f ( n ) 挚 若7 r 将p 分划为t 个子集s 1 ，岛，且：。i & i = n ，使得对任意i = 1 ，2 ，t ，c 日( & ) 均为空凸多边形，则称7 r 为尸的空凸分划 河北师范大学硕士研究生学位论文 设”表示空凸分划7 所确定的p 中空凸多边形的个数，记 g ( p ) = ：m 讯 “：丌为p 的空凸分划) g ( n ) = ：m o z g ( p ) ：i p i = n ) 3 1 8 】中证明了孚 g ( n ) 普1 【1 9 】中证明了字 g ( n ) 酱 ；特别 地，对于n = 1 9 2 n 1 4 ( 1 ) ，有g ( n ) 5 问题3 。对于后3 ，求最小整数n ( 女，1 ) ，使得任意处于一般位置的”( 女，1 ) 一点 集均包含两个不同的子集q l 与q 2 ，g 日- ) 为空凸一边形，g h ( 0 2 ) 为空凸z 一 边形，且它们的凸包不相交，即g h ( q 1 ) ng 日( q 2 ) = o 显然有n ( 3 ，3 ) = 6 1 8 】证得竹( 3 ，4 ) = 7 ， 2 0 】证得n ( 4 ，4 ) = 9 ，n ( 3 ，5 ) = 1 0 ， n ( h7 ) = + o 。，1 2 扎( 4 ，5 ) 1 4 以及1 6 n ( 5 ，5 ) 2 0 本文第二节研究问题l ( 1 7 】) 中去掉不交条件所得的一个相关问题一平面有 限点集中空凸多边形的计数问题主要研究了= 4 的情形，得到了一些有意义的 结果 本文第三节给出n ( 3 ，4 ) = 7 ( 1 8 】) ，n ( 4 ，5 ) 1 4 ( 2 0 】) 这两个重要结论的直接证 明，比 1 8 】和【2 0 】中的证明方法更为简洁 河北师范大学硕士研究生学位论文 2 平面有限点集中的空凸四边形问题 令p 表示平面上无三点共线的n 一点集，即p 处于一般位置 4 定义2 ，1 若一个区域r 的内部不包合p 中的点，则称该区域为空，记为r 竺0 否 则，称区域r 非空，记为r o 特别地，设rcp ，若丁的凸包g h ( t ) 中无p 的 占、，则称a 日( t ) 所确定的凸多边形为空凸多边形，记为e h ( 丁) 竺0 ，简记为丁兰o 否则，称g 日( t ) 非空，记为g h ( t ) 喾0 ，简记为t 喾0 定义2 2 若7 r 将p 分划为t 个子集s l ，s 2 ，岛，且：1l & i = 礼，使得对任意 i 1 ，2 ，) ，g h ( & ) 均为空凸j & j 边形，则稚7 r 为p 的空凸分划 令七表示正整数，j ( p ) 表示p 的空凸分划”所确定的空凸k 一边形的个数记 吼( p ) = ：m 。z ：( p ) ：”为p 的空凸分划) g ( n ) = ：7 n 打； 9 ( p ) ：j 尸i = n 定义2 3 刀p 的子集 o ，6 ，c ) 所确定的凸锥g ( “6 ，c ) 是指以。为顶点，6 ，c 在 边界上且么地c 为锐角的角形区域的内部p 中的点d 称为g ( o | 6 ，c ) 的触点，若 d c ( 。油，c ) 且g ( n ，6 ，d ) 中不合p 的点，这时记d = 4 ( n 徊，c ) 本文获得了以下结果 定理2 1g a ( 竹) 【器j 定理2 2g 4 ( n ) 5 茜，其中n = 2 1 2 一1 4 ( k 1 ) 为证明这些结果，需要如下引理 河北师范大学硕士研究生学位论文 引理2 3 刀f 4 ( 5 ) = 1 引理2 4 口刁f 4 ( 9 ) = 2 5 引理2 5 口刁设m 为正整数，对于平面上处于一般位置的任意( 2 m + 4 ) 一点集， 必可将平面划分为三个不交的凸区域，使得其中一个区域包含给定点集中四个最形 成的凸四边形，其他两个区域各含给定点集的m 个点 引理2 6g 4 ( 5 ) = 1 证明：注意到平面有限点集的不交分划必为空凸分划，由丑( 5 ) = l 可得g 4 ( 5 ) = l 口 引理2 7g 4 ( 9 ) = 2 证明：一方面存在这样的8 一点集p ，使得肌( p ) = l ( 见图1 ) ，因此g 4 ( 8 ) = 1 ，g 4 ( 9 ) 2 成立；另一方面，由引理2 4 日( 9 ) = 2 知g 4 ( g ) f 4 ( 9 ) = 2 ，故g 4 ( 9 ) = 2 口 图1 平面上恰含一个空凸四边形的8 - 点集 引理2 8g 4 ( 1 3 ) = 3 河北师范大学硕士研究生学位论文 6 引理2 8 与下面的引理2 9 证明方法类似，本文只证引理2 9 ，该引理本身是本 文的一个重要结果 为表述简洁，若存在直线f 将p 分为两部分，使其中一部分点集的凸包包含一 个空凸e 一边形0 4 ) ，则称z 从p 中分离出一个空凸 一边形( 4 ) 这里所说的 分离不一定是严格分离，即直线f 可能过p 中的点 引理2 9g 4 ( 1 7 ) = 4 证明：令p 表示平面上处于一般位置的1 7 - 点集，y ( p ) 表示g 日( 尸) 的顶点集， 记y ( p ) = u l ， 2 ，仇 ，且 ， z ，仇按逆时针排序用磊表示连接点n ，6 的 线段，n 6 表示连接点、6 的真线 若存在直线z 从p 中分离出个空凸i 一边形0 4 ) ，使其与剩余的至多1 3 一 点集的凸包不相交。简称为与剩余的至多1 3 一点集不相交，或称空凸i 一边形与其 余点分离，则由引理2 8 知p 中存在4 个空凸四边形以下假设 ( ) 不存在具有上述j 陛质的直线c 若对某个i 有地一l 饥仉+ l 型0 令可= a ( 咄+ l ；地“仇一2 ) ，则直线”州从p 中 分离出一个空凸四边形 ；地+ 1 可q “与剩余1 3 - 点集不相交，与( ) 矛盾( 见图2 ) 所 图2 仇一1 饥饥+ l 垒口图示 图3c ( 咄+ l ；q ，p 1 ) 掌0 图示 河北师范大学锕士研究生学位论文7 以对任意的i 都有钵一1 地址+ i 芒9 令a = a ( 饥；仉+ l ，钆+ 2 ) ，则显然g ( 哦i q + 1 ，a ) 型口若g ( 饥+ l ；陇，n ) 碧0 ，令 轨= a 0 ；仇，扯一1 ) ，则矗线鼽轨从尸中分离出一个空凸四边形饥吼+ 1 鼽与剩余1 3 点集不相交，与( t ) 矛盾( 见图3 ) 下面证明对任意的t j ，有鼽n 若否，设肌= p ，则g ( u ；u 。，鼽) 型o ， 令z = a ( a ；q l ，u ，2 ) ，则直线a 。从p 中分离出一个空凸四边形饥a z “与剩余 1 3 一点集不相交，与( * ) 矛盾( 见图4 ) 图4 乳= p l - 1 的情形 综上可知，只须在以下假设下证明结论t ( + ) g ( 。； l ，a ) ug ( u l ；地，a ) 笺0 ， 且对任意的 j ( i ，j = 1 ，2 ，3 ，一，t ) 有n 肼 情形l ：i y ( p ) l 6 设由让一l 砘一l ，她十l 执，甄瓦j 围成的三角形的内部为正 由( ) 及( 十 ) 知必存在某噩竺0 ，记该正所对应的四边形为q = p 以一l ”h u + 1 情形1 1 ：q 型0 这时。 是与其他1 3 一点集交为空的空凸四边形，由引理2 8 知p 中存在4 个 型盟堑堂生塑型塑l 8 空凸四边形，显然虮( p ) 4 ( 见图5 ) 情形1 2 ：q t 喾0 这时u t a 鼽一- u 是与其他1 3 - 点集交为空的空凸四边形，这里 表示q 内部 丽的最近点，由引理2 8 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ( 见图6 ) 图5q 竺0 图示 图6q 喾d 图示 情形2 ：i y ( p ) j = 5 由( ) 及( ) 知必存在某正，如n ，至多含尸中的一个点 若五兰口类似情形i 同理可证 下面考虑丑恰含一点g 的情形 情形2 1 ：e ( 址；p 1 ，口) 喾0 令p 2 a ( u 2 ；p 1 ，g ) ，则u l p 】p a ( p ；功，g ) 是与其他1 3 点分离的空凸四边形，由引 理2 8 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ( 见图7 ) 情形2 2 ：e ( 啦；p l ，口) 掣d 令吼= a ( 地；吼挑) 情形2 2 1 ：g l g ( u 1 ；p l ，g ) 这时 l n q l g 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个 空凸四边形，显然9 4 ( p ) 4 ( 见图8 ) 河北师范大学硕士研究生学位论文 图7g ( 吨；p 1 ，g ) 喾0 图示 图8 引理2 9 情形2 2 1 图示 情形2 2 2 ：口1 g ( ；g ，p 5 ) ( 见图9 ) 图9 引理2 9 情形2 2 2 图示 图l o 引理2 9 情形2 4 1 图示 情形2 2 2 1 ：c ( q ；u 2 ，口1 ) 竺0 9 这时 。口，印l 是与其他1 3 点分离的空凸四边形，由引理2 8 知尸中存在4 个 空凸四边形，显然9 4 ( p ) 4 情形2 2 2 2 ：e ( 口；u 2 ，口1 ) 碧d 情形2 2 2 2 1 ：g 5 ；p l ，q 1 ) 掌0 令啦= a ( p 5 ；p l ，q 1 ) ，则口l g q 2 p 5 与啦p l 口l a ( 9 1 ；忱，p 2 ) 是与其他9 点分离的两个 空凸四边形，由引理2 7 知p 中存在4 个空凸四边形。显然仇( 尸) 4 情形2 2 2 2 2 ：g 0 5 ；p l ，口1 ) 羔d 河北师范大学硕士研究生学位论文 1 0 ( i ) 9 1 e o l ；p 5 ， 5 ) 令啦= a ( q l ；p 5 ，鸭) ( i a ) 的= 这时q 吼p 5 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个 空凸四边形，显然肌( p ) 4 ( i b ) 啦 这时u 2 p l g a ( 9 1 ； 2 ，p 2 ) 与u l q l q 3 p 5 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 ( i i ) q 1 不属于g l ；船，) 令口4 = a ( 口l ；船， 5 ) ( i i a ) 吼”5 这时忱p l q a ( q 1 ； 2 ，p 2 ) 与 1 q 1 铂p 5 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然乳( p ) 4 ( i i b ) 吼= 令q 5 = a ( q l ：，p 4 ) ( i i b a ) 口5 与口l 在讶巧的同侧 g ( ；q l ，9 5 ) 粤0 这时 2 p l ( g l ； 2 ，p 2 ) 与u l q l 舶船是与其他9 点分离的两个空凸四边形， 由引理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 g ( ”5 ；q l ，q 5 ) 喾0 令q 6 = 4 ( ；q l ，口5 ) 若舶c ( 1 ；p l ，g ) ，则u l p l 蜘g 与q l p 5 q 5 是与其他9 点分离的两个空凸 四边形，由引理2 7 知p 中存在4 个空凸四边形，显然吼( p ) 4 ； 若口6 g ( l ；q ，q 1 ) ，且a ( g ； 2 ，口6 ) 兰0 ，则吨p l 口是与其他1 3 点分离的 空凸四边形，由引理2 8 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ，否则， u 2 p l 口6 a ( 9 6 ；吨，p 2 ) 与u l 口g l 船是与其他9 点分离的两个空凸四边形，由引理2 7 河北师范大学硕士研究生学位论文 知p 中存在4 个空凸四边形，显然肌( p ) 4 ； 若驰a ( l ；吼，p 5 ) ，则碗p 1 弘( q l ； 2 ，m ) 与 l g l 9 6 p 5 是与其他9 点分离的 两个空凸四边形。由引理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 ( i i b b ) 啦与 l 在巧瑶异侧的情形类似可证 由对称性知g 她i p i ，风) 与g ( ；热，p 1 ) 均恰含一点g 情形2 3 ：g ( 吨；p 5 ，“5 ) 鲁0 这时p l u 2 p 5 是与其他1 3 点交为空的空凸四边形，由引理2 8 知尸中存在4 个空凸四边形，显然m ( p ) 4 情形2 4 ：由对称性g ( 也；船， 5 ) 掌0 且g ；p l ， 2 ) 掌0 令1 = a 池；p 5 ，如) ， t 2 = a ( ；p 1 ，忱) 情形2 4 1 ：t 1 = t 2 ，令l = t 2 = t ，不失一般性，设t 与船在叽口的同侧( 见图 1 0 、 情形2 4 1 1 ：g ( 5 ；， 2 ) 喾d 令z l = a ( 5 汜 2 ) 情形2 4 1 1 1 ：z l g ( 1 ；p ，q ) 这时 l p l z l q 与船t a ( t ；，p 4 ) 是与其他9 点分离的两个空凸四边形，由引理 2 7 知尸中存在4 个空凸四边形，显然肌( p ) 4 情形2 4 1 1 2 ：f l a ( u l ；q ，t ) ( i ) g ( q ；啦，f 1 ) 兰0 这时吨p l q f l 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空 凸四边形，显然9 4 ( p ) 4 ( i i ) e 妇；也，z 1 ) 喾0 ，且g ( 2 ；t ，z 1 ) 掌0 令2 2 = a ( u 2 ；t ，z 1 ) ( i i a ) 岛e ( 地i p l ，g ) 河北师范大学硕士研究生学位论文 1 2 这时 1 p l z 2 9 与p 5 t u 5 4 ( t ；，m ) 是与其他9 点分离的两个空凸四边形，由引理 2 7 知尸中存在4 个空凸四边形，显然9 4 ( p ) 4 ( i i b ) f 2 g ( l ；g ，z 1 ) g ( g ；，f 2 ) 兰0 这时 2 p l 口f 2 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空凸四边形，显然肌( 尸) 4 g ( g ；吨，2 2 ) 0 这时 2 p l z 2 a ( 2 2 ；u 2 ，p 2 ) 与u l q 扣5 是与其他9 点分离的两个空凸四边形。由 引理2 7 知p 中存在4 个空凸四边形，显然吼( p ) 4 ( i i i ) e ( q ； 2 ，z 1 ) 喾0 ，但g ( 2 ；t ，f 1 ) 兰0 这时吨p l z l a ( f 1 ；吨，p 2 ) 与 l g 印5 是与其他9 点分离的两个空凸四边形，由引理 2 7 知p 中存在4 个空凸四边形，显然m ( p ) 4 情形2 4 1 2 ：g ；t ，也) 型0 ，令f 3 = a ；吨，p 2 ) ，类似情形2 4 1 1 同理可得 情形2 4 2 ：t l t 2 情形2 4 2 1 ：t 1 与t 2 在u l q 的同侧，不失一般性，设t 1 ，2 与p 1 在 1 q 的同侧 ( 见图1 1 ) 情形2 4 2 1 i ：d ( “，2 ) 笺0 这时p 5 q 2 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空 凸四边形，显然乳( p ) 4 情形2 4 2 1 2 ：g ( g ； 5 ，t 2 ) 喾0 这时p 5 2 a ( t 2 ；，m ) 与 1 p l t l 口是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 河北师范大学硕士研究生学位论文 图1 l 引理2 9 情形2 4 2 1 图示囹1 2 引理2 9 情形2 4 2 2 图示 1 3 情形2 4 2 2 ：t 1 与t 2 在 l g 的异侧( 见图1 2 ) 情形2 4 2 2 1 ：a ( p l ；u 2 ，t 1 ) 掌0 这时 l 口t 印5 与t l p l 忱a ( l ； 2 ，p 2 ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 情形2 4 2 2 2 ：由对称性可设g l ；啦，t 1 ) 兰0 且g ( p 5 ；地，t 2 ) 竺0 ( i ) g 0 1 ；p 5 ，2 ) 喾毋令s = a 0 1 ；p 5 ，t 2 ) ( i a ) s 与p l 在”1 9 的异侧 这时啦p 1 船t 1 与”1 口s a ( s ；p 5 ，2 ) 是与其他9 点分离的两个空凸四边形，由引理 2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ， ( i b ) s 与p l 在 l 口的同侧 这时 l p l t l s 与q 珊”5 t 2 是与其他9 点分离的两个空凸四边形，由引理2 7 知尸 中存在4 个空凸四边形，显然9 4 ( 尸) 4 ( i i ) g ( t 1 ；仍，t 2 ) 皇0 ( i i a ) g ( l ；t 2 ，他) d 令s l = a ( t 1 ；t 2 ， 5 ) s l e ( l ；t 1 ，g ) 河北师范大学硕士研究生学位论文 这时u l p l t l s l 与q m 地t 2 是与其他9 点分离的两个空凸四边形 知p 中存在4 个空凸四边形，显然肌( p ) 4 s l c ( u l ；口，t 2 ) 这时”l g s l 2 与 2 t l p 5 p l 是与其他9 点分离的两个空凸四边形 知p 中存在4 个空凸四边形，显然肌( p ) 4 ( i i b ) g ( l ；t 2 ，) 皇0 但g ( 地；t l ， 2 ) 掣0 令s 2 = a ( 嵋；t 1 ，地) 1 4 由引理2 7 由引理2 7 s 2 a ( l ；t 1 ，q ) 这时 1 t l s 2 p 1 与q 船地t 2 是与其他9 点分离的两个空凸四边形，由引理2 7 知尸中存在4 个空凸四边形，显然9 4 ( 尸) 4 s 2 g ( l ；q ，2 ) 这时”l q 5 2 2 与p l p 5 l 忱是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形，显然m ( p ) 4 ( i i c ) a ( l ；t 2 ，) 竺0 且g ( ；t 1 ，u 2 ) 垡0 这时1 吨 5 t 2 是与其他1 3 点交为空的空凸四边形，由引理2 8 知p 中存在4 个 空凸四边形，显然m ( p ) 4 情形3 ：l y ( p ) i = 4 由( + ) 及( 丰+ ) 知必存在某正，如五，至多包含p 中的l 或2 个点 若丑至多包含尸中的一个点，类似情形2 同理可证 以下考虑五恰包含2 个点的情形 令p = a ( 地；p 1 ，p 4 ) ，口= a ( 毗；p 4 ，p 1 ) 河北师范大学硕士研究生学位论文 当p 不属于正时， 1 p l p a 0 ；u 1 ，啦) 是与其他1 3 点分离的空凸四边形，由g 理28 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ，故由对称性知p ，q n 当p = 口时，设墨中剩余的p 中的点为r 1 5 r g ( u l ；p l ，p ) 这时口l p l r p 是与其他1 3 点分离的空凸四边形，由引理28 知尸中存在4 个空凸四边形，显然9 4 ( p ) 4 r g ( 】；p ，肌) 这时 1 矿p 4 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空凸四边形，显然乳( 尸) 4 若平面上的有限点集构成某一凸多边形的顶点集，则称此有限点集处于凸位 置当 p ，q ，p 1 ，m ) 不处于凸位置时，不妨设g 卯1 p 4 口g ( 口1 ；p l ，p ) 这时口1 p l 卯是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 。口a ( u 1 ；弘m ) 这时口1 刚m 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个空凸四边形，显然9 4 ( 尸) 4 下面考虑p g 且 p ，q ，p l ，m ) 处于凸位置的情形 情形3 1 ：g ( p l ；m ，讪) 掣0 ( 见图1 3 ) ，令g i = a ( p 1 ；m 啦) 情形3 1 1 ：q 1 e ( u l ；p 1 ，p ) 河北师范大学硕士研究生学位论文 图1 3 引理2 9 情形3 ，1 图示 图1 4 引理2 9 情形3 2 图示 1 6 这时 l p l g l p 与q m 砒a ( q ；u 4 ，p 3 ) 是与其他9 点分离的两个空凸四边形。由引 理2 7 知p 中存在4 个空凸四边形，显然m ( 尸) 4 情形3 1 2 ：9 1 g ( 1 ；p ，口) 情形3 1 2 1 ：a 溉；p l ，9 1 ) 喾0 令啦= a 慨；p 1 ，9 1 ) 情形3 1 2 1 1 ：口2 g ( l ；p l ，p ) 这时 1 p l q 2 p 与m g 口1 a ( q 1 ；p 4 ，m ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 情形3 1 2 1 2 ：q 2 g ( 1 ；p ，q 1 ) 且g 溉；口2 ，9 1 ) 喾0 令口3 = a ( p 4 ；啦，9 1 ) ( i ) 驰g ( 1 ；p 1 ，p ) ， 这时”1 p 1 口铲与p 4 9 q 2 a ( 啦；m ，口1 ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ( i i ) 啦g ( l ；p ，口2 ) 这时u l p q 3 啦与p l q l m g 是与其他9 点分离的两个空凸四边形，由引理2 7 知 尸中存在4 个空凸四边形。显然9 4 ( p ) 4 河北师范大学硕士研究生学位论文 1 7 ( i i i ) 的g ( u l ；啦，口1 ) 这时u l 口2 口3 口与p l 口1 p 4 p 是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 情形3 1 2 1 3 ：口2 e 扣1 ；p ，口1 ) 且g 0 4 ；9 2 ，9 1 ) 型0 这时u 1 9 2 q l g 与u 2 p l p a ( 麒也，现) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 情形3 1 2 2 ：g 帆；p 1 ，9 1 ) 兰0 但g 慨；m ，地) d 令吼= a ( p 4 ；口1 ，u 2 ) 情形3 1 2 2 1 ：q 4 g ( u l ；p l ，p ) 这时 l p l q 4 p 与m q 吼a ( 口1 ；p 4 ，u 4 ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知尸中存在4 个空凸四边形，显然肌( p ) 4 情形3 1 2 2 2 ：q 4 g ( l ；弘q 1 ) ( i ) g ；u 2 ，啦) 皇0 这时”2 p l p q 4 是与其他1 3 点分离的空凸四边形，由引理2 8 知| p 中存在4 个 空凸四边形，显然肌( p ) 4 ( i i ) g ；啦，啦) 喾0 ( i i a ) e ( 口4 ；p l ， 2 ) 兰o 这时 1 p q l g 与u 2 p 1 吼a ；u 2 ，p 2 ) 是与其他9 点分离的两个空凸四边形。由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 ( i i b ) g ( 吼；p 1 ，地) 喾o 令r = a ( 口4 ；p 1 ，啦) r g ( 1 ；p 1 ，p ) 这时 1 p l r p 与乳g g l a ( 口l ；m ，蛳) 是与其他9 点分离的两个空凸四边形，由 引理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 河北师范大学硕士研究生学位论文 1 8 r g ( 1 ；p ，9 4 ) 这时 1 p 吼r 与p 1 口l m 口是与其他9 点分离的两个空凸四边形，由引理2 7 知尸中存在4 个空凸四边形，显然卯( p ) 24 情形3 1 2 2 3 ：吼g ( 1 ；q l ，q ) 这时u l q l 饥g 与吨p l p a p ；忱，仇) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 情形3 1 2 2 4 ：口4 e ( 口l ；q ，肌) 这时 l g 吼p 4 与p l p 9 1 a ( 口1 ；p 1 ，吨) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 情形3 1 2 3 ：g ( m ；p l ，口1 ) 笺o 且g 慨；q “ 2 ) 垒0 令q 5 = a ；地，轨) 情形3 1 2 3 1 ：q 5 g ( u 1 ；p 1 ，p ) ( i ) e ( p l ；吨，船) 喾o 这时口1 p g l q 与口5 p l 抛a ( 舶； 2 ，p 2 ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然舶( p ) 4 ( ) g ( p 1 ；地，驰) 望0 ( i i a ) g ( 1 ；口5 ，p ) 竺o 这时u z p l p q 5 是与其他1 3 点分离的空凸四边形，由引理2 _ 8 知p 中存在4 个 空凸四边形，显然9 4 ( p ) 4 ( i i b ) g ( l ；口5 ，p ) 喾o 令骺= a ( ；驰，p ) 。q l 与p 4 在 2 q 的同侧 这时册9 1 与u l p l 口5 口6 是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形，显然吼( p ) 4 河北师范大学硕士研究生学位论文 1 9 。9 1 与m 在u 2 口的异侧 这时 l p l 口5 p 与 2 q l q m 是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形，显然m ( p ) 4 情形3 1 2 3 2 ：啦e ( u l ；p ，口1 ) ( i ) g 0 ；u 2 ，9 5 ) 垒0 这时u 2 p l p 是与其他1 3 点分离的空凸四边形，由引理2 8 知p 中存在4 个 空凸四边形，显然9 4 ( p ) 4 ( i i ) g 0 ；u 2 ，如) o 这时吨p l q 5 a ( 口5 ；u 2 ，p 2 ) 与 1 册1 q 是与其他9 点分离的两个空凸四边形。由引 理27 知尸中存在4 个空凸四边形，显然乳( 尸) 4 情形3 1 2 3 3 ：舶a ( 口1 ；q l ，q ) 这时u 2 p l p a ；”2 ，p 2 ) 与u l 口l 口5 q 是与其他9 点分离的两个空凸四边形。由引 理2 7 知p 中存在4 个空凸四边形，显然9 4 ( p ) 4 情形3 1 2 3 4 ：口5 g ( 口1 ；g ，肌) 这时巩q q 5 肌与”2 p l p 口1 是与其他9 点分离的两个空凸四边形，由引理2 7 知尸 中存在4 个空凸四边形，显然啦( p ) 4 情形3 1 3 ：口l g ( ”1 ；口，p 4 ) 这时 1 9 口l p 4 与”2 p l p a o ，；u 2 ，p 2 ) 是与其他9 点分离的两个空凸四边形，由引 理2 7 知p 中存在4 个空凸四边形，显然肌( p ) 4 情形3 2 ：由对称性知g 1 ；肌，饥) 兰0 且g ( 肌；p l ，忱) 垒0 令t = a ( p 1 ；m ，船) ( 见 图1 4 ) 情形3 2 1 ：t e ( 1 ；p l ，p ) 河北师范大学硕士研究生学位论文 2 0 这时 1 p 1 印与砒p 4 弘( 饿 4 ，p a ) 是与其他9 点分离的两个空凸四边形，由引理 2 7 知p 中存在4 个空凸四边形，显然出( p ) 4 情形3 2 2 ：a ( u l ；p ，口) 情形3 2 2 1 ：g ( 咄；p 1 ，t ) 口令u = 以( 地；p 1 ，t ) 情形3 2 2 1 1 ：u ( ? ( u l ；p l ，p ) 这时。p l 叩与啦p 4 驰是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形显然蚰( 尸) 4 情形3 2 2 1 2 ：u g ( 1 ；p ，t ) 这时口l 础g 与p l t 啦弛是与其他9 点分离的两个空凸四边形，由引理2 7 知p 中存在4 个空凸四边形，显然