首页 | 本学科首页   官方微博 | 高级检索  
     


Shortest path between two simple polygons
Affiliation:1. National Institute of Advanced Industrial Science and Technology, Tokyo 135-0064, Japan;2. Hitachi, Ltd., Yokohama 244-0817, Japan
Abstract:Consider a collection of mutually disjoint simple polygons in the plane containing a total of n edges. Two of them are specified as a source polygon S and a target polygon T. We present an efficient algorithm for finding a shortest path between S and T avoiding the other polygons. We show that it runs in O(n2) time, using a linear-time algorithm for computing the visibility polygon of a point. This problem is related to a wire routing design of a certain type of LSI for which terminals are of polygonal shape and larger than a wire segment.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号