(∀(s≦t))について求めて、それらの中で最大のものを選びだせば、それが先の平面内の全ての直交凸領域のゲインの最大値となる。(s,t)(∀(s≦t))を全て計算するという方針をとる。この場合、全てのタイプで同一である。U,D,N},(∀(s≦t)))を求める。以下は、各タイプごとに説明する。(s,t)は、以下の式により求められる。ここで、maxを求める時に、s=tの場合は数30の(1)(2)式だけで比較をし、大きい方の値を用いる。その他の場合は(1)乃至(4)のすべてから最も大きい値を用いる。[s,t]だけからなる領域(幅1の縦長の長方形)のゲインを表す。(2)式は、第m−1列がW−Typeでその区間が[s,t]、且つ第m列も区間[s,t]で右端となっている領域のうち最大のゲインを表す。これは、図8(a)に表したような場合を示す。m-1列がW−Typeであることは決まる。(m-1)]が、s(m−1)≧s,t(m−1)≦t−1を満たし、第m列の区間[s,t]で右端という領域のうち最大のゲインを示す。これは、図8(b)のような形状を意味する。第m−1列の上端は、t−1以下であり、下端はs以上である。(m-1)]がs(m−1)≧s+1,t(m−1)≦tを満たし、第m列の区間[s,t]で右端という領域のうち最大のゲインを表す。これは、図8(c)のような形状を意味する。第m−1列の上端はt以下であり、下端はs+1以上である。W-Typeの左列はW−Typeしかあり得ないということが考慮されている。(s,t)の計算を一列中の全ての区間[s,t]に対して行う。この計算は図9のアルゴリズムに従う。以上のように、第m列が領域の右端で第m−1列からの変化傾向がW−Typeという領域のうち最大のゲインが得られる。最初に以下の式の値を求めておく。これは、図10のようなアルゴリズムにて実行される。(s,t)は、以下の式により求められる。(1)乃至(3)式は、s=tの場合に比較に用いられ、その際(4)式は用いられない。[s,t]のみからなる領域(幅1の縦長の長方形)のゲインを表す。(m-1)]が、s(m−1)≦s,t(m−1)=tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは、図11(a)に示した形状の場合であって、第m−1列の下端の上限はsである。is,s(m−1)≦s,t(m−1)=tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは、図11(b)に示した形状の場合であって、第m−1列の下端の上限はsである。t-1,第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは、図11(c)に示した形状の場合であって、第m−1列の下端の上限はsであり、また上端の範囲はs以上t−1以下である。(2)乃至(4)式は、U−Typeの左隣列はW−Type又はU−Typeしかあり得ないということが考慮されている。(s,t)の計算を一列中の全ての区間[s,t]に対して行う。この計算は、図12に示すアルゴリズムに従う。このように、第m列が領域の右端でそこの変化傾向がU−Typeという領域のうち最大のゲインが得られる。最初に以下の式の値を計算しておく。これらの計算は、図13に示されたアルゴリズムにより実行される。(1)乃至(3)式は、s=tの場合に比較に用いられ、その際(4)式は用いられない。(s,t)は、以下の式により求められる。[s,t]のみからなる領域(幅1の縦長の長方形)のゲインを表す。(m-1)]が、s(m−1)=s,t(m−1)≧tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは、図14(a)に示した形状の場合であって、第m−1列の上端の下限はtである。is,s(m−1)=s,t(m−1)≧tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは図14(b)に示した形状の場合であって、第m−1列の上端の下限はtである。≦s(m−1)≦t,t(m−1)≧tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは図14(c)に示した形状の場合であって、第m−1列の上端の下限はtであって、下端の範囲はs+1以上t以下である。D−Typeの左隣列はW−Type又はD−Typeしかあり得ないということが考慮されている。(s,t)の計算を一列中の全ての区間[s,t]に対して行う。この計算は図15のアルゴリズムに従う。このようにして、第m列が領域の右端でそこの変化傾向がD−Typeという領域のうち最大のゲインが得られる。(s,t)は、以下の式により求められる。ここで、maxを求める時、各式は式の後ろの条件を満たす場合にのみ用いられる。−1を満たす時のみ比較され、(7)式はs>0を満たす場合にのみ比較に用いられる。[s,t]のみからなる領域(幅1の縦長の長方形)のゲインを表す。[s,t]で右端という領域のうち最大のゲインを表す。これは図16(a)に示した形状の場合である。(3)式は、第m−1列の区間[s,t]がU−Typeであって、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。これは図16(b)に示した形状の場合である。t]がD−Typeであって、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。16(c)に示した形状の場合である。m-1列の区間[s,t]がN−Typeであって、その区間[s,t]であり、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。16(d)に示した形状の場合である。m列は区間[s,t]で右端という領域のうち最大のゲインを表す。(e),第m−1列の上端の下限はt+1であり、下端の上限はsである。(m-1)≦s−1,t(m−1)≧tを満たし、第m列は区間[s,t]で右端という領域のうち最大のゲインを表す。m-1列の上端の下限はtであり、下端の上限はs−1である。(s,t)の計算を一列中の全ての区間[s,t]に対して行う。この計算は次のアルゴリズムに図17に従う。N-Typeという領域のうち最大のゲインが得られる。obtained.【0067】上述の(a)乃至(d)の計算にて各列の各[s,t]を右端とする領域の最大のゲインを計算することができる訳であるが、それと同時に"領域"自体も同時に記録しておく必要がある。これは、後の出力ステップでは、この求められた直交凸領域内に含まれるデータを取り出すからである。region.【0068】ここで、同じ最大値の領域が複数存在する場合には、それらのうち先に見つかった方を解として取り扱う。