计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
3期
44-46
,共3页
凸多边形:直径%计算几何
凸多邊形:直徑%計算幾何
철다변형:직경%계산궤하
求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别.对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率.
求凸多邊形直徑是計算幾何中的一箇基本問題,在Preparata-Shamos算法的基礎上,提齣瞭採用動態規劃和二分查找的算法,不需要對凸多邊形進行預處理,使整箇算法的時間複雜度降低到O(n)級彆.對算法實現的理論分析結果進行瞭驗證,實驗結果錶明算法具有較高效率.
구철다변형직경시계산궤하중적일개기본문제,재Preparata-Shamos산법적기출상,제출료채용동태규화화이분사조적산법,불수요대철다변형진행예처리,사정개산법적시간복잡도강저도O(n)급별.대산법실현적이론분석결과진행료험증,실험결과표명산법구유교고효솔.
