二维点集凸壳研究的意义与现状分析

1.3.2　二维点集凸壳研究的意义与现状分析

点集凸壳算法间的“同构化本质与联系”与点集凸壳算法的“同构化改进与创新”，是值得密切关注与认真研究的计算几何学新问题。

一、点集凸壳算法研究的意义

点集凸壳，人们早已关注，广泛应用于计算图形中，可用一组图形点的点集凸壳显示出其点簇；图像处理中，可用寻求图像点的点集凸壳找到数字图像中的关键凸面；机器人学中，可据人工视觉下视物点的点集凸壳指挥机器人行为；指纹识别中，可据指纹边缘轮廓点的点集凸壳获得高质量的指纹；模式识别中，可借模式点的点集凸壳描述模式外形的重要特征；地物辨识中，可借航空航天遥测地面视物点的点集凸壳快速识别地物的平面场景区域；公路规划中，可借所论区域内各城、镇、乡、村位置点的点集凸壳科学规划该区域的最佳环形公路；物体分类中，可让各物体点的点集凸壳相似度勾画出这些物体所属类别；古繁体文字分解中，可凭构造字形点的点集凸壳形成对文字的最优划分等等。

圆集凸壳（即覆盖给定二维圆集的最小凸多边形），人们尚未关心，将会应用于地质勘探中，可用各勘测点所能决定的最大/最小矿藏潜贮圆（形区）域的圆集凸壳，判定其可能的最大/最小矿藏区域；移动通信中，可据各塔台网点所能决定的最大/最小通信圆域的圆集凸壳，判定其可能的最大/最小有效通信区域；军事打击中，可借各攻击武器敌方弹着点所能决定的最大/最小打击圆域的圆集凸壳，判定其可能的最大/最小有效打击区域；环境监测中，可凭各污染源点所能决定的最大/最小污染圆域的圆集凸壳，判定其可能的最大/最小受污染范围；CAD中，可用各设计物件点所能决定的最大/最小占位圆域的圆集凸壳，提高和优化其CAD设计速度与质量等等。

显然，在深化点集凸壳已有的应用中，生成所论点集凸壳的算法首当其冲，而进一步研究点集凸壳的新算法更显得举足轻重；在推进点集凸壳算法创新研究中，研究它们的同构化构造本质势在必行，而进一步应用它们的同构化构造联系尤为重要。因此，开展同构化点集凸壳算法创新研究，对“有力促进计算几何学的丰富与发展，大大提升点集凸壳的应用与水平，捷足抢占同构化圆集算法创新研究制高点”，具有重要学术意义与重大应用价值。

二、国内外点集凸壳算法研究现状

迄今已近40年的国外点集凸壳算法研究，始于20世纪70年代、盛于80年代、巅于90年代，但滞于21世纪，至今已久无新进展。较具影响的串行点集凸壳算法及其研究者，主要有：1970年，D. Chand和S. Kapur提出了第一个最早的凸壳算法“卷包裹”算法，但可惜它是O（nh）的低效近似算法（其中：n为输入二维点集的点数，h为输出凸壳的顶点数）；1972年R. Graham发表了第一个最流行的“格莱汉姆扫描算法”，但其O（n log n）的算法处理较繁复；1973年A. R. Jarvis、1977年W. F. Eddy 、1978年A. Bykat分别给出了正相关于凸壳顶点数的行进算法、快速凸壳算法、快找凸壳算法，但其O（nh）的算法效率欠佳。随后数十年间研究点集凸壳算法，绝大多数（例如，1977年F. Preparata＆amp; S.J. Hong 、1978年A. Bykat、1978年S. G. Akl ＆amp; G. T. Tourrint、1979年A. M. Andrew、1979年P. J. Green ＆amp; B. W. Silverman、1984年M. Kallay、1986年D. Kirkpatrick ＆amp; R. Siedel等人提出的凸壳算法）都是O（n log n），也有一些算法（例如，1978年J. L. Bentley＆amp; M. I. Silmos、1981年L. P. Devroye等人所提出算法）在一定的凸壳顶点分布约束下可期达O（n）。较具影响的并行点集凸壳算法及其研究者，主要有：1988年R. Miller and Q. F. Stout、1995年M. J. Atallah ＆amp; D. Z. Chen等人提出的并行凸壳算法等。此外，不少著作、网站也较详细地介绍了点集凸壳及其算法研究，例如J. O. Rourke的《Computational Geometry in C（2nd Edition）》（1998）。

