Title :
An efficient method for computing the feasible region with translational containment between two convex polygons
Author :
Chen, Yu-Kumg ; Chou, Shuo-Yan ; Wu, Tzong-Chen
Author_Institution :
Dept. of Electron. Eng., Huafan Univ., Taiwan
Abstract :
A convex polygon containment problem is studied: whether a given convex polygon P can be translated to fit inside another fixed convex polygon Q. An O(pq log q) time algorithm is presented for solving such a problem, where p and q are the numbers of vertices of P and Q. In addition, by utilizing the existence algorithm, it takes O(pq log q) time to find the set of all placements of P that fit inside Q
Keywords :
computational complexity; computational geometry; convex polygon containment problem; existence algorithm; feasible region; fixed convex polygon; translational containment; Electronics industry; Engineering management; Industrial electronics; Information management; Metals industry; Motion planning; Path planning; Raw materials; Shape measurement; Technology management;
Conference_Titel :
Distributed Computing Systems Workshop, 2001 International Conference on
Conference_Location :
Mesa, AZ
Print_ISBN :
0-7695-1080-9
DOI :
10.1109/CDCS.2001.918735
