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

• Item type: National Convention(1)
• 公開日: 1988-09-12
• タイトル: 対応の与えられた点集合間のミニマックス近似問題について
• タイトル / 言語: en
• タイトル: On the Minimax Approximation of Two Corresponding Sets of Points
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 九州工業大学情報科学センター
• 著者所属: 九州大学工学部
• 著者所属(英): en
• 著者所属(英): Kyushu Inst.Tech.
• 著者所属(英): en
• 著者所属(英): KyushuUniv.
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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に関してほとんど線形に近い関数である。また、以下では定数サイズの三角関数を一部含む多項式の根が定数時間で厳密に求められると仮定する。
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00349328
• 書誌情報: 全国大会講演論文集; 巻 第37回, 号 基礎理論および数値処理, p. 11-12, 発行日 1988-09-12
• 出版者 / 言語: ja
• 出版者: 情報処理学会