高次の動的Voronoi図とその応用

• Item type: Journal(1)
• 公開日: 1993-12-15
• タイトル: 高次の動的Voronoi図とその応用
• タイトル / 言語: en
• タイトル: Higher - Order Dynamic Voronoi Diagrams and Its Applications
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 計算幾何学
• 著者所属: 中央大学理工学部情報工学科
• 著者所属: 東京大学理学部情報科学科
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, The University of Tokyo
• 著者名: 今井, 桂子; 今井, 浩
• 著者名(英): Keiko, Imai; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 計算幾何学の分野では、近年、動的な対象物に対する研究が盛んになってきている。本稿では、平面上を動く集合に対する高次のVoronoi図（高次の動的Voronoi図）を求めるアルゴリズムとその解析を行う。点の座標は１つのパラメタに関する多項式や有理式で表されており、その次数が点の数によらない定数である場合を考える。ｓの動き方を決める多項式や有理式によって定まる定数としたとき、ｍ次（ｍ≧2）のVoronoi図の場合，その位柏変化の回数はO(n 2ms+m+3(n) ) であり、O(n 2ms+m+2(n) Iog n) 時間でm次の動的Voronoi図が構成できることを示す。ここで、s（n）は（n、s）Davenport?Schinzel列の最大長を表し、nに関して線形に近い関数である。また、対応の与えられた平面上の2つの点集含を回転や平行移動などの幾何的な変換によって最適な位置に当てはめる問題に、高次の動的Voronoi図が応用できることについても述べる。
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 34, 号 12, p. 2458-2463, 発行日 1993-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764