"空間的に離散して配置される複数の要素から形成される離散パターンの該要素の空間配置を計算する情報処理装置であって、前記離散パターンの前記要素が配置される領域内での前記要素の密度分布から、要素各々に対し、該要素各々に与えられた初期位置での密度を求めて、該密度に応じた大きさを有し該要素各々が他を斥ける領域を表す図形と、該図形の移動範囲と設定する設定部と、前記図形各々の位置を決定変数として、前記図形同士の衝突および前記図形の前記移動範囲からの突出に対しペナルティを与える目的関数を最小化して、前記図形各々の位置の最適解を演算する演算部と、前記図形各々の位置の最適解を前記要素の空間配置として出力する出力部とを含む、情報処理装置。前記目的関数は、図形同士が衝突し合う深度に応じてペナルティを与える非線形項と、図形が移動範囲から突出する深度に応じてペナルティを与える非線形項とを含み、制約なしの非線形最適化問題を構成する、請求項1に記載の情報処理装置。前記目的関数は、前記要素が配置される領域を画定する容器から図形が突出する深度に応じてペナルティを与える非線形項をさらに含む、請求項2に記載の情報処理装置。前記図形同士が衝突し合う深度は、図形間で衝突による貫通を除去するために必要な平行移動の距離として定義され、前記突出する深度は、注目する図形と、移動範囲または容器との間で、前記突出による貫通を除去するために必要な平行移動の距離として定義される、請求項3に記載の情報処理装置。前記ペナルティを与える非線形項は、それぞれ、微分可能でかつ微分連続性を有する関数である、請求項2に記載の情報処理装置。一様分布列を用いて前記要素の密度分布を再現する前記要素の初期配置を生成し、前記要素各々の初期位置を記憶部に書き込む初期配置生成部をさらに含む、請求項1に記載の情報処理装置。前記演算部は、前記要素が配置されるべき領域を画定する容器を複数の区域に分割し、各区域に属する図形間の衝突を検知する手段を備え、少なくとも同一区域に属さないため衝突し得ない図形間のペナルティの計算を省略することを特徴とする、請求項1に記載の情報処理装置。前記設定部は、入力として与えられる要素の大きさと、前記要素の密度分布から与えられる前記要素各々の初期位置での要素の充填率とを用いて、前記要素各々に対し設定する前記図形の大きさを計算する、請求項1に記載の情報処理装置。前記要素は、ドットであり、前記離散パターンは、2次元空間的に離散して配置される複数のドットから形成されるドットパターンであり、前記図形は、円であることを特徴とし、さらに、前記円iの半径riは、下記式上記式中、r0は、前記要素であるドットの半径を表し、ρは、ドットの初期位置での充填率を表し、aは、上記不等式を満たす定数である。に従って決定されることを特徴とする、請求項1に記載の情報処理装置。空間的に離散して配置される複数の要素から形成される離散パターンの該要素の空間配置を計算するための、コンピュータシステムが実行する計算方法であって、コンピュータシステムが、前記離散パターンの前記要素が配置される領域内での前記要素の密度分布から、要素各々に対し、該要素各々に与えられた初期位置での密度を求めて、該密度に応じた大きさを有し該要素各々が他を斥ける領域を表す図形と、該図形の移動範囲とを設定するステップと、コンピュータシステムが、前記図形各々の位置を決定変数として、前記図形同士の衝突および前記図形の前記移動範囲からの突出に対しペナルティを与える目的関数を最小化するよう最適化問題を解き、前記図形各々の位置の最適解を演算するステップと、コンピュータシステムが、前記図形各々の位置の最適解を前記要素の空間配置として出力するステップとを含む、計算方法。前記目的関数は、図形同士が衝突し合う深度に応じてペナルティを与える非線形項と、図形が移動範囲から突出する深度に応じてペナルティを与える非線形項とを含む、請求項10に記載の計算方法。前記目的関数は、前記要素が配置される領域を画定する容器から図形が突出する深度に応じてペナルティを与える非線形項をさらに含む、請求項11に記載の計算方法。コンピュータシステムが、一様分布列を用いて前記要素の密度分布を再現する前記要素の初期配置を生成し、前記要素各々の初期位置を記憶部に書き込むステップをさらに含む、請求項10に記載の計算方法。前記演算するステップは、コンピュータシステムが、前記要素が配置されるべき領域を画定する容器を複数の区域に分割し、各区域に属する図形間の衝突を検知するステップをさらに備え、少なくとも同一区域に属さないため衝突し得ない図形同士のペナルティの計算が省略されることを特徴とする、請求項11に記載の計算方法。空間的に離散して配置される複数の要素から形成される離散パターンの該要素の空間配置を計算するための情報処理装置を実現するためのコンピュータ実行可能なプログラムであって、前記コンピュータを、前記離散パターンの前記要素が配置される領域内での前記要素の密度分布から、要素各々に対し、該要素各々に与えられた初期位置での密度を求めて、該密度に応じた大きさを有し該要素各々が他を斥ける領域を表す図形と、該図形の移動範囲とを設定する設定部、前記図形各々の位置を決定変数として、前記図形同士の衝突および前記図形の前記移動範囲からの突出に対しペナルティを与える目的関数を最小化して、前記図形各々の位置の最適解を演算する演算部、および前記図形各々の位置の最適解を前記要素の空間配置として出力する出力部として機能させるためのプログラム。請求項15に記載のコンピュータ実行可能なプログラムをコンピュータ可読に格納する記録媒体。上述した特許文献1および特許文献2に開示される技術は、ポテンシャルを最急降下法で解くことに相当し、ある程度の良質なドットパターンを得ることができる。しかしながら、特許文献1および特許文献2の従来技術では、多体問題としての運動方程式を解く際に、多数の点同士に働く斥力を計算する必要があり、最悪の場合で入力サイズの2乗のオーダで計算量が急増する。近年、液晶ディスプレイの大面積化に伴い上記散乱パターン内で必要なドット数が増大しているため、上記従来技術では、計算時間がかかってしまい、デバイスの大面積化に対応する観点からは、充分なものではなかった。本発明は、上記従来技術に鑑みてなされたものであり、本発明は、ドット等の要素に対し円等の仮想的な図形を設定して、上記仮想的な図形間の衝突による相互作用を導入し、仮想的な図形間の衝突が除去されるよう最適化演算することにより、良質な離散パターンを効率的に生成することが可能な情報処理装置、計算方法、プログラムおよび記録媒体を提供することを目的とする。本発明は、上記課題を解決するために、空間的に離散して配置される複数の要素点ないし微小構造であるドットから形成される離散パターンにおける該要素の空間配置を計算する、下記の特徴を有した情報処理装置を提供する。本発明の情報処理装置は、与えられた上記離散パターンの要素が配置される領域内での要素の密度分布から、要素各々に対し、要素各々に与えられた初期位置での密度を求め、該密度に応じた大きさを有し、要素各々が他を斥ける領域を表す図形を設定する。同時に、上記要素各々に対し、上記図形が移動することができる移動範囲を設定する。そして、本情報処理装置は、上記設定された図形各々の位置を決定変数として、図形同士の衝突および図形の移動範囲からの突出に対しペナルティを与える目的関数を最小化することによって、図形各々の位置の最適解を演算し、得られた図形各々の位置の最適解を上記離散パターンにおける要素の空間配置として出力する。本発明では、上記目的関数は、図形同士が衝突し合う深度に応じてペナルティを与える非線形項と、図形が移動範囲から突出する深度に応じてペナルティを与える非線形項と、必要に応じて要素が配置されるべき領域を画定する容器から図形が突出する深度に応じてペナルティを与える非線形項とを含むことができる。そして、上記目的関数は、制約なしの非線形最適化問題を構成し、上記最適解は、非線形最適化問題の局所最適解として求めることができる。上記図形同士が衝突し合う深度は、図形間で衝突による図形間の貫通を除去するために必要な平行移動の距離として定義することができる。上記突出する深度は、注目する図形と、移動範囲または容器との間で、突出による貫通を除去するために必要な平行移動の距離として定義することができる。本発明によれば、さらに、上記情報処理装置としてコンピュータシステムが実行する、離散パターンにおける該要素の空間配置の計算方法、上記情報処理装置を実現するためのコンピュータ実行可能なプログラム、および上記プログラムをコンピュータ読取可能に格納する記録媒体を提供することができる。上記構成によれば、要素間の相互作用を要素各々に対し設定した図形の衝突で表し、離散パターン生成処理を図形同士の衝突を除去ないし最小化する問題として帰着させているため、遠く離れた図形要素同士の相互作用を取り扱う必要がなく、最適解を高速に得ることが可能となる。また、得られた要素の空間配置の最適解は、ドット密度分布に応じた大きさの図形同士の衝突除去により、ドット重なりや非一様性が解消されている。ひいては、規則的パターンを含む部材との間でモアレ縞を発生させない程度に充分に不規則であり、かつ、輝度ムラが目視されない程度に充分に一様であり、かつ、任意の連続的ドット密度分布を備えることができるという要件を満たす、光学的に良質なドットパターンを高速に生成することが可能となる。以下、本発明の実施形態について説明するが、本発明は、以下の実施形態に限定されるものではない。なお、以下に説明する実施形態では、空間的に離散して配置される複数の要素から形成された離散パターンの該要素の空間配置を演算する情報処理装置として、液晶ディスプレイ用バックライトユニットにおける導光板や拡散シートで用いられる、微小な散乱体の配置を規定するドットパターンを生成するドットパターン生成装置を一例として説明する。概要本発明の実施形態によるドットパターン生成装置は、複数ドットの2次元配置を最適化演算し、一様に離散して配置されたドットから形成されるドットパターンを生成する。ドットパターン生成処理では、まず、ドット密度分布と、ドット初期配置とが与えられる。液晶ディスプレイLCD用バックライトユニットの導光板等の散乱パターンに適用する場合、液晶セル上の輝度分布を一様にするために、充填率が変化するドットパターンが必要となり、この充填率の2次元的な分布が設計データとして与えられる。上記ドット密度は、この充填率に相当する。上記ドット初期配置は、疑似乱数などの乱数関数や、超一様分布列LDS:LowDiscrepancySequenceを用いて、上記ドット密度に応じた確率で配置されたものである。初期配置の段階では、通常、ドット間で重なりを生じさせ、またドット分布に非一様性を生じさせ得る。液晶表示デバイスにおいて、散乱ドットパターン内のドット間の重なりは、その部分が輝点または暗点として目視されてしまい、ドット分布の非一様性は、輝度ムラとして知覚されてしまう。したがって、上記一様分布列等で与えられるドット初期配置そのままでは、光学的な用途に耐えない。そこで、本発明の実施形態によるドットパターン生成処理では、ドット間の相互作用を導入し、ドットの2次元配置を決定変数とする非線形最適化問題として、その最適解具体的には局所最適解を演算する。初期条件として与えられた不規則なドット初期配置を、適切な相互作用を導入して、最適化演算により一様化することによって、導光板等の散乱ドットパターンとして好適に用いることが可能な、光学的に良質なドットパターンを生成することができる。なお、本発明の実施形態において目標となる望ましいドットパターンとは、プリズムシートや液晶セルといった規則的パターンを含む部材との間でモアレ縞を発生させない程度充分に不規則であり、かつ、輝度ムラが目視されない程度充分に一様であり、かつ、任意の連続的充填率分布を備えることができる、という要件を満たすものである。本発明の実施形態のドットパターン生成処理においては、上述したドット間の相互作用は、ドット各々に対して、当該ドットが他を斥ける領域を仮想的に表す図形を設定し、目的関数中にドット各々の仮想的な図形間の衝突に対してペナルティを与える評価関数によって導入される。上記仮想的な図形、より具体的には仮想的な円は、設計データとして与えられる充填率の分布を再現するべく、各ドットに対して初期条件として与えられた位置におけるドット密度に応じた半径が設定される。すなわち、ドット密度が小さな位置に配置されたドットに対しては、比較的大きな半径の円を設定し、反対に、ドット密度が大きな位置に配置されたものに対しては、比較的小さな円を設定する。そして、最適化演算では、上記仮想的円同士の衝突の程度に応じてペナルティを与える目的関数を、記憶計算量が線形の手法を用いて反復的に最小化し、複数ドットの2次元配置を最適化する。これにより、規則的パターンを含む部材との間でモアレ縞を発生させない程度充分に不規則であり、かつ、輝度ムラが目視されない程度充分に一様であり、かつ、任意の連続的充填率分布を備えることができるという要件を満たす、光学的に良質なドットパターンを提供することが可能となる。機能ブロック以下、本発明の実施形態によるドットパターン生成装置について、機能ブロック図を参照しながら、より詳細に説明する。図1は、本発明の実施形態によるドットパターン生成装置の機能ブロック図である。本発明の実施形態によるドットパターン生成装置100は、概ね、パーソナルコンピュータ、ワークステーション、サーバなどの汎用コンピュータ装置として構成される。本発明の実施形態によるドットパターン生成装置100は、各種設計データおよびパラメータが入力される入力部110と、入力された設計データおよびパラメータに従ってドットの初期配置を生成する初期配置生成部120と、条件設定部130と、衝突除去演算部140と、出力部150とを含んで構成される。ドットパターン生成装置100は、より具体的には、シングルコアプロセッサまたはマルチコアプロセッサなどのCPU、キャッシュメモリ、RAM、ストレージデバイスなどを備え、適切なOSの制御のもと、ハードウェアおよびソフトウェアが協働して、各機能部および各処理を実現している。上記入力部110は、ドットが配置される領域以下、容器という。を規定する容器形状データ、容器内のドット密度分布を与えるドット密度分布データ、およびその他の演算条件や設計条件を規定するパラメータの入力を受け付ける。上記容器形状データは、例えば液晶ディスプレイ用バックライトユニットの導光板の散乱ドットパターンであれば、散乱体が設けられる領域の形状に応じたデータが与えられる。ここでは、説明の便宜上、矩形の枠を容器とした容器形状データが与えられるものとして説明するが、特に限定されるものではない。上記ドット密度分布データとしては、上記容器を所定の大きさの区画に区切り、各区画jj=1,..,M;Mは区画数毎のドット密度の配列データとして与えられても良く、連続したドット密度分布を与える関数gx、yおよびその係数として与えられても良い。なお、本明細書においては、ドット密度に関連して、単位領域の面積に対してドットが占める総面積の割合を表すドット充填率ρ、および単位面積あたりに配置されるドット数を表す点密度dの2種類の密度を定義するが、説明する実施形態では、ドット充填率ρが与えられ、また上記ドット密度分布は、各区画j毎のドット充填率ρjの配列として与えられるものとして説明する。上記初期配置生成部120は、入力部110で与えられたドット密度分布に応じた不規則なドット初期配置を生成する。ドット初期配置の生成方法は、疑似乱数により直接座標を決定する手法SimplePseudorandomNumberMethod、規則格子を与えて格子点の変位を疑似乱数で揺動する手法PseudorandomPerturbationMethod、超一様分布列を用いる手法などを採用することができる。初期状態におけるドット配置に対し適切な一様性および不規則性を付与し、ひいては最終的なドットパターンの品質を向上する観点からは、超一様分布列を用いる手法を採用することが望ましい。以下、超一様分布列を用いてドット密度分布に応じて不規則なドットの初期配置を生成するドット初期配置生成処理について説明する。超一様分布列LDSとは、その分布列に最初に属するN点について、ディスクレパンシDiscrepancyDNという量が下記式1で表される条件を満たすものをいう。下記式1中、Cは、ドット数Nに依存しないある定数であり、ディスクレパンシDNは、0<x,y≦1で定義された矩形領域[0,1]2について、下記式2のように定義される量である。下記式2中、Ex、yは、線分0,0-x,yを対角線とする矩形領域[0,x×[0,y内に入るドット数であり、Nは全体のドット数である。絶対値記号の内側は、ドット数の割合から、矩形領域の面積の割合を差し引いたものであり、ディスクレパンシDNは、点集合が稠密かつ一様に分布している場合にゼロとなる。下記式2より、ディスクレパンシDNが、点集合の分布の偏りを表す量となっていることが直感的に理解される。また、上述した変化するドット密度に対応してドット初期配置を生成するために、まず、ドットが配置される容器を所定の大きさの区画に分割し、合計でM個の区画とする。そして、区間0,1に規格化された3次元のLDS点集合を予め生成しておき、区画iのドット充填率をρiとして、下記方程式3より区画kを選択し、その区画kにおいて、残りのLDS点集合の桁を用いてドット位置を選択する。下記方程式3中、Uは、超一様点集合のある桁を表す。そして、生成するドットの個数だけ上記プロセスを繰り返すことによって、ドット密度分布に応じたドットパターンの初期配置が与えられる。なお、LDSを用いたドット密度分布に応じて不規則なドット初期配置の生成処理の詳細については、例えば特開2007-306576号公報特許文献1を参照することができる。図1Aは、初期配置生成部120により生成された、LEDLightEmittingDevice照明用散乱ドットパターンのドット初期配置の一部を表す図である。図1Aによれば、ドットが、左上から右下にかけてドット密度が増加するように配置されている様子が示されている。生成された初期配置のドット集合A={xi,yi|i=1,...,N}の座標データは、メモリ等の記憶装置が提供する記憶部に格納される。なお、説明する実施形態では、初期配置生成部120が、入力部110に与えられた容器形状データおよびドット密度分布データを用いて、ドット初期配置を生成するものとして説明するが、他の実施形態では、上記LDS等の手法を用いて予め生成された既存のドット初期配置データを入力データとして与えてもよい。条件設定部130は、ドット間の相互作用を導入するため、ドット集合A={xi,yi|i=1,...,N}内の各々のドットiに対し、ドットが他を斥ける領域を仮想的に表す円Siを設定する。円Siは、ドットiの初期位置におけるドット充填率ρに応じた半径riを有しており、各ドットiの初期位置xi,yiを中心として設定される。初期配置においてドット密度が小さな位置に配置されたドットに対しては、大きな半径の円、つまり大きな排斥範囲が設定され、ドット密度が大きな位置に配置されたドットに対しては、小さな半径の円、つまり小さな大きな排斥範囲が設定される。円Siの半径riは、最終的なドットパターンの光学的な品質に影響を与え得るため、以下、円Siの半径riの決定手法について詳細を説明する。無限の空間内における円の最密配置は、六方最密充填であり、本実施形態による円の半径の決定手法では、六方最密充填により円を配置した場合を勘案して円の半径を決定する。図2は、円の六方最密充填配置160を示し、図2に示すように、六方最密充填配置160においては、正三角形1個分の領域164に半円が配置されることになるため、半径r’の円162の六方最密充填配置における点密度dは、下記式4で表すことができる。円ドットの点密度dと、ドットが占める充填率ρとの関係は、下記式5で表すことができるので、ドットの代わりに容器内に配置する円の半径r’は、下記式6を用いて決定することができる。下記式5および6中、r0は、ドット半径を表し、例えば設計パラメータとして与えられるものである。また、六方最密充填配置160では、各円同士がちょうど接触する状態になっているため、最密充填の半径r’をそのまま用いるよりも、むしろ若干大きくした方が、円同士の衝突が適度に発生して、最終配置における非一様性を効果的に除去できるという経験的な観測がある。このことから、説明する実施形態では、容器Rから分割された全区画D={[sj,tj]×[uj,wj]|j=1,...,M}において各区画jに与えられるドット充填率をρjとし、下記式7中の不等式を満足する所定の定数aを用いて、下記式7によって初期位置xi,yiに配置されたドットiの半径riを好適に決定することができる。なお、下記式7中、定数aは、π/√3程度の大きさとすると良好である。なお、上記式7は、ドット密度分布が各区間毎の配列データとして与えられる実施形態で用いられる関係式を示すが、ドット密度分布を直接与える関数が入力される場合には、上記式6およびその関数を用いて、各ドットiの初期位置xi,yiからriを直接計算すればよい。また、上記式7は、散乱ドットパターンにおけるドット形状が円である場合の計算式を示す。ドット形状は、円以外にも様々な幾何学的形状が考えられるが、その場合、適宜ドットに対して定義される大きさを上記円に換算して上記ドット半径r0を設定したり、TImamichietalAmultisphereschemefor2Dand3DpackingproblemsInSLS2007ProceedingsofEngineeringStochasticLocalSearchAlgorithmsDesigningImplementingandAnalyzingEffectiveHeuristicsVolume4638ofLectureNotesinComputerScience207211Springer2007非特許文献1に開示される技術を適用し、ドットの幾何学的形状を複数の円で近似する手法を採用したりすることができる。図1Bは、条件設定部130により設定された円の集合の一部を表す図であり、図1Aで示したドット密度分布に応じた半径の分布をもって円が配置されている様子が示されている。また、図1Bを参照すると、LDS等の手法で配置されたドット初期配置では、ドットの偏りが明瞭に存在し、すなわち非一様であることが理解される。円の集合{Si={xi,yi,ri|i=1,...,N}は、メモリ等の記憶装置が提供する記憶部に格納され、後述する衝突除去演算部140による演算の際に参照される。また、説明する実施形態では、詳細は後述するが、上記ドット間の相互作用を導入するための円のほか、演算過程でドットが初期配置から離れて移動しないように、各々のドットii=1,...,Nに対し、移動できる範囲を規定する移動範囲Qiを設定する。移動範囲Qiは、ドットiの初期位置xi,yiにおけるドット充填率ρに応じた大きさを有し、ドットiの初期位置xi,yiを中心として配置された仮想的な図形で表される。上記移動範囲Qiによるドットiの移動制限は、目的関数中に、上述した円Siが、移動範囲Qiを表す図形から突出することに対してペナルティを与える評価関数を導入することによって、最適化処理中に組み込まれる。なお、移動範囲Qiは、円、四角形、その他の多角形など種々の図形領域とできるが、相互作用を評価する計算の簡素さの観点からは、図3に示すようなA正方形またはB円の形状を用いることが好ましい。また、移動範囲Qiの大きさについては、円の半径riと同様に、ドットiの初期位置xi,yiにおけるドット充填率ρに応じた大きさの範囲とすることが好ましく、ドットiに設定された円の半径riに依存する形で設定することができる。例えば4riの辺の正方形、または4riの直径の円として、移動範囲Qiを設定することができる。説明する実施形態では、移動範囲Qiは、4riの辺の正方形を用いて、各ドットiの初期位置xi,yiを中心して画定される。さらに、説明する実施形態では、詳細は後述するが、上記ドット間の相互作用および初期位置を中心とした移動範囲の制限に加えて、入力部110に入力された容器形状データを用いて、ドットを配置できる領域を規定する容器Rの仮想的な図形を設定することができる。上記容器Rによる制限は、目的関数中に、上述した円Siが、容器Rを表す図形から突出することに対してペナルティを与える評価関数を導入することによって、最適化処理中に組み込まれる。なお、説明する実施形態では、容器Rは、散乱体が設けられる領域の形状に応じた大きさを有する矩形の領域が与えられるものとする。衝突除去演算部140は、上記条件設定部130により設定された容器R、ドット各々の円Si、ドット各々の移動範囲Qiを用いて、円ドットの位置座標xi,yiを決定変数として、非線形最適化演算を行う。衝突除去演算部140は、より具体的には、円同士の衝突、円の容器からの突出および円の移動範囲からの突出に対する3種類のペナルティを総和した目的関数を、記憶計算量が線形の手法により、反復的に最小化することで、円ドットの位置座標xi,yiの局所最適解を求める。図1Cは、衝突除去演算部140により位置座標xi,yiが最適化された円の集合の一部を表す図である。図1Cに示す円の配置は、図1Bで示した円の配置と比較して、良好な一様性が実現されていることが理解される。最終的な円の集合{Si={xi,yi,ri|i=1,...,N}は、演算結果としてメモリ等の記憶部に格納されており、出力部150は、円Siの位置座標xi,yiの配列を記述した位置座標データを出力する。図1Dは、出力部150により出力される位置座標データに基づくドットパターンを表しており、図1Aに示したドット初期配置と比較して、一様なドット分布が実現されていることが理解される。非線形最適化処理]以下、本発明の実施形態の衝突除去演算部140が実行する非線形最適化処理について、詳細を説明する。上記衝突除去演算部140が解く最適化問題は、円Siの中心座標を位置ベクトルvi=xi,yiで表し、2つの図形A,Bの貫通深度をδA,Bで表し、ミンコフスキー和を丸付き加算記号で表すと、下記式8および9に示す制約なし非線形最適化問題として定式化される。下記式8中、バー付きRは、容器Rの外部領域補集合を表し、バー付きQiは、移動範囲Qiの外部領域を表す。貫通深度δSi,Sjは、円Siと円Sjとの衝突の程度を表し、貫通深度δSi,バー付きRは、円Siが容器Rから突出する程度を表し、貫通深度δSi,バー付きQiは、円Siが移動範囲Qiから突出する程度を表し、これらは、上述した3種類のペナルティを与える。図形Aと位置ベクトルvとのミンコフスキー和は、下記式10で示すように、図形Aの平行移動を表す。したがって、貫通深度の関数中の円Siと位置ベクトルviとのミンコフスキー和は、位置ベクトルviが規定する位置に中心位置がある円Siを表している。また、2つの図形A,Bの貫通深度δA,Bは、下記式11で示すように、任意の方向への平行移動が許されるときの、2つの図形A,Bの衝突を除去するために必要な平行移動の距離として定義される。下記式11中、∥...∥は、ユークリッドノルム距離を表し、φは、空集合を表す。すなわち、円同士の衝突の程度を表す貫通深度δSi,Sjは、円Siおよび円Sjの衝突を除去するために必要な平行移動の距離であり、円Siおよび円Sjが重なる場合、円の半径の和と、中心間の距離との差rirj-∥vi-vj∥として求めることができる図4Aの太矢印。また、円Siおよび円Sjが重ならない場合Si∩Sj=φは、貫通深度δSi,Sjはゼロとなる。円Siが容器Rから突出する程度を表す貫通深度δSi,バー付きRは、円Siと容器の外側領域バー付きRを表す図形との衝突を除去するために必要な平行移動の距離である図4Bの太矢印。同様に、円Siが移動範囲Qiから突出する程度を表す貫通深度δSi,バー付きQiは、円Siと移動範囲の外側領域バー付きQiを表す図形との衝突を除去するために必要な平行移動の距離である図4Cの太矢印。上記式8で表される目的関数は、円同士の衝突の程度に応じてペナルティを与える第1の項と、円が容器から突出する程度に応じてペナルティを与える第2の項と、円が移動範囲から突出する程度に応じてペナルティを与える第3の項とからなり、それぞれの項は、2次非線形項とされている。結果として目的関数は、多峰性を有し、かつ微分可能な関数となる。このため、上記式8および9で表される非線形最適化問題は、L-BFGSLimitedmemoryBroydenFletcherGoldfarbShanno法、信頼領域法、共役勾配法、BarzilaiBorwein法などの記憶計算量が線形の手法を利用して、局所最適解に高速に収束させることが可能となる。なお、説明する実施形態では、上記式8に示す目的関数の第1項~第3項は、いずれも2次非線形項としているが、微分可能なかつ微分連続性を有する関数であれば充分であり、他の実施形態では、貫通深度δの次数は、1より大きな値とすることができる。また、目的関数において、第1項~第3項それぞれに重み付けを行ってもよい。以下、本発明の実施形態による衝突除去演算部140が実行する非線形最適化処理で使用することができる、記憶計算量が線形の手法の一例として、L-BFGS法について説明する。L-BFGS法は、準ニュートン法の一種でBFGS法を省メモリ化した手法である。L-BFGS法とは、ニュートン法におけるヘッセ行列を計算せずに、勾配ベクトルを用いて、ヘッセ行列の逆行列に収束するような行列の列を逐次近似によって構成していくアルゴリズムである。下記式12は、L-BFGS法における主要な更新式を表しており、下記更新式12中、αk、Hk、および∇fzkは、それぞれ、k回目のイタレーションにおける、1次元探索によって決定されるステップ幅、探索方向を与えるヘッセ行列の逆行列の近似行列、および目的関数fzkの勾配ベクトルを表す。所定の収束条件または打ち切り条件が成立するまで、下記更新式12に関連してイタレーションを行うことにより、位置ベクトルzk=vii=1,...,Nを局所最適解へ収束させることができる。また、上記式8に示す上記目的関数は、円ペアの各組み合わせについて貫通深度δSi,Sjを計算する項が残されているが、本発明の実施形態では、ドット同士の相互作用をドット各々に対し設定した円の衝突で表し、ドットパターン生成処理を円同士の衝突を除去ないし最小化する問題として帰着させているため、遠く離れた円同士の相互作用を取り扱う必要がない。したがって、斥力を導入して多体問題を解く場合のような、あらゆる組み合わせのドット相互間の作用を演算する必要性はなく、高速に局所最適解を得ることが可能となる。上記遠く離れた円同士の相互作用は、円同士の衝突を検知するアルゴリズムを利用することにより、衝突が検出されないこれら遠く離れた円同士の演算処理を省略することが可能となる。円同士の衝突を検知するアルゴリズムとしては、スラブ分割法や平面分割法など、円が配置される空間を複数の区域に分割し、各区域に属する円同士の衝突を検知することで、少なくとも同一区域に属さないため衝突し得ない円ペアに対する計算を省略することにより、全体における円同士の衝突を高速に検知することが可能な手法を好適に挙げることができる。図5は、本実施形態の最適化演算処理に適用することができる、スラブ分割法および平面スイーブ法を組み合わせた手法を適用した円の衝突検知手法を説明する図である。本実施形態の円の衝突検知アルゴリズムでは、図5Aに示すように、まず、ドットが配置される容器Rを、等間隔hの複数のスラブR1,R2RLに分割し、各円Siを、当該円Siが交差するいずれかのスラブに割り当てる。なお、図5A中、グレイで示した円は、スラブR2に割り当てられる円を表している。衝突する円ペアは、少なくとも1つのスラブに割り当てられ、適切な間隔h>2rmax;rmaxは円の最大半径である。を与えることにより、最大で2つの隣接するスラブまで割り当てられることになる。そして、各スラブ内について、平面スイープ法を適用し、円同士の衝突を検出し、各スラブ内で衝突する円のペアの集合演算を行うことで、すべての衝突する円ペアが重複なく取得される。図5A中、太字矢印は、平面スイープの方向を表しており、ここでは、左から右スイープするものとして説明する。平面スイープ法では、各スラブに割り当てられた円を、円の左端位置xi-riで昇順にソートし、円ペアSi,Sjについて、円Sjが円Siの右側に位置しi<j≦N、かつ、円Sjの左端位置xj-rjが、円Siの右端位置xiriよりも左側にあるxiri>xj-rjという条件を満たすか否かを判定する。円Siの右側に位置する円Sjの左端が、円Siの右端よりも左側に位置する場合は、衝突し得るペアとして検出する。図5Bに示す例では、注目する円をS4とすると、円S5および円S6が衝突し得るペアとして検出される。なお、スラブ分割法および平面スイープ法に基づく衝突検知アルゴリズムの詳細については、TImamichietalPerformanceAnalysisofaCollisionDetectionAlgorithmofSpheresBasedonSlabPartitioningIEICETransactionsonFundamentalsofElectronicsCommunicationsandComputerSciencesVolumeE91AIssue923082313September2008非特許文献2を参照することができる。ハードウェア以下、本発明の実施形態によるドットパターン生成装置のハードウェア構成について説明する。図6は、本発明の実施形態によるドットパターン生成装置10のハードウェアブロック図である。図6に示したドットパターン生成装置10は、コンピュータ装置34として構成され、中央処理装置CPU12と、CPU12が使用するデータの高速アクセスを可能とするL1およびL2などのレベルを有するキャッシュメモリ14と、CPU12の処理を可能とするRAM、DRAMなどの固体メモリ素子から形成されるシステムメモリ16とを備えている。システムメモリ16は、ドット密度分布データ、ドット初期配置データや、上記最適化演算における途中結果および最終結果を記憶する記憶領域を提供する。CPU12、キャッシュメモリ14およびシステムメモリ16は、システムバス18を介して、他のデバイスまたはドライバ、例えば、グラフィックスドライバ20およびネットワークデバイスNIC22へと接続されている。グラフィックスデバイス20は、バスを介してディスプレイ装置24に接続されて、CPU12による上記ドットパターン生成処理結果をディスプレイ画面上に表示させている。また、ネットワークデバイス22は、トランスポート層レベルおよび物理層レベルでドットパターン生成装置10を、TCP/IPなどの適切な通信プロトコルを使用するネットワークへと接続している。システムバス18には、さらにI/Oバスブリッジ26が接続されている。I/Oバスブリッジ26の下流側には、PCIなどのI/Oバス28を介して、IDE、ATA、ATAPI、シリアルATA、SCSI、USBなどにより、ハードディスクなどの記憶装置30が接続されている。また、I/Oバス28には、USBなどのバスを介して、キーボードおよびマウスなどのポインティングデバイスなどの入出力装置32が接続されていて、オペレータによる上記設計データや設計パラメータの入力処理およびドットパターン生成処理実行の指令をコンピュータ装置34に対し行う。また、使用するオペレーティングシステムOSとしては、MacOS登録商標、Windows登録商標、Windows登録商標200XServer、UNIX登録商標、AIX登録商標、LINUX登録商標またはそれ以外の適切なOSを挙げることができる。ドットパターンの利用形態以下、本発明の実施形態によるドットパターン生成装置10が生成したドットパターンの利用形態について一例を示す。図7は、エッジライト型液晶表示用バックライトユニットの典型的構造を示す。図7に示すバックライトユニット200は、CCFLColdCathodeFluorescentLamp202と、CCFLリフレクタ204と、CCFL202で放射された光を反射する反射シート206と、CCFL202から放射された光を誘導する導光板208とを含む。CCFLリフレクタ204は、導光板208の一方の側面にあるCCFL202を包み、光を導光板208の入射面に集めて光源の効率を極大化させている。導光板208の上面には、導光板表面から一定の方向にすり抜ける光を散乱させ、導光板208表面全体にわたり均質に広がるように光拡散する拡散シート210と、拡散シート210から出てくる光を屈折し、集光させ、バックライト表面での輝度を増強する垂直方向および水平方向の光コリメータ212,214と、保護シート216とをさらに含む。CCFL202から放射された光は、導光板208の下面での散乱と、上面での全反射を繰り返し、全反射条件が破れたところで導光板208から射出される。散乱または拡散反射を引き起こすために、導光板208の下面には、白色顔料のドットパターンが印刷され、あるいはドットパターン状の微小構造例えば矩形のくぼみの配列が形成される。本実施形態のドットパターン生成装置10が出力する座標データから、これら導光板208の下面の表面に設けられる白色顔料のドットパターンのプリントデータ、または微小構造の配列を生成するフォトリソグラフィ用マスクパターンデータを作成することができる。以上説明した実施形態によれば、ドット間の相互作用をドット各々に対し設定した円の衝突で表し、ドットパターン生成処理を円同士の衝突を除去ないし最小化するという問題に帰着させている。このため、遠く離れた円ドット同士の相互作用を取り扱う必要性がなく、非線形最適化問題の局所最適解を高速に得ることが可能となる。また、得られたドットの空間配置の局所最適解は、ドット密度分布に応じた大きさの図形同士の衝突除去により、ドットの衝突、異常近接やその分布の非一様性が解消されている。ひいては、規則的パターンを含む部材との間でモアレ縞を発生させない程度に充分に不規則であり、かつ、輝度ムラが目視されない程度に充分に一様であり、かつ、任意の連続的ドット密度分布を備えることができるという要件を満たし、光学的に良質なドットパターンを提供することができる。特許文献1および特許文献2に開示される従来技術は、多体問題として運動方程式を解くものであり、これはポテンシャルを最急降下法で解くことに対応し、ある程度良質なドットパターンを提供することができる。しかしながら、運動法的式を解く際に、多数の点の斥力を計算する必要があり、最悪で入力サイズの2乗オーダの計算量が必要となる。これに対して、本発明の実施形態による最適化演算では、図形の衝突除去という最急降下法よりも実用的に優れた手法を用いることによって、同等以下の反復回数で高速に均衡状態に収束させることが可能となる。また、本発明の実施形態による最適化演算では、円の半径をドット密度に応じて適切に設定することにより、円同士の衝突を適度なものとしており、一回の反復における計算時間も短縮される。さらに、円の半径をドット密度に応じて適切に設定することにより、光学的に良質なドットパターンが生成されることが保証される。さらに、上記ドット各々に対し移動することができる移動範囲Qiを初期位置を中心に画定しているため、上記特許文献1および特許文献2に開示される従来技術においてみられた、一部のドットが空白領域に逃げてしまうという減少も抑制することが可能となる。以下、液晶ディスプレイ用拡散シートの具体的な設計手順を参照して、本発明の実施形態によるドットパターン生成装置の利用態様および作用効果について説明する。以下に説明するユースケースでは、対角7インチの液晶ディスプレイを備える小型端末用の拡散シートに関するものである。従来技術では、当該拡散パターンの製品を1種類作成するために、以下1~5で示す設計手順を踏むことになる。1まず、輝度ムラを低減する対象の発光表示装置の輝度分布を測定する。これには、1時間から半日程度の時間を要する場合がある。2続いて、充填率分布データを計算する。試作評価を繰り返すため、通常、幾通りかの充填率分布データを作成する。また光源付近、中央部、光源と反対側など、特異な輝度ムラを有する箇所と、それ以外の領域とを個別に計算してから貼り合わせる場合もある。この場合、充填率分布データの数は、上記箇所の組み合わせ数となる。また、測定した輝度分布は、そのままでは不規則なノイズが強く、ドットパターンの設計データとして使用できない可能性がある。たとえ特定の光源に対しては理想的な輝度分布を与える充填率分布であっても、充填率分布自体が不規則なノイズを含んでいては、ドットパターンとして汎用性がないため、低品質とみなされる。したがって、X方向、Y方向、または2次元で輝度分布を平滑化し、この平滑化後の測定輝度分布を初期状態として、これを理想的な輝度分布に改善するための充填率分布データを算出する。充填率分布データ1パターンを作成するために数時間要するため、例えば製品1種類について9=3設計方針×3箇所通りとすると、1名の人員で1~2日程度の時間を要することになる。3充填率分布データを用いてドットパターン生成処理を行う。本ユースケースによる対角7インチのLCD用のものであれば、全面にわたる70万点のドットが必要となる。従来技術では、1回の計算に7~12時間要する場合がある。複数の充填率分布データを用いる場合、そのままパターン数区分け箇所の組み合わせ数について計算を行うため、例えば9通りとすると、3~5日程度の時間を要することになる。4最適なパターン設計が完了した後は、生成したドットパターンにおいて、残留した異常接近ドットを除去し、空白領域に逃げたドットを除去する作業を、CADComputerAidedDesign上で人手にて行う。作業時間は、上記の残留異常ドットペア数やドット数に依存するが、1名の人員で数時間~数人の人員で数日程度の時間を要する場合がある。5そして、ドットの座標データをマスク業者に出荷し、マスクから拡散シートを生産する。したがって、従来技術によれば、ある条件では、2~3名の人員で10.5日程度の時間が必要となる。これに対して、本発明の実施形態によるドットパターン生成処理では、上記3の3~5日程度かかる計算が数時間1日未満で完了し、上記4の作業については、原則、不要となる。したがって、本発明の実施形態によるドットパターン生成処理によれば、上記従来技術で行った場合と同様の条件としても、合計1名の人員で3.0日程度の時間で完了させることが可能となる。また、より大面積なものを対象とすると、本発明の実施形態と上記従来技術との差はより顕著になる。以上説明したように、本発明の実施形態によれば、ドットに対し仮想的な円を設定して、上記円同士の衝突による相互作用を導入し、円同士の衝突が除去されるよう最適化演算することにより、良質なドットパターンを高速に生成することが可能な情報処理装置、計算方法、プログラムおよび記録媒体を提供することができる。なお、本発明の実施形態によるドットパターン生成装置100は、ドットパターンにおけるドット各々の位置座標の配列を記述した位置座標データを出力するものとして説明した。しかしながら、他の実施形態では、本発明のドットパターンの位置座標データを生成する機能が組み込まれた照明設計解析装置、またはマスクパターン生成装置として構成することもできる。本発明の実施形態によるドットパターン生成装置は、コンピュータ実行可能なプログラムを、コンピュータ装置にロードして各機能部を実現することにより提供される。このようなプログラムとしては、例えば、FORTRAN、COBOL、PL/I、C、C、Java登録商標、Java登録商標Beans、Java登録商標Applet、Java登録商標Script、Perl、Rubyなどのレガシープログラミング言語や、オブジェクト指向プログラミング言語などで記述された、コンピュータ実行可能なプログラムにより実現でき、コンピュータ可読な記録媒体に格納して、頒布することができる。以下、本発明の実施形態によるドットパターン生成装置による散乱ドットパターンの生成処理について、具体的な実施例をもって説明するが、本発明は後述する実施例に限定されるものでもない。1.コンピュータにおける実装クロック数2.5GHzのマルチコアプロセッサインテル登録商標Core登録商標2DuoT9300と、4GBのRAMとを備えるThinkPad登録商標X61を用いて、本発明の実施形態によるドットパターン生成装置のプログラムを実装するコンピュータシステムを構成した。本コンピュータシステムのオペレーティングシステムは、WINDOWS登録商標XPとし、上記プログラムは、Cによって記述した。また、ドット初期配置は、上記超一様分布列を用いる手法により与え、最適化演算は、L-BFGS法を用いて実装した。また、比較例として、特許文献1および特許文献2に記載された、ドット間の相互間力を定義して、多体問題を解くことでドットパターンを求めるというドットパターン生成装置のプログラムを、上記と同等のコンピュータシステム上に実装した。2.実験例設計条件として、移動範囲Qiは、円の半径をriとして4riの辺の正方形とし、半径riを決定するための上記式7中の定数aをπ/√3とし、ドット直径2r0を46μmとした。2.1.実験例1実施例設計条件として、さらに、容器Rを一辺3.0cmの正方形領域とした。用いた充填率分布データは、中心部の充填率が60であり、外延部の充填率が0であり、平均勾配が40/cmであった。本発明の実施例によるドットパターン生成装置を用いて、合計11万点のドットを配置するLED照明用散乱ドットパターンの生成処理を実行したところ、演算開始から108秒で均衡状態に収束した。2.2.実験例2実施例本発明の実施例によるドットパターン生成装置を用いて、30×157mmの矩形領域を容器Rとし、28万点のドットを配置する蛍光管直下型液晶表示バックライト用散乱ドットパターンの生成処理を実行したところ、演算開始から279秒で均衡状態に収束した。2.3.実験例3実施例本発明の実施例によるドットパターン生成装置を用いて、330×30mmの矩形領域を容器Rとし、11万点のドットを配置する液晶ディスプレイの角ムラに適用するエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンの生成処理を実行したところ、演算開始から111秒で均衡状態に収束した。2.4.実験例4~6比較例実験例4として、比較例のドットパターン生成装置を用いて、上記実験例1と同一条件で11万点のドットを配置するLED照明用散乱ドットパターンの生成処理を実行したところ、均衡状態に収束するまで38分要した。実験例5として、比較例のドットパターン生成装置を用いて、上記実験例2と同一条件で、28万点のドットを配置する蛍光管直下型液晶表示バックライト用散乱ドットパターンの生成処理を実行したところ、均衡状態に収束するまで38分要した。実験例6として、比較例のドットパターン生成装置を用いて、上記実験例3と同一条件で、11万点のドットを配置するエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンの生成処理を実行したところ、均衡状態に収束するまで15分要した。3.1.実験例1によるドットパターンの生成結果実施例図8は、上記実験例1によるLED照明用散乱ドットパターンの生成例を示す。図8Aは、超一様分布列を用いて生成されたドット初期配置によるドットパターンを示す。図8Bは、初期配置のドット各々に対し設定された円の集合を示す。図8Cは、均衡状態における円の集合を示す。図8Dは、出力される位置座標データによるドットパターンを示す。図8Aによれば、外延部から中心部にかけてドット密度が増加するようにドットが配置されており、図8Bによれば、図8Aに示すドット密度分布に応じた半径の分布をもって円が配置されている。また図8Bを参照すると、LDSで配置されたドット初期配置では、ドットの偏りが模様となって現れ、非一様な分布が明瞭に確認された。一方、図8Cに示す均衡状態で円の配置は、図8Bで示した円の配置と比較しても、極めて高い一様性が実現されていることが理解され、図8Dに示す最終的に得られるドットパターンは、図8Aに示したドット初期配置と比較して極めて一様なドット分布が実現されていることが理解される。3.2.実験例2によるドットパターンの生成結果実施例図9は、上記実験例2による蛍光管直下型液晶表示バックライト用散乱ドットパターンの生成例を示す。図9Aは、ドット初期配置によるドットパターンを示し、図9Bは、初期配置による円の集合を示す。図9Cは、均衡状態における円の集合を示し、図9Dは、出力される位置座標データによるドットパターンを示す。図9Aによれば、光源のパターンに対応して周期的にドット密度を変動させて、ドットが配置されていることが理解される。図9AおよびBを参照すると、LDSで配置されたドット初期配置では、ドットの偏りが模様となり現れ、非一様な分布が明瞭に確認される。一方、図9Cおよび図9Dに示す均衡状態の円の配置およびドットパターンでは、図9Aおよび図9Bで示したものと比較しても、極めて高い一様性が実現されていることが理解される。3.3.実験例3によるドットパターンの生成結果実施例図10は、上記実験例3によるエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンの生成例を示す。図10Aは、ドット初期配置によるドットパターンを示し、図10Bは、初期配置による円の集合を示す。図10Cは、均衡状態における円の集合を示し、図10Dは、出力される位置座標データによるドットパターンを示す。また、図11A~Dは、上記図10A~Dに示したエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンにおける左下隅の拡大図である。図10Cおよび図11C、並びに図10Dおよび図11Dに示す均衡状態の円の配置およびドットパターンでは、図10Aおよび図11A、並びに図10Bおよび図11Bで示したものと比較しても、極めて高い一様性が実現されていることが理解される。3.4.実験例6によるドットパターンの生成結果比較例実験例6で得られたエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンにおける左下隅の拡大図を図12Bに示す。図12Aは、比較のため、実験例3について得られたエッジライト型液晶表示バックライトの角ムラ低減用散乱ドットパターンの左下隅の拡大図を示す。図12Aと図12Bとを比較すると、図12Bに示す実験例6によるドットパターンでは、図12Aには認められない空白領域へのドット逃げEが発生しており、上記実験例3に比べて明確な品質の低下が認められた。4.実験例1~3実施例および実験例4~6比較例の計算時間の比較図13は、実験例1~3および実験例4~6よるドットパターン生成処理に要した計算時間を表した棒グラフである。図13に示すように、本実施例のドットパターン生成処理によれば、比較例の場合に比べて、同等以上の品質を有するドットパターンの生成処理を、8分の1から最高で20分の1の時間で計算を完了させられることが示された。5.ドットパターンにおける異常近接の評価下記表1および表2は、実験例1~3実施例および実験例4~6比較例で生成されたドットパターン中の異常ドットをカウントした結果を示す。表1は、ドットサイズ46μmに対しドット中心間距離が46μm以下、つまり明らかな衝突が生じたペア数をカウントした結果を表す。表2は、ドットサイズ46μmに対しドット中心間距離が60μm以下、つまり輝度ムラとなる蓋然性の高い異常近接ペア数をカウントした結果を表す。上記表1および表2中、LED点光源のパターンについては、実施例が上記実験例1に対応し、比較例が上記実験例4に対応する。直下型のパターンについては、実施例が上記実験例2に対応し、比較例が上記実験例5に対応する。角ムラのパターンについては、実施例が上記実験例3に対応し、比較例が上記実験例6に対応する。表1および表2中、緩和前とあるのは、ドット初期配置における明らかな衝突が生じたペア数または異常近接ペア数を示す。表1および表2に示されるように、本発明の実施例によるドットパターン生成装置によれば、生成されるドットパターンに関し、衝突するドットペアを発生させず、異常近接ドット数は、比較例に比べて低減されることが示された。6.まとめ以上までの実験例によれば、本発明の実施例によるドットパターン生成装置は、ドット間の相互間力を定義して多体問題を解くことでドットパターンを求めるという比較例の手法に比べ、非常に高速に均衡状態に収束させることが可能であり、ドットパターンの品質も、同等以上のものが得られることが示された。さらに、本発明の実施例によるドットパターンでは、一部の点が空白領域に逃げる現象が回避できることが確認された。空白領域へ逃げるドットが発生すると、人手による調整が必要となるため、本発明の実施例によるドットパターン生成処理によれば、ドット調整にかかる作業コストをも削減することができることを意味する。これまで本発明を図面に示した実施形態および実施例をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用効果を奏する限り、本発明の範囲に含まれるものである。"