拡大縮小を考慮した点集合の正方格子度を求めるアルゴリズム  [in Japanese] An Algorithm for Fitting a Perfect Grid to a Set of Points by Rotation,Translation and Scaling  [in Japanese]

LSIなどの超微細な部品を基板上に実装する産業用ロボットでは,より精密さを要求されるので,部品をある決められたところに機械的に配置する位置決め操作によるだけでなく,視覚センサからの情報を用いて補正することが有効である[4].この位置決め問題に関連し,今井,炭野,内藤[3,5]は,ピングリッドアレイ型LSIのピンをほぼ正方格子状に並んだN個の点集合とみなし,点集合が与えられた間隔から構成される正方格子の格子点に平行・回転移動によりどの程度近づけることができるかを示す尺度すなわち正方格子度をミニマックス近似の観点から定義し,それを0(N log N)の手間で求めるアルゴリズムを示した.本論文では,[3,5]の手法を更に拡張し,正方格子状に並んだN点集合に対して,平行・回転移動・拡大縮小を用いて最も適合する間隔から構成された正方格子を配置し,その正方格子から正方格子度をO(N^4)の手間で求めるアルゴリズムを示す.