デローンセット

距離空間の数学理論において、εネット、εパッキング、ε被覆、一様離散集合、相対的に密な集合、およびデローン集合（ボリス・デローンにちなんで命名）は、点の間隔が均等な集合の密接に関連した定義であり、これらの集合のパッキング半径と被覆半径は、それらの間隔の均等さを測る指標となる。これらの集合は、符号理論、近似アルゴリズム、および準結晶理論に応用されている。

( M , d )が距離空間であり、X がMの部分集合である場合、Xのパッキング半径rは、Xの異なる要素間の距離の最小値の半分です。Xの点を中心とする半径rの開球はすべて互いに素です。Xの被覆半径Rは、Mのすべての点がXの少なくとも 1 つの点から距離R以内にある最小の距離です。つまり、Rは、Xの点を中心とする半径の閉球が、M全体を和集合として持つ最小の半径です。

ε-パッキングとは、パッキング半径r ≥ ε /2（同等に、最小距離≥ ε）の集合Xであり、 ε-カバリングとは、カバリング半径R ≤ εの集合Xであり、ε-ネットとは、 ε-パッキングとε-カバリングの両方である集合（ε /2 ≤ r ≤ R ≤ ε ）である。

集合は、非ゼロの充填半径（0 < r ）を持つ場合、一様に離散的であり、有限の被覆半径（ R < ∞）を持つ場合、相対的に密である。

デローン集合とは、一様に離散的であり、かつ比較的密な集合（ 0 < r ≤ R < ∞ ）である集合のことである。したがって、すべてのεネットはデローンであるが、その逆は成り立たない。^{[ 1 ] [ 2 ]}

上記の定義の中で最も制約が厳しいεネットは、 εパッキング、εカバーリング、およびデローン集合と同様に構築が困難です。しかし、 Mの点が整列しているときはいつでも、超限帰納法により、順序付けにおける前の点の集合までの距離の最小値が少なくともεであるすべての点をNに含めることで、εネットNを構築できることが示されています。次元が制限されたユークリッド空間内の有限個の点の集合の場合、各点は、直径εのセルのグリッドにマッピングし、ハッシュテーブルを使用して、近くのどのセルがすでにNの点を含んでいるかをテストすることで、定数時間でテストできます。したがって、この場合、εネットは線形時間で構築できます。^{[ 3 ] [ 4 ]} 

より一般的な有限またはコンパクトな距離空間の場合、最遠点優先走査に基づくTeo Gonzalezの代替アルゴリズムを使用して有限εネットを構築できます。このアルゴリズムは、ネットN を空に初期化し、NからM内の最も遠い点をNに繰り返し追加し、同点の場合は任意に処理し、Mのすべての点がNから距離ε以内になったときに停止します。^{[ 5 ]}次元が制限された空間では、Gonzalez のアルゴリズムは、最遠距離と最短距離の比が多項式である点集合に対してO( n log n )時間で実装でき、任意の点集合に対しても同じ時間制限で近似できます。^{[ 6 ]}   

• デローンセット– タイル百科事典