K-レベルとパラメトリック最小木の極値列挙について

概要

論文の詳細を見る
平面上の直線アレンジメントのK-レベルは、その組合せ複雑度が未解決であり、組合せ幾何学で注目されている研究対象である。また、パラメトリック問題として見た時、選択問題(K番目に小さい元の計算)のパラメトリック化と考えることができる。K-レベルにおける一つの大きな特徴は、高々K個の極大点しか持たないという点であり、これが数々の性質の基となっている。本研究では、これらの極大点をすべて列挙する高速アルゴリズムを提案する。アルゴリズムの計算時間はO(n log n)+O^^∿((kn)^<2/3>)時間であり、また、大きいほうからr個の極大点だけならばO(n log^2 n)+O^^∿((rn)^<2/3>)時間で列挙を行う.さらに、k-レベル問題はパラメトリックマトロイド問題の特殊な場合と捉えることができるが、パラメトリック最小木問題では、k-レベルのy座標に対応するものは、辺の重みが線形に変化するグラフでの最小木の最大重み辺(ボトルネック辺)になる。この問題にたいしては、ボトルネック辺を最大/最小にするパラメタ値を求める高速アルゴリズムを提案する。アルゴリズムでは、単体領域探索に用いられるMatousekの点集合分割を利用する。
一般社団法人情報処理学会の論文
2001-11-27