http://swrc.ontoware.org/ontology#TechnicalReport
Monotone Polygon Containment Problems Under Translation
ja
Institute of Computer Science National Tsing Hua University
Institute of Computer Science National Tsing Hua University
Jui-ShangChiu
Jia-ShungWang
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.
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）
1989
98(1989-AL-012)
123-130
1989-11-20