Microsoft PowerPoint - ppt-3.pptxテーマ３：凸包 凸包の定義，構成アルゴリズム 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． １点ずつ加えて行く． 現在の凸包の内部の点なら 何もしない． 現在の凸包の外部の点なら その点から凸包に接線をひき， 凸包を修正する． 問題１：凸包の内部/外部の判定方法 問題２：凸包への接線の求め方 凸包の定義 凸包(convex hull)とは， 与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと． 全ての点を含む最小の軸平行 長方形から始め，ここから削っていく． ちょうど良い 削りすぎ 削りすぎた分をどのように 復元するか？ 凸包構成アルゴリズム(1) 凸包の基本的な性質１： 平面上の点集合Sの凸包の頂点
