长廊最短路径的最优算法  

An Optimal Algorithm for Gallery Shortest Path Problem

作　　者：傅清祥[1] 王朝利[1] 孙剑峰[1] 

机构地区：[1]福州大学计算机科学与技术系,福州350002

出　　处：《计算机辅助设计与图形学学报》2002年第12期1138-1141,共4页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家重点基础研究发展规划项目 (G19980 3 0 60 0 )资助

摘　　要：定义了长廊为平面上由一序列凸四边形构成的有界连通区域 ,提出长廊最短路径问题 ,并给出求长廊最短路径的一个算法 ,最后证明该算法的正确性和在最坏情况下的最优性 .The paper defines gallery as a bounded connected region which is formed from a sequence of convex quadrangles on a plane. An algorithm for finding the shortest path is presented, and its correctness as well as optimality in the worst case is analyzed.

关 键 词：长廊 最短路径 最优算法 Graham扫描法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]