Monotone Polygon Containment Problems Under Translation

• Item type: SIG Technical Reports(1)
• 公開日: 1989-11-20
• タイトル: Monotone Polygon Containment Problems Under Translation
• タイトル / 言語: en
• タイトル: Monotone Polygon Containment Problems Under Translation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Institute of Computer Science National Tsing Hua University
• 著者所属: Institute of Computer Science National Tsing Hua University
• 著者所属(英): en
• 著者所属(英): Institute of Computer Science National Tsing Hua University
• 著者所属(英): en
• 著者所属(英): Institute of Computer Science National Tsing Hua University
• 著者名: Jui-ShangChiu; Jia-ShungWang
• 著者名(英): Jui-Shang, Chiu; Jia-Shung, Wang
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1989, 号 98(1989-AL-012), p. 123-130, 発行日 1989-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会