首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:The Shortest Path of Touring Lines given in the Plane
  • 本地全文:下载
  • 作者:Lijuan Wang ; Dandan He ; Ansheng Deng
  • 期刊名称:The Open Cybernetics & Systemics Journal
  • 电子版ISSN:1874-110X
  • 出版年度:2015
  • 卷号:9
  • 期号:1
  • 页码:262-267
  • DOI:10.2174/1874110X01509010262
  • 出版社:Bentham Science Publishers Ltd
  • 摘要:

    Given two points p, q and a sequence of n lines (n>1) in the plane, we want to find the shortest path of touring all the given lines that starts at p and ends at q. In this paper, we solve the problem by reducing it to the problem of finding the shortest path that tours all the segments in a convex polygon from p to q. We first introduce how to construct the convex polygon. Then, we propose the solution to process the intersections of two adjacent segments by crossing over two segments. Finally, based on rubber-band algorithm, a new algorithm is proposed which can find the shortest path of touring segments in a convex polygon, and the O(n2) running time can be obtained for this problem, which improves the previous O(n3logn) time. Our algorithm is simple and efficient.

国家哲学社会科学文献中心版权所有