計算幾何 （アルゴリズム論２）

Computational geometry （アルゴリズム論２）

9914B72

14ISCIP304

関川　浩

Hiroshi Sekigawa

2024年度後期

2024 Second Semester

月曜2限

Monday 2nd Period

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

計算幾何学とは，幾何学の問題を効率よく解くアルゴリズムを開発したり，その計算量を解析したりする計算機科学の一分野である．

この授業では，計算幾何学への入門として2次元，3次元の線形計画問題を説明した後，代表的な問題をいくつか取り上げ，問題に関わる図形の性質，問題を解くために利用するデータ構造，問題を効率よく解くアルゴリズムについて説明する．担当教員が企業の研究員のときに計算幾何学を利用した例なども取り上げる予定である．

本科目は本学科のカリキュラム・ポリシーに定める「数学を中心とする基礎教育と，応用領域を基盤とする最先端の多様な専門教育」のうちの専門教育に該当する科目の一つであり，ディプロマ・ポリシーに定める「数学を中心とする基礎知識を習得し、数学の応用領域を体系的かつ統合的に理解できる能力」の一部を身につけること，具体的には，計算幾何学で用いる基本的な概念，データ構造，アルゴリズムについて理解することが目的である．

(1) 凸包の性質および2次元の凸包構成法を理解すること．
(2) 超平面アレンジメントの定義，性質，構成法を理解すること．
(3) 三角形分割の定義と性質，Voronoi 図と Delaunay 三角形分割の構成法を理解すること．
(4) 代表的な幾何学的探索問題を解くアルゴリズムを理解すること．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

とくになし．

ディベート・ディスカッション　Debate/Discussion／プレゼンテーション　Presentation

-

授業時間中に適宜，演習の時間を取り解いた問題を解説してもらうので，できるだけ事前に問題を解いておくこと．

到達度評価試験50%，レポート30%，演習20%の割合で評価する．レポートの提出，演習で少なくとも1問解くことを必須とし，一方でも欠けた場合は科目全体の成績を「-」とする．

• 到達度評価試験は授業全体の範囲から基本的な問題を出題する．
• レポートはテーマ(1)が終了する第6回終了後，到達目標(1)に関する基本的な問題を出題する．解説は到達度評価試験前にLETUSに掲載する．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

【参考書】
今井浩，今井桂子，計算幾何学，共立出版，1994.
M. ドバーグ，M. ファン クリベルド，M. オーバマーズ，O. チョン，コンピュータ・ジオメトリ—計算幾何学：アルゴリズムと応用，近代科学社，2010.
【その他資料】
講義資料をLETUSに掲載する．

第1回：計算幾何学とは
計算幾何学とはどのような分野であるかを理解する．

第2回：低次元線形計画問題(1)
高速なアルゴリズムを実現する有効なパラダイムである縮小法について理解する．

第3回：低次元線形計画問題(2)
縮小法を利用して線形計画問題を解くアルゴリズムについて理解する．

第4回：低次元線形計画問題(3)
ランダム抽出を利用して線形計画問題を解くアルゴリズムについて理解する．

第5回：凸包(1)
凸包の定義と性質，および，2次元の凸包を構成する Graham のアルゴリズム，包装法について理解する．

第6回：凸包(2)
2次元の凸包を構成する分割統治法，およびそれに線形計画法を組合せたアルゴリズムについて理解する．

第7回：アレンジメント(1)
超平面のアレンジメントの定義と性質について理解する．

第8回：アレンジメント(2)
超平面と点との間の双対性，および，超平面と点との間の双対変換について理解する．
アレンジメントの応用についても理解する．

第9回：アレンジメント(3)
アレンジメントの構成法について理解する．

第10回：三角形分割(1)
三角形分割の定義と性質について理解する．

第11回：三角形分割(2)
Voronoi図とDelaunay三角形分割の構成アルゴリズムについて理解する．

第12回：三角形分割(3)
Delaunay三角形分割の性質について理解する．

第13回：幾何学的探索(1)
幾何学的データ探索の代表的なデータ構造であるヒープ探索木と区分木について理解する．

第14回：幾何学的探索(2)
点位置決定問題を解くアルゴリムについて理解する．

第15回：到達度の確認と解説
本科目の授業内容に関する到達度の確認と解説を行う．

情報通信関係企業での研究員（数学，情報系）としての勤務実績を活かし，計算幾何に関する講義を行う．

Mathematica

Python

N

N