計算幾何学を用いた一刀切り問題の解法
情報数理工学実験第二A・B／コンピュータサイエンス実験第二A・B (MICS実験第二)
2017年度後学期
第4ラウンド
岡本 吉央
概要
「紙を折り，ある直線に沿って切る．これによってどのような形が切り出せるのか？」これは「一刀切り問題」と呼ばれ，1998年にDemaine, Demaine, Lubiwにより「直線によって構成されたどんな形も切り出せる」ことが証明された．この実験では，彼らのアルゴリズムを実装し，実際に切り出せることを確認する．実装にはRubyを使用する．
キーワード：計算幾何学，計算折り紙，アルゴリズム
レポート
- 締切：2月19日 (月) 13:00 (もちろん厳守)
- 形式：紙媒体のものと電子媒体のものの両方
- 提出先 (紙媒体)：西4号館4階事務室前のレポート提出箱「岡本」
- 提出先 (電子媒体)：岡本宛にメールで (メーリングリスト宛ではないので注意)，bzip2などで適当に圧縮するとよい
- 再提出が必要な場合，2月21日 (水) の16:00までに個人 (メーリングリストへ登録されているアドレス) 宛のメールで連絡する
- 注意：2月9日でCEDは閉室する．
スケジュール
- 12/25 (月) 休講
- 1/10 (水) 一刀切り入門，Ruby入門
- 1/15 (月) 三角形の一刀切り
- 1/17 (水) 直線骨格の構成 (1)：凸多角形
- 1/22 (月) 凸多角形の一刀切り
- 1/24 (水) 直線骨格の構成 (2)：単純多角形
- 1/29 (月) 単純多角形の一刀切り
- 1/31 (水) レポート作成
実験資料
一刀切りの例
実験テキストの訂正表 (見つけたら教えて下さい)
補足情報
[Teaching Top]
[Top]
okamotoy@uec.ac.jp