動的な点に対するVoronoi図とその応用について

スポンサーリンク

概要

• 論文の詳細を見る

• Recently, the Voronoi diagram for moving objects has been investigated in connection with motion planning in robotics and geometric optimization problems in computational geometry. In this paper, we consider the Voronoi diagram for moving points parametrized by t in the plane, whose coordinates are polynomials or rational functions of t. We show that the dynamic Voronoi diagram has the combinatorial complexity of O(n^2λ_<s+2>(n)) and can be computed in O(n^2λ_<s+1>(n)log n) time and O(n) space, where s is some fixed number and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequence.

• 日本応用数理学会の論文
• 1991-06-15

著者

• 今井 桂子

  津田塾大学数学科

関連論文

• 動的な点に対するVoronoi図とその応用について
• Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
• 超平面/曲面のアレンジメントの組合せ論的性質(数理モデルの解析における組合せ論的様相)

スポンサーリンク