长廊最短路径的最优算法
An Optimal Algorithm for Gallery Shortest Path Problem
-
摘要: 定义了长廊为平面上由一序列凸四边形构成的有界连通区域,提出长廊最短路径问题,并给出求长廊最短路径的一个算法,最后证明该算法的正确性和在最坏情况下的最优性.Abstract: 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.
下载: