Takehiro Ito   Yuichiro Miyamoto   Hirotaka Ono   Hisao Tamaki   Ryuhei Uehara   
ALGORITHMS AND COMPUTATION, PROCEEDINGS 5878 403-+ 2009年
Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider the problems of finding an orientation of all edges in G: MIN-SUM ORIENTATION is to minimize the sum of the shortest directed d...
本論文では最短路を高速に検索するためのデータ構造とアルゴリズムの工夫,階層メッシュ疎化法,を提案する.最短路に頻出する枝をあらかじめ抽出することで,応答する経路の最適性を保証しつつ,検索時間の大幅な短縮に成功した.全米道路(約 2400 万点,約 5800 万枝)に適用した実験結果も報告する.階層メッシュ疎化法は,関連する既存手法に比べてメモリ使用量が少ないのが長所である.In this paper, we propose the levelwise mesh sparsification...
Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012 241-246 2012年12月
This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangula- Tion. There exists a theorem which characterizes De- launay graphs and yields a p...