中文摘要：

离散与组合几何是现代数学的重要分支。本项目旨在研究其中的两类问题平面有限点集Erd?s-Szekeres问题与平面有限点集的Erd?s距离问题。拟探讨Erd?s-Szekeres内点问题；Erd?s-Szekeres分划问题；Erd?s距离中的等腰集问题以及互异距离数问题。拟确定若干相关计数函数的取值、上下界，证实或否定一些重要猜想。这些问题均为近年来受到广泛关注的前沿课题，其研究吸引了国内外许多著名的专家和学者。本项研究在离散与组合几何学的理论中有重要意义，在计算机图形学、计算几何学、结晶学及运筹学中有着广阔的应用前景。欧美各国数学界对这一领域的研究十分重视。本项目研究将促进离散与组合几何这一实用性很强的数学分支在我国的发展，并为计算机科学与计算机图形学的研究与技术开发提供理论依据与实用工具。

结论摘要：

本项目执行期间研究平面有限点集的Erdos-Szekeres内点问题与分划问题、Erdos距离中的互异距离数和等腰集问题、以及平面格点多边形的内格点数问题、组合恒等式及邻强边染色问题等。在国家基金的大力资助下获得了若干重要成果，受到同行专家的关注。本项研究有重要的理论和应用价值，有助于促进这一应用前景广阔的数学分支在国内的发展。本项目共发表论文18篇，其中16篇论文发表在SCI或EI收录刊物。 平面有限点集Erdos-Szekeres内点问题对任意的正整数k，确定最小整数r(k)，使得平面上任何处于一般位置且至少含有r(k)个内点的集合P包含一个子集Q，Q的凸包的内部恰好含有P的k或k+1个内点。本课题组利用一种完美的内10点几何构型证明了r(5)=11。在积累前期研究结果的基础上，课题组对约束参数做了适当的修正，提出了两类新的计数函数t(k)、h(k)，通过完善有关缺陷集的性质证得t(k)( k<7)的确切值，构造了一种较好下界；通过布置有限点集中点的位置，讨论半平面和接触点，进一步证得h(3)=8，这两类函数对Erdos-Szekeres原始内点问题当基数较大时的研究意义很大。针对Erdos-Szekeres空凸分划研究，确定了包含不交空凸双三角形和五边形的最小点集恰好包含12个点。 Erdos距离问题最早研究平面n点所确定的单位距离数是多少？问题逐渐扩大，研究论文层出不穷。本课题研究互异距离数问题称一平面点集为k-距离集，如果任意两点间恰好确定k种互异距离。令g(k)表示确定k个距离的点集的最大点数。著名数学家Erdos于1996年提出的著名猜想g(6)=13。课题组通过研究直径图的性质对此猜想给出了正确的证明，另外给出了等价基础上的十一点五距离集与七点四距离集及几何构型。利用平面几何中边角知识巧妙地否定了圆上的四等腰八点集的存在性。 课题组对阿基米德铺砌问题有部分研究，完整刻画了包含两个内格点的凸格多边形的特性及个数问题，研究中涉及Pick型定理及有关的格点知识。在组合恒等式问题的研究上确定了多项组合计数公式或相互递推关系。利用算法分析中的分支限界技术设计了几种算法来研究联图的邻强边染色，给出了六种联图的邻强边色数。这些研究成果可以应用到计算机科学及通讯信号的研究中，与信息科学有密切的联系。