点集合の重み付きミニマックス線形近似問題に対するアルゴリズム

情報処理学会

書誌事項

タイトル別名
  • An Algorithm for Weighted Minimax Linear Approximation of Points

この論文をさがす

説明

d次元空間でのn点の重み付きミニマックス線形近似問題が アルゴリズム的には d+1次元での2n点の凸包を求めるという計算幾何学での最も基本的な問題に帰着できることを示す.これより d=2の平面の場合には 問題がO(n log n)の最適の手間で解けることがわかる.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