11 2019/12 01
01 02 03 04 050607
08091011121314
15161718192021
22232425262728
29303101020304
Click セミナー

過去のセミナー

開催日2019年12月5日(木曜日)
開催時間16時30分-17時30分
発表者中畑 裕 
発表者の紹介京都大学
タイトル連結かつ非交差な幾何グラフのランダム生成と最適化 
発表の概要
与えられた平面上のn点に対し,連結かつ非交差な幾何グラフの集合を表すデータ構造を構築するアルゴリズムを提案する.
構築されたデータ構造を用いると,効率良く数え上げ,列挙,ランダム生成,「分解可能な」関数の最適化が可能である.
我々の手法は,Wettsteinによる様々な幾何グラフに対してデータ構造を構築する手法に基づく.
我々はWettsteinの手法における連結性を扱うテクニックを改善し,
非交差な全域木と非交差な全域閉路に対し,既存手法より高速なアルゴリズムを提案する.
また,提案手法を少し修正することで,全域閉路に囲まれる面積が最大・最小となるような全域閉路を求めることも可能であることを示す.
本手法並びに,それが基とするWettsteinの手法は,DDやフロンティア法と非常に関連の深いものであると考える.
発表ではその関連についても議論したい.
開催場所VBL301B
接続サイト神田ラボ、京大ラボ