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 等数据库收录! |
|