Coreset とは

計算ジオメトリでは、コアセットは、2つのセットに幾何学的尺度を適用すると(最小境界ボックスの体積など)、ほぼ等しい数になるという意味で、大きなポイントセットの形状に近似する小さなポイントのセットです。多くの自然幾何学的最適化問題は、1 +εの係数内で最適解を近似し、素早く(線形時間または近似直線時間で)発見することができ、1 /εの独立関数ここで、εは任意の正の数である。この場合、コアセットを見つけて、コアセットに正確な最適化アルゴリズムを適用するという考えに基づいて、線形時間または近似直線時間近似スキームを得る。厳密な最適化アルゴリズムがどれほど遅いかに関わらず、εの任意の固定選択に対して、この近似スキームの実行時間は、O(1)にコアセットを見つける時間を加えたものになります。