対応の与えられた点集合間のミニマックス近似問題について

情報処理学会

書誌事項

タイトル別名
  • On the Minimax Approximation of Two Corresponding Sets of Points
公開日
1988-09-12

この論文をさがす

説明

2つの似かよった点集合の間の最適な当てはめを求める問題は、パタン認識・画像処理などでよく現われる。本稿では、n点同士の1対1対応の与えられた平面上の点集合S,Tが与えられたとき、Sを平行移動と回転することにより対応する点同士の距離の最大値が最小になるようにする問題を考え、それに対するアルゴリズムを与える。このミニマックス型の問題は、例えばピングリッドアレイ型LSIを円形の穴が正方格子状に並んだプリント基板上に自動実装する装置を実現する際に現われる。そこでは、LSIのピンを点とみなした点集合と、円形の穴の中心点の集合との間の対応する点間の距離のミニマックス値が円の半径以下であるとき、かつそのときに限りLSIを基板に実装することが可能である。関連した問題として、プリント基板上のパタンが円ではなく正方形が格子状に配列された問題があり、その問題に対しては既にO(n log n)の手間のアルゴリズムが与えられている。本稿では、まずこの問題を、n個の3変数関数の最大値をとる関数の最小化問題として定式化する。n個の1或は2変数関数の最大値(或は最小値)を値としてとる関数を求めることは、近年の計算幾何学における中心的な話題であり、1変数の場合は特にDavenport-Schinzel列という名の下で研究されている。3変数関数に関する問題は、まだ殆ど調べられておらず、その点でも以降の議論はおもしろい。この定式化に基づき、ここでの3変数関数の最大値関数の性質を調べ、その性質を利用してこの問題に対するO(n^2λ_<10>(n)1ogn)の手間のアルゴリズムを与える。ここで、λ_<10>(n)は10次のDavenport-Schinzel列の最大長であり、それ自身はa(n)をAckermann関数の逆関数としたときO(n2^O(a(n)^4))であることが示されている。λ_<10>(n)はnに関してほとんど線形に近い関数である。また、以下では定数サイズの三角関数を一部含む多項式の根が定数時間で厳密に求められると仮定する。

収録刊行物

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

問題の指摘

ページトップへ