計算幾何学を用いた一刀切り問題の解法

岡本 吉央

概要

キーワード：計算幾何学，計算折り紙，アルゴリズム

レポート

• 締切：2月13日 (月) 13:00 (もちろん厳守)
• 形式：紙媒体のものと電子媒体のものの両方
• 提出先 (紙媒体)：西4号館4階事務室前のレポート提出箱「岡本」
• 提出先 (電子媒体)：岡本宛にメールで (メーリングリスト宛ではないので注意)，bzip2などで適当に圧縮するとよい
• 再提出が必要な場合，2月20日 (月) の16:00までに個人 (メーリングリストへ登録されているアドレス) 宛のメールで連絡する

スケジュール

• 1/11 (水) 一刀切り入門，Ruby入門
• 1/16 (月) 三角形の一刀切り
• 1/18 (水) 直線骨格の構成 (1)：凸多角形
• 1/23 (月) 凸多角形の一刀切り
• 1/25 (水) 直線骨格の構成 (2)：単純多角形
• 1/30 (月) 単純多角形の一刀切り
• 2/1 (水) レポート作成

実験資料

• 凸多角形の一刀切りの例
• 単純多角形の一刀切りの例 (折り線の向きが1か所間違っていたので修正 (1/23))

• P1，スケジュール：1/18から2/1まで，「月曜日」と「水曜日」を逆転．
• P5, 真ん中あたり：「大文字あってはいけない」→「大文字であってはいけない」
• P30，$x'_i$ と $y'_i$ を定める式：「$\alpha_1$」→「$\alpha_i$」(8か所)
• P30，$y'_i$ を定める式：2つ目の「$\sin$」→「$\cos$」
• P30, アルゴリズム2の6行目：$i^*$ と $i^*+1$ 以外の $i$ に対して， $v_i$ と $v'_i$ を結ぶ線分も $S$ に格納しなければならない．
• P34，囲み注意の後：「実際この紙を折ってみる」ときに，垂線として得られる線は谷折りであるとする
• P34，囲み注意の4行下：「それは上から見る」→「それを上から見る」
• P34，囲み注意の6行下：「折りたたむことである」→「折りたためばよい」
• P34，脚注：「受け取った紙」→「印刷した紙」
• P35, 1行目：「推薦」→「垂線」
• P39，上の図：多角形の外側の直線骨格が間違っている．正しいのは，そのページの下の図．

補足情報

• Erik Demaineによる「The Fold-and-Cut Problem」のページ