オフセット概念の拡張
スポンサーリンク
概要
- 論文の詳細を見る
P, Qをユークリッド空間R^dのコンパクトな部分集合とし, Qに交わるPのすべての平行移動図形の和集合をPによるQのouter on-offsetと定義する.Pが半径rのR^dのボールの場合, outer on-offsetは距離2rのQのouter offsetと一致することを示した.さらに, PによるQの補集合のouter on-offsetの補集合をinner on-offsetと定義する.両on-offsetの形状計算はPとQの間のMinkowski和の計算に帰する事ができ, P, Qが凸多角形の場合, outerそれらの計算量はともにθ(n_P+n_Q)であり, P, Qが3次元の凸多面体の場合, それぞれθ(n_P^2n_Q), O(n_Pn_Q)であることを示した.
- 一般社団法人情報処理学会の論文
- 2005-09-16
著者
関連論文
- 星状多面体の内点判定のためのO(logn)アルゴリズム
- 区分木ソート(セッション3)
- 動的計画法による配管の最適溶接位置決定法
- 凸多面体間の定方向貫通距離計算と交差判定のための平均手間がθ(log^2n)のアルゴリズム
- 球面分割グラフにおける点位置決定アルゴリズムと凸多面体の支持点計算への応用
- 窓のある単純多角形間の交差判定最適アルゴリズム
- 凸多角形間の交差判定・定方向貫通距離計算・ユークリッド距離計算の統一的アプローチ
- 凸多角形の点包含判定のための入力感応型最適アルゴリズム(セッション3)
- オフセット概念の拡張
- 正則曲線と直線分が混在した平面閉曲線の2重接線について