与えられた平面分割のVoronoi近似

概要

論文の詳細を見る
本論文では、与えられた、平面の分割をVoronoi図で近似する問題を最適化問題として定式化する。目的関数は凸ではなく、また微分不可能点を持つ。このような問題に対して有効な一般的な解法は現在のところ知られていない。そこで我々はごく原始的な降下法にいくつかの工夫を加えたものを解法として用いる。もちろん得られる解は局所最適解でしかないが、種々の計算機実験により、我々のアルゴリズムによると目的関数の意味で最適解に十分近い解を得ることが可能であることがわかった。この問題は与えられたVoronoi図から母点の座標を復元する問題(Voroni図構成問題の逆問題)を特殊な場合として含んでいる。それは、与えられた平面の分割がそれ自身Voronoi図の場合である。我々のアルゴリズムにより、この場合にも、実用的な規模の問題が実用的な時間で解けることを示した(17 MIPS の性能を持つ大型計算機の上で、32個の母点カ)ら生成されたVoronoi図の母点の座標を約10秒で復元できた。)。さらに、ふたつの例をあげて我々のアルゴリズムが有効であることを示した。一つは、生態学の分野の例で、32の領域を持ち、172点で定められる分割であり、もう一つは都市工学の分野で、11の領域を持ち、192点で定められる分割である。上と同じ計算機で、10秒以内にこれらの分割を近似するVoronoi図をもとめることができた。
社団法人日本オペレーションズ・リサーチ学会の論文

与えられた平面分割のVoronoi近似

スポンサーリンク

概要

著者

関連論文

スポンサーリンク