動的問題とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/19 02:37 UTC 版)

「計算幾何学」の記事における「動的問題」の解説

もうひとつ大きな分類として動的問題があり、それは（入力する幾何学的要素を加えたり除いたりするような）入力の逐次変更に追随して繰り返し解を求める効果的なアルゴリズムの発見を目的とする。この種の問題に対するアルゴリズムは普通、動的データ構造を伴う。計算幾何学的な問題はどれも動的問題に作り変えることができる。例えば範囲探索問題は与える点を増減させることを考えることによって動的範囲探索問題に変形される。動的凸包問題は、たとえば（入力点を増減させるような）点集合の動的な変化に対しての、凸包の変化の様子を追う問題である。 この種の問題の計算量は 探索に用いるデータ構造の構築に必要な時間と空間、 探索されたデータ構造の探索空間における逐次変更に伴う修正に掛かる時間と空間、 要求に解答するための時間（と余分な空間） によって評価される。

※この「動的問題」の解説は、「計算幾何学」の解説の一部です。
「動的問題」を含む「計算幾何学」の記事については、「計算幾何学」の概要を参照ください。