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

IPSJ

Bibliographic Information

Other Title
  • An Algorithm for Weighted Minimax Linear Approximation of Points

Search this article

Description

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

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top