高次の動的 Voronoi 図とその応用
スポンサーリンク
概要
- 論文の詳細を見る
計算幾何学の分野では,近年,動的な対象物に対する研究が盛んになってきている.本稿では,平面上を動く点の集合に対する高次のVoronoi図(高次の動的Voronoi図)を求めるアルゴリズムとその解析を行う.点の座標は1つのパラメタに関する多項式や有理式で表されており,その次数が点の数によらない定数である場合を考える.sを点の動き方を決める多項式や有理式によって定まる定数としたとき,m次(m≥2)のVoronoi図の場合,その位相変化の回数はO(n^2λ_<s+m+3>(n))であり,O(n^2mλ_<s+m+2>(n)logn)時間でm次の動的Voronoi図が構成できることを示す.ここで,λs(n)は(n,s)Davenport-Schinzel列の最大長を表し,nに関して線形に近い関数である.また,対応の与えられた平面上の2つの点集合を回転や平行移動などの幾何的な変換によって最適な位置に当てはめる問題に,高次の動的Voronoi図が応用できることについても述べる.
- 1993-12-15
論文 | ランダム
- C-8-6 量子ビット用低臨界電流磁束量子回路の研究(C-8.超伝導エレクトロニクス,一般講演)
- CS-6-6 超伝導量子ビット制御に向けた超伝導モジュール技術(CS-6.量子ビットの現在、量子コンピューティングの将来,シンポジウム)
- C-8-11 スケジューラ付き4×4スイッチSFQ回路の設計と動作実証(C-8.超伝導エレクトロニクス,一般講演)
- C-8-10 SFQスイッチの大容量化のためのマルチプレクサの設計と評価(C-8.超伝導エレクトロニクス,一般講演)
- 量子ビット用マルチチップモジュールへのSQUID応用(SQUID,一般)