放物線のアレンジメントの組合せ複雑度について

概要

論文の詳細を見る
曲線族のアレンジメントの複雑度の評価は計算幾何学で重要な問題である。直線のアレンジメントに関しては多くの結果があるが、その他の曲線のアレンジメントに対しての研究は困難性が高く、あまり進んでいない。本論文では、疑似放物線族のアレンジメントの複雑度を考察する。二次関数のグラフ、即ち平面上のy軸方向の放物線の族を考えよう。各々の放物線は平面を二分し、二本の放物線は互いに高々2回しか交わらない。一般に、それぞれが平面を二分し、また、互いに2回ずつしか交わらない平面曲線の族を疑似放物線族という。主結果としては、疑似放物線族を切断して互いに1回しか交わらない曲線分の族にすることを考え、必要な最小切断数の下界O(n^<4/3>)と上界O(n^<5/3>)を与える。また、円のアレンジメントに対しても同じ下界と上界を与える。応用として、疑似放物線のアレンジメントのレベルの複雑度に対するO(n^<23/12>)の新しい上界を与え、又、移動する点のユークリッド最小木の組合せ変更数の既知の上界をO(n^<1/12>)改良する。
一般社団法人情報処理学会の論文
1995-01-23