凸包の計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/17 04:35 UTC 版)
詳細は「凸包アルゴリズム（英語版）」を参照 「ギフト包装法」も参照 計算幾何学において、点やその他の幾何学的対象のなす有限集合の凸包を計算するアルゴリズムが数多く知られている。ギフト包装法などがある。 「凸包の計算」というのは、曖昧さ無く効果的に求める凸図形を表すデータを構築することを意味する。凸包アルゴリズムの計算量は通例、入力点の数 n と凸包に属する点（出力点）の数 h とに関して評価される。 二次元及び三次元の点集合に対して、計算量 O(n log h) で凸包を計算できる出力依存アルゴリズムが知られている。三次元より高次の d-次元では、凸包の計算時間は最悪の場合で O ( n ⌊ d / 2 ⌋ ) {\displaystyle O(n^{\lfloor d/2\rfloor })} となる。
※この「凸包の計算」の解説は、「凸包」の解説の一部です。
「凸包の計算」を含む「凸包」の記事については、「凸包」の概要を参照ください。
ウィキペディア小見出し辞書の「凸包の計算」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 凸包の計算のページへのリンク
