2024-06-20T17:28:07Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000326762024-03-29T05:26:34Z01164:02592:02721:02722
Monotone Polygon Containment Problems Under TranslationMonotone Polygon Containment Problems Under Translationjpnhttp://id.nii.ac.jp/1001/00032676/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32676&item_no=1&attribute_id=1&file_no=1Copyright (c) 1989 by the Information Processing Society of JapanInstitute of Computer Science National Tsing Hua UniversityInstitute of Computer Science National Tsing Hua UniversityJui-ShangChiuJia-ShungWangWe investigate the problem of determining whether a polygon I can be translated to fit inside another polygon E without constructing the whole boundary of the feasible region. In the case of rectilinearly 2-concave polygons an O(mn log^2 mn) algorithm is presented where m is the number of edges of I and n is the number of edges of E. Since the feasible region may have O(m^2n^2) edges this algorithm is more efficiently to solve the problem. Also an O(mn log m) algorithm is presented to solve the case of monotone polygons.We investigate the problem of determining whether a polygon I can be translated to fit inside another polygon E without constructing the whole boundary of the feasible region. In the case of rectilinearly 2-concave polygons, an O(mn log^2 mn) algorithm is presented where m is the number of edges of I and n is the number of edges of E. Since the feasible region may have O(m^2n^2) edges, this algorithm is more efficiently to solve the problem. Also, an O(mn log m) algorithm is presented to solve the case of monotone polygons.AN1009593X情報処理学会研究報告アルゴリズム（AL）198998(1989-AL-012)1231301989-11-202009-06-30