教員一覧

研究紹介

主に計算幾何（computational geometry）関係のアルゴリズムを開発しています。最近、順序付きの特性を有する幾何学的物体を巡回する問題について研究しています。例えば、下の幾何問題に対するアルゴリズムの研究を取り組んでいます。
1) 平面上に線分の集合が与えられるとき、どの線分も少なくとも１点を含む境界線最短の凸包を多項式時間で見つけることができるか。
2) 多角形領域P内にn点が与えられるとき、すべての点をちょうど１回訪問する、Pの境界線と交差しないようなハミルトン路を求める多項式時間のアルゴリズム が存在するか。グラフにおける同様の問題がNP困難であることが分かっているが、この問題はNP困難でないと予測されている。