N（〜500）次元で、球/長方形に既存の点が含まれないように、最大の球または長方形を見つけたいと思います。ポイントのセット全体が、軸に沿った長方形のボックス (値の下限と上限) に囲まれています。
問題を解決するために使用できる既知の多項式時間メソッド/コードはありますか?
よく知られている 2 つのアルゴリズム: i) 四角形内の最大の空の四角形 ( http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf ) と、ii) 場所の制約内で最大の空の円を見つける ( http ://www.cs.dartmouth.edu/reports/TR86-130.pdf ) は機能しません。
上記のアルゴリズムの複雑さは N log N または N^2 log N (N は既存のポイントの数) ですが、複雑さは凸包または境界ポリゴンの頂点数の線形関数でもあります。500 次元の長方形には 2^500 の角があり、上記の手法は実行できません。
理想的には、N (点の数) と D (次元) の多項式時間で最大の円/長方形を決定できる方法 (正確である必要はありません) を探しています。
ありがとうございました。