単純多角形内部の最短経路発見のためのメモリ調節可能アルゴリズム

摘要

平面に与えられたれ頂点の単純多角形に対し，内部の任意の2点間の最短経路を発見するメモリ調節可能アルゴリズムを提案する．この問題は，入力として与えられた単純多角形Pに対して，質問点として多角形内部に2点p，qが与えられた時，Pの内部を通りpからqへの距離最小の経路を報告することである．本稿で提案するメモリ調節可能アルゴリズムは，任意の作業領域のサイズsに対して正常に実行され，sの増加に従い計算時間が短縮されるという性質を持つ．ここで，sは作業領域のサイズを表すパラメータで，Ω（1）≦s≦O（n）とする．ただし，Pに対しO（nlogn）時間の前処理を許すとする．