确定平面点集凸包的一类最优算法

作     者：崔国华 洪帆 余祥宣 

作者机构：华中理工大学计算机科学与工程系 

基　　金：国家自然科学基金 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：1997年第20卷第4期

页      码：330-334页

摘      要：确定平面点集的凸包问题在计算机图形学、图象处理、ＶＬＳＩ设计与ＣＡＤ／ＣＡＭ等众多领域中有广泛的应用，多年来人们一直在寻找此问题的快速算法．本文研究了平面点集的凸包问题与排序问题的内在联系，证明了在最坏情况下这两个问题的最优算法具有相同的时间复杂度，进而将平面点集的凸包问题转化成排序问题，并利用双动线检测方法构造了以排序算法为基础的确定平面点集凸包的一类最优算法．

主 题 词：凸包 排序 点集 最优算法 计算机图形学 

学科分类：08[工学] 080203[080203] 0802[工学-机械学] 

核心收录：

馆 藏 号：203609374...