タイル平面に基づく最小曲がり径路探索アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
迷路法と線分探索法が持つ長所を継承し,短所を克服する新しい配線手法であるグリッドレス・ルータに関する研究が数年前よりなされるようになった.しかし,最小曲がり径路探索手法としては.効率の良くないものや,複雑なデータ購造によるものしか知られていない.そこで本論文では,最小曲がり径路探索問題に焦点をあて,タイル平面と呼ばれる単純なデータ構造に基づいた,高速に径路を求めるグリッドレス・ルータを提案する.このルータは,O(n log n)の手間の前処理後,O(k)の手間で径路を,O(k log k)の手間で最小曲がり径路を求めるとともに,O(k)の手間で図形データの更新を行う.ここで,nは図形の頂点数,k (通常,k≪n)は径路を求める際に探索した図形の頂点数である.このときの空間複雑度はO(n)である.また,提案した手法をインプリメントした結果を報告するとともに,従来の線分探索法との比較を行う.
一般社団法人情報処理学会の論文
1989-02-15

著者

関連論文

もっと見る

スポンサーリンク