WEKO3
アイテム
ネットワークボロノイ図を用いたグラフ分割木の提案と最短経路探索への適用
http://hdl.handle.net/10112/2268
http://hdl.handle.net/10112/2268790ec5b2-d606-4640-b0f0-d87683c62cd3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KU-1100-20080600-01.pdf (1.1 MB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2010-07-27 | |||||
| タイトル | ||||||
| タイトル | ネットワークボロノイ図を用いたグラフ分割木の提案と最短経路探索への適用 | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| その他のタイトル | ||||||
| その他のタイトル | Proposal of Graph-partitioning Tree using Network Voronoi Diagram and its Application to Shortest Path Problems | |||||
| 著者 |
蒲原, 智也
× 蒲原, 智也× 上島, 紳一 |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 23771 | |||||
| 姓名 | Kambara, Tomoya | |||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 23772 | |||||
| 姓名 | Ueshima, shinichi | |||||
| 概要 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 本稿では, 道路網をエッジ重み付きグラフと捉え, ネットワークボロノイ図を用いたグラフ分割木の生成法とそれを用いた経路探査法を提案する．提案手法では, 道路網を表すグラフに対して,ネットワークボロノイ分割を行うことで, 部分グラフに分割し,全体領域を部分領域に分割する. 次に, 各部分グラフをノードと見て, 隣接する部分グラフ同士を融合することにより, 各領域を拡張しながら, より広い部分領域のグラフを構成する. これにより, 原地図と構造化情報として領域の隣接関係と包含関係を持つ階層型グラフ分割木を生成する．最後に, 提案グラフ分割木に,再帰的な経路探査アルゴリズムを与え, その有効性を確認するため, 国土地理院数値地図の道路網データに実際に適用して, 提案アルゴリズムを用いたグラフ分割木の定量的な評価を行う. The authors propose a new balanced space partitioning tree utilizing Network Voronoi Diagram and layering procedures, by considering road maps as planar graphs with edge costs. In our approach, we partition a given graph and generate subgraphs, which represents subregions of the target space. Next, setting each subgraph as a node, we merge with adjacent subgraphs, and extend the subgraphs to represent a wider subregion. By repeating these two steps successively, we generate a balanced space partitioning tree for original maps and structuring information for region adjacency and inclusion relation independently of road density spread over the space. Next, using the proposed tree, we provide a reflexive shortest path search algorithm. We perform numerical simulation to investigate the geometric characteristics of graph partitioning tree, and verify the efficiency of search method. |
|||||
| 書誌情報 |
日本データベース学会論文誌 = DBSJ Journal 巻 7, 号 1, p. 1-6, 発行日 2008-06 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 18831060 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA12331521 | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 出版者 | ||||||
| 出版者 | 日本データベース学会 | |||||
