2008-04-12から1日間の記事一覧
いくつかの発展のためのコメントがあるが、このブログの性格上、もっとも発展が望ましい方向は 「離散幾何学と組合せ幾何学」への発展で、参照文献はこちら組合せ幾何学のアルゴリズム作者: Herbert Edelsbrunner,今井桂子出版社/メーカー: 共立出版発売日: …
美術館問題 多角形内に最小個数の点をとり、多角形内のすべての点が「見える」ようにするための「監視員配置点」を求める問題 美術館定理 単純多角形の三角形への分割 - 警備員巡回路問題 美術館問題では、監視員は不動だったが、1人の監視員が移動してもよ…
幾何的探索 幾何的探索の前に、スカラー的探索とは 多数のデータがあって、該当データを探すとき、データに決まりがなければ、しみつぶしにするしかない データに順序があれば、その順序を利用して探索をかける(ソートしたリストを用いた2分探索) データに…
アレンジメントとは 2次元の場合:直線による平面の分割 3次元の場合:平面による空間の分割 分割は、点、辺、セル(いくつかの辺に囲まれる凸領域)などを要素として構成されるが、それらの間の接続関係 アレンジメントの組合せ特性と構成アルゴリズム 単純…
Wikipediaの記事 ボロノイ図とは 自然現象に頻発し、既存の自然科学・社会科学ですでに利用されている 数学の対象であり、既存の幾何構造の理論などを利用可能 直接の関連の見出しにくい幾何問題にも応用が利くことが多い ボロノイ図の定義と性質 母点 ボロ…
凸包のアルゴリズムの出力 凸包を構成する点集合の決定 凸包構成点の周回順序の決定 包装法 確定した凸包構成点から次を探す Grahamの走査法 ある点からの偏角による位置の評価とソート 逐次構成法 部分データでの解を求め、データを加えながら、解を変更し…
2線分の交差をどう判定するか n本の線分の交差 2線分の組合せが多くなる:取り扱いの工夫が必要 2分探索木を用いた対処 水平・垂直線分の場合 任意方向線分への拡張 応用(2次元表示(グラフィクスが中心)) 隠面除去 線形分離・凸多角形の交差 長方形交差
計算幾何学 幾何学的な問題を扱うアルゴリズムの設計と解析の学問。幾何学的な対象は、従来の情報処理方式と異なったアプローチを要することが多く、独特な特徴を備える 幾何用語 d次元ユークリッド空間 点・直線・平面・線形多様体・多面体 線分 凸領域・凸…
計算幾何学入門―幾何アルゴリズムとその応用作者: 譚学厚,平田富夫出版社/メーカー: 森北出版発売日: 2001/10メディア: 単行本購入: 1人 クリック: 23回この商品を含むブログ (5件) を見る