与上述研究同期，1978年D. Avis、1981年A. C. Yao等人证明了找出凸壳的时间下限为Ω（n log n）。1997年C. Barber等人提出的以“删除以初始点集的最左点、最右点、最高点、最低点为顶点的四边形内各点”与“在随后逐步缩小的各自剩余区域内寻找其制高点”为特色的快速凸壳算法，事实上成为全球点集凸壳算法研究的迄今顶峰。此后，A. Ernst1、B. Sara1等人对分治技术、随机技术等的凸壳算法研究作了有益探索。21世纪前后，点集凸壳算法研究越来越多地集中到的应用化、并行化、高维化方向，但总体上出现了21世纪的裹足不前。

至今已二十来年的国内点集凸壳算法研究，本质上应属跟踪研究；它始于20世纪80年代、巅于90年代，同滞于21世纪。1985年周之英最早提出平面点集凸壳的实时算法，1990年起最专注点集凸壳算法研究是周培德。较具影响的点集凸壳算法及其研究者，主要有：1980年代，最早期的周之英（平面点集凸壳的实时算法），汪嘉业（单多边形求凸壳的线性时间算法）；1990年代，最突出的周培德（求凸壳顶点的一种算法等），杜玉越（一种求简单多边形凸壳的最优算法），周洪玉（图像处理系统中快速凸化算法），以及吴中海、文尚猛、金文华、王志强、李秀忠等人及其研究；2000年来，陈国良（《并行计算：结构·算法·编程》），周培德（《计算几何：算法分析与设计》），以及汪学明、庞明勇、郝小柱、彭认灿、胡鹏、余翔宇、杨勋年等人及其研究。尤其可贵的是，王晓东（凸壳问题的计算时间下限）1994年证明了比国外更精确的凸壳找出时间下限。但进入21世纪来，我国点集凸壳算法研究不可避免地同国外一样也停滞不前。

三、国内外点集凸壳算法研究现状分析

2005年，中国信息化百名学术与管理带头人、四川省有突出贡献优秀专家、西南财经大学博（硕）士生导师周启海教授，在讲授研究生课程《并行算法的设计与实现》（教材《并行计算：结构·算法·编程》，陈国良著，高等教育出版社2003年版）时，率领其创新研究团队，进行了点集凸壳算法研究，并越来越认识到：

（1）国内外学术界起于20世纪90年代中后期的点集凸壳研究注意力的转移，存在若干弱点。

① 仅为求凸壳而将“点集”栅格化成“格集”，使凸壳算法研究误转到复杂度更大的近似算法方向。

② 在点集串行凸壳算法尚停留在1997年顶峰而未取得重大新突破的背景下，就开始向点集并行凸壳算法研究转移，使其并行化研究难以取得根本性新进展。

③ 在缺乏对点集凸壳算法构造特点及其同构本质的科学认识与应用研究的前提下，就开始向n（≥3）维点集凸壳算法研究转移，使其高维化研究难以取得实质性新进展。

（2）国内点集凸壳算法研究历史虽不短，也不乏重要学术成果（例如：平面点集凸壳的实时算法、图像处理系统中快速凸化算法、求平面点集凸壳的一个最优算法等），但无需讳言与国外同行相比仍有较大差距。不仅我国起步期学术成果最早问世时间比国外同行晚整整15年，更因长期以来我国此领域研究队伍过小且大多数研究尚属介绍或应用国外同行学术成果的跟踪研究，使我国的点集凸壳算法研究总体上总是沿袭国外研究思路而一直无法超越其1997年已达巅峰，具有独立知识产权的原创性、源头性、自主性、领先性创新研究成果一直寥若晨星。

（3）点集凸壳的各算法之间，点集凸壳算法与圆集凸壳算法之间，本质上一定必有其相应的同构化本质联系与构造关系。