d次元単位ボール内の格子生成

$ d $次元の単位ボール($ ell_2 $
-normに関して)内のすべての格子点を生成するための標準アルゴリズムがあるかどうかを知りたいと思っています。

ブルートフォースのアプローチは、$ ell_ infty $単位のボールの上に格子を生成し、各点をループし、厳密に$ 1
$より大きいノルムを持つ点を取り除くことです。私は、この問題を解決するより洗練されたアプローチがあるのだろうかと思っていました。私の最初の考えは、$
n $点で$ d-1
$次元の球を覆い、これらの点を使って格子座標ベクトルを生成するために使用できる「限界」を見つけようとすることです。そして、これらの限界$
[a_1、b_1] times [a_2、b_2] times … times [a_d、b_d]
$で定義された間隔で格子を定義します。しかし、私の考えでは、実際に前述の限界を決定するために、球に置くポイント数とアルゴリズムを決めることは自明ではありません。

別のアプローチは、ボールに内接することができる最大体積の多面体の座標が何であるかを考えて、何らかの形でそれらが格子上にあるように制約することです。これもやはり些細なことではありません。同様の考え方は、頂点が格子点であるという制約を適用して単位ボールを含めることができる最小多面体を見つけることです。次に、2つの格子点の間の距離を減算し、球の内部で終わることができます。

既知の解決策のこれらの問題のいずれか/解決するのは簡単ではありませんか?

前もって感謝します。

ベストアンサー

一般に、そのような点が存在するかどうかを知ることさえ困難です。 最短ベクトル問題(SVP)と同等であり、この問題に対する多項式時間アルゴリズムはないと推測した。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です