مجموعة ديلون

في النظرية الرياضية للفضاءات المترية ، تُعدّ الشبكات إبسيلونية ، والتعبئات إبسيلونية ، والتغطية إبسيلونية ، والمجموعات المنفصلة بانتظام ، والمجموعات الكثيفة نسبيًا ، ومجموعات ديلون (نسبةً إلى بوريس ديلون ) عدة تعريفات وثيقة الصلة لمجموعات النقاط المتباعدة جيدًا ، ويقيس نصف قطر التعبئة ونصف قطر التغطية لهذه المجموعات مدى تباعدها. لهذه المجموعات تطبيقات في نظرية الترميز ، وخوارزميات التقريب ، ونظرية أشباه البلورات .

إذا كان ( M , d ) فضاءً متريًا، و X مجموعة جزئية من M ، فإن نصف قطر التعبئة r للمجموعة X يساوي نصف أصغر مسافة بين عناصر X المختلفة . ستكون الكرات المفتوحة التي نصف قطرها r والمتمركزة عند نقاط X منفصلة تمامًا عن بعضها. أما نصف قطر التغطية R للمجموعة X فهو أصغر مسافة بحيث تكون كل نقطة من M ضمن مسافة R من نقطة واحدة على الأقل في X ؛ أي أن R هو أصغر نصف قطر بحيث تكون الكرات المغلقة التي يبلغ نصف قطرها هذا والمتمركزة عند نقاط X متحدة مع جميع عناصر M.

التعبئة ε هي مجموعة X ذات نصف قطر تعبئة r ≥ ε /2 (بمعنى آخر ، الحد الأدنى للمسافة ≥ ε )، والتغطية ε هي مجموعة X ذات نصف قطر تغطية R ≤ ε ، والشبكة ε هي مجموعة تكون كل من التعبئة ε والتغطية ε ( ε /2 ≤ r ≤ R ≤ ε ).

تكون المجموعة منفصلة بشكل منتظم إذا كان لها نصف قطر تعبئة غير صفري ( 0 < r )، وتكون كثيفة نسبيًا إذا كان لها نصف قطر تغطية محدود ( R < ∞ ).

مجموعة ديلون هي مجموعة منفصلة بانتظام وكثيفة نسبيًا ( 0 < r ≤ R < ∞ ). وبالتالي، فإن كل شبكة إبسيلون هي مجموعة ديلون، ولكن ليس العكس. ^{[ 1 ] [ 2 ]}

باعتبارها التعريف الأكثر تقييدًا من بين التعريفات المذكورة أعلاه، فإن بناء الشبكات ε لا يقل صعوبة عن بناء حزم ε ، وتغطيات ε ، ومجموعات ديلون. مع ذلك، عندما يكون لنقاط M ترتيب جيد ، يُظهر الاستقراء المتسامي أنه من الممكن بناء شبكة ε N ، وذلك بتضمين كل نقطة في N يكون الحد الأدنى للمسافات بينها وبين مجموعة النقاط السابقة في الترتيب ε على الأقل . بالنسبة للمجموعات المحدودة من النقاط في فضاء إقليدي ذي بُعد محدود، يمكن اختبار كل نقطة في زمن ثابت عن طريق رسمها على شبكة من الخلايا قطرها ε ، واستخدام جدول تجزئة لاختبار أي الخلايا المجاورة تحتوي بالفعل على نقاط من N ؛ وبالتالي، في هذه الحالة، يمكن بناء شبكة ε في زمن خطي . ^{[ 3 ] [ 4 ]} 

بالنسبة للفضاءات المترية المحدودة أو المدمجة الأكثر عمومية ، يمكن استخدام خوارزمية بديلة لـ تيو غونزاليس، تعتمد على اجتياز الأبعد أولاً، لإنشاء شبكة ε محدودة . تبدأ هذه الخوارزمية الشبكة N فارغة، ثم تضيف إليها بشكل متكرر أبعد نقطة في M عن N ، مع كسر التعادلات بشكل عشوائي، وتتوقف عندما تكون جميع نقاط M ضمن مسافة ε من N. [ ^{5 ]} في الفضاءات ذات بُعد المضاعفة المحدود ، يمكن تنفيذ خوارزمية غونزاليس في زمن O( n log n ) لمجموعات النقاط التي تكون فيها النسبة بين أبعد وأقرب مسافة متعددة الحدود، ويمكن تقريبها في نفس الحد الزمني لمجموعات النقاط العشوائية ^{. [ 6 ]}   

• مجموعة ديلون – موسوعة البلاطات