アクル-トゥーサンヒューリスティック
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/23 18:21 UTC 版)
「凸包アルゴリズム」の記事における「アクル-トゥーサンヒューリスティック」の解説
このシンプルなヒューリスティックは、凸包アルゴリズムの実装の最初のステップとして、パフォーマンスを向上させるためによく使われる。これは、1978年のセリム・アクルと G.T.トゥーサンによる効率的な凸包アルゴリズムをベースとしている。とにかく凸包の一部ではない多くの点をすばやく除外するというアイデアである。この方法ではまず、x 座標が最低と最高の2つの点と、 y 座標が最低と最高の2つの点を見つける（これらの各操作は O（n）となる）。これらの4つの点は凸四角形を形成し、この4点以外のこの四角形内のすべての点は凸包の一部ではない。この四角形にあるこれらすべての点を見つけることも O（n）であり、したがって、操作全体は O（n）となる。必要に応じて、 x 座標と y 座標の合計が最小および最大の点、および x 座標と y 座標の差が最小および最大の点も追加して、不規則な凸八角形を形成して除外を行います。点が確率変数となる場合、つまり現実でよくあるケースで、この除外処理によって、凸包アルゴリズムが線形時間で完了することが期待される。
※この「アクル-トゥーサンヒューリスティック」の解説は、「凸包アルゴリズム」の解説の一部です。
「アクル-トゥーサンヒューリスティック」を含む「凸包アルゴリズム」の記事については、「凸包アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「アクル-トゥーサンヒューリスティック」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- アクル-トゥーサンヒューリスティックのページへのリンク
