组合几何中的平面有限点集问题

论文摘要

设P为无三点共线的平面有限点集．P的内点是指P中不落在其凸包CH（P）边界上的点．P的全部内点所成的集合记为I（P），V（P）=P＼I（P）称为P的顶点集．对任意给定的正整数k≥1，设g（k）为最小整数，使得任何至少含有g（k）个内点的无三点共线的平面有限点集P必包含一个子集Q （?）P，CH（Q）的内部intCH（Q）恰含有P的k个内点．确切地说，2001年Avis等证明了下述结果：g（1）=1，g（2）=4，g（3）≥8；对任意k≥4有g（k）≥k+2；2003年Fevens证明了对任意k≥3有g（k）≥3k-1．对给定的非负整数k，g（k）的存在性或有限性的判定至今仍然是一个未解决的难题．令2004年Bisztriczky等证得，对给定的正整数k，如果g△（k）有限，则g（k）也是有限的．本文获得了g（3）=9这一重要结果，并改进了g（k）的下界，证得对任意k≥3有g（k）≥3k．关于内点的另一重要研究课题是确定其中P为无三点共线的平面有限点集．2000年Avis等证明了h（4）=7．Fevens于2003年证得对任意5≤k≤8有h（k）≥2k+1；对任意k≥8有h（k）≥3k-7．本文证得h（5）=11．按Grunbaum-Shaphard给出的定义，平面铺砌T是由可列个闭集组成的集族T={T1，T2，…}，使得T1，T2，…的并覆盖全甲面，且Ti的内部两两不交．这里闭集T1，T2，…称为T的铺砌元．T中任意有限个铺砌元（其中至少有两个互异）的交或为空，或为由孤立点与线段构成的集合．交点称为铺砌的顶点，交线段称为铺砌的边．边对边铺砌是指下述类型的铺砌；每个铺砌元是多边形且任二相邻的铺砌元的交是一条完整的铺砌边．如果铺砌中围绕一顶点的铺砌元按环形循序是n1-边形，n2-边形等等，则称该顶点属[n1．n2．…]型．以正多边形为铺砌元且所有顶点属同一类型的铺砌恰好有11种，这11种铺砌统称为阿基米德铺砌．顶点类型为[n1.n2．……．nr]的阿基米德铺砌称为[n1．n2．……．nr]铺砌．设H为[6．6．6]铺砌的顶点集．[6．6．6]铺砌是由边长为单位长度的正六边形构成的．H中的点称为H-点，顶点落在H中的简单多边形称为H-多边形．Reay与Ding于1987年提出并解决了若干有关H-多边形的计数问题．近年来Kolodziejczyk在相关问题研究中获得了一系列深刻的结果，并就H-多边形P的边界H-点数b（P）与内部H-点数i（P）的关系提出猜想b（P）≤3i（P）)+7．2004年Kolodziejczyk证得如下结果：恰含一个内部H-点的H-三角形△的边界H-点数b（△）∈{3，4，5，6，7，8，10}．本文推广Kolodziejczyk的结果，证得恰含k个内部H-点的H-三角形的边界H-点的个数至多为3k+7，并由此提出了两个很有意义的猜想．称平面上的有限点集P为k-等腰集，若对任一k-子集E（?）P，E中存在三个点，其中一点至其他两点的距离相等．1998年Fishburn对k=3，4的情形进行了研究，构造出了所有的3-等腰集，给出了4-等腰集的部分结果，并就4-等腰集提出了6个待解决难题．2002年Xu与Ding对其中的4个问题作出了肯定的回答，给出了完整的结果．本文进一步研究其中的3个问题，获得了部分新结果，构造了无四点共圆无三点共线的4-等腰7-点集，刻画了若干满足某些特殊条件的凸4-等腰7-点集．

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 1.1 平面有限点集的Erdos-Szekeres问题
• 1.2 格点与准格点问题
• 1.3 平面有限点集的距离问题-等腰集问题
• 第二章 g（k）估值问题
• 2.1 g-缺陷集的性质
• 2.2 g（3）=9及其证明
• 2.3 g（k）≥3k及其证明
• 第三章 h（k）估值问题
• 3.1 h-缺陷集的性质
• 3.2 h（5）=11及其证明
• 第四章 H-多边形的边界H-点个数问题
• 4.1 基本事实与相关引理
• 4.2 H-三角形的边界H-点个数
• 4.3 两个猜想
• 第五章 4-等腰集问题
• 5.1 无四点共圆无三点共线的4-等腰7-点集
• 7-1的凸4-等腰7-点集'>5.2 包含R₇-1的凸4-等腰7-点集
• 5的凸4-等腰7-点集'>5.3 包含R₅的凸4-等腰7-点集
• 参考文献
• 索引
• 攻读博士学位期间取得的科研成果
• 致谢