اجتياز الأبعد أولاً

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

النقاط الخمس الأولى في عملية اجتياز مجموعة نقاط مستوية باستخدام أسلوب "الأبعد أولاً". يتم اختيار النقطة الأولى بشكل عشوائي، وتكون كل نقطة لاحقة أبعد ما يمكن عن جميع النقاط المختارة سابقاً.

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

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

التعريف والخصائص

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

يمكن وصف مسارات أبعد نقطة بالخصائص التالية. لنفترض أن لدينا عددًا k ، ولننظر إلى البادئة المكونة من أول k نقطة من مسار أبعد نقطة أولًا في أي فضاء متري. ولتكن r المسافة بين النقطة الأخيرة من البادئة وبقية النقاط فيها. عندئذٍ، تتمتع هذه المجموعة الجزئية بالخاصيتين التاليتين:

  • جميع أزواج النقاط المختارة تقع على مسافة لا تقل عن r من بعضها البعض، و
  • جميع نقاط الفضاء المتري تقع على مسافة لا تتجاوز r من المجموعة الفرعية.

وبالمقابل، فإن أي متتالية تمتلك هذه الخصائص، لجميع قيم k ، يجب أن تكون مسارًا يبدأ من الأبعد. هاتان هما الخاصيتان الأساسيتان لمجموعة ديلون ، لذا فإن كل بادئة من مسار الأبعد تشكل مجموعة ديلون. [ 3 ]

التطبيقات

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

لاحقًا، شاع استخدام نفس تسلسل النقاط على يد غونزاليس (1985) ، الذي وظّفه ضمن خوارزميات التقريب الجشعة لحل مشكلتين في التجميع، حيث يتمثل الهدف في تقسيم مجموعة من النقاط إلى k مجموعة. تسعى إحدى المشكلتين اللتين حلّهما غونزاليس بهذه الطريقة إلى تقليل القطر الأقصى للمجموعة، بينما تسعى الأخرى، المعروفة بمشكلة المركز k المتري ، إلى تقليل نصف القطر الأقصى، أي المسافة من نقطة مركزية مختارة في المجموعة إلى أبعد نقطة عنها في المجموعة نفسها. على سبيل المثال، يمكن استخدام مشكلة المركز k لنمذجة مواقع مراكز الإطفاء داخل مدينة، لضمان إمكانية وصول سيارات الإطفاء إلى أي عنوان داخل المدينة بسرعة. في كلتا مشكلتي التجميع، يختار غونزاليس مجموعة من k مركزًا للمجموعة عن طريق تحديد أول k نقطة من مسار البحث الأبعد أولًا، ثم يُنشئ المجموعات بتعيين كل نقطة إدخال إلى أقرب مركز مجموعة. إذا كانت r هي المسافة من مجموعة المراكز k المختارة إلى النقطة التالية في الموضع k + 1 في المسار، فإن كل نقطة في هذا التجميع تقع ضمن مسافة r من مركزها، ويكون قطر كل مجموعة على الأكثر 2r . مع ذلك، فإن مجموعة المراكز k مع النقطة التالية تقع جميعها على مسافة r على الأقل من بعضها البعض، وأي تجميع k سيضع نقطتين من هذه النقاط في مجموعة واحدة، إحداهما على مسافة r /2 على الأقل من مركزها، وقطرها r على الأقل . بالتالي، تعطي طريقة غونزاليس التقريبية نسبة تقريبية قدرها 2 لكلا مشكلتي التجميع. [ 3 ]   

أُعيد اكتشاف طريقة غونزاليس الاستدلالية بشكل مستقل لمسألة المركز k المتري بواسطة داير وفريز (1985) ، اللذين طبقاها بشكل أعم على مسائل المركز k الموزون. [ 5 ] وفي ورقة بحثية أخرى حول مسألة المركز k من نفس الفترة، حقق هوشباوم وشمويز (1985) نفس نسبة التقريب البالغة  2، [ 6 ] لكن تقنياتهما مختلفة. [ 5 ] ومع ذلك، غالبًا ما تُنسب طريقة غونزاليس الاستدلالية، واسم "اجتياز الأبعد أولًا"، بشكل خاطئ إلى هوشباوم وشمويز. [ 7 ] بالنسبة لكل من مسألة تجميع القطر الأدنى-الأقصى ومسألة المركز k المتري ، تُعد هذه التقريبات مثالية: فوجود طريقة استدلالية ذات زمن متعدد الحدود بنسبة تقريب ثابتة أقل من  2 يعني أن P = NP . [ 3 ] [ 6 ]

إلى جانب استخدامها في التجميع، يمكن استخدام خوارزمية البحث من الأبعد أولاً في نوع آخر من مسائل تحديد مواقع المرافق، وهي مسألة تشتت المرافق القصوى الدنيا، حيث يتمثل الهدف في اختيار مواقع k من المرافق المختلفة بحيث تكون متباعدة قدر الإمكان. وبشكل أدق، يتمثل الهدف في هذه المسألة في اختيار k نقطة من فضاء متري مُعطى أو مجموعة مُعطاة من النقاط المرشحة، بطريقة تُعظّم أقصر مسافة بين كل زوج من النقاط المختارة. ويمكن تقريب ذلك باختيار أول k نقطة من خوارزمية البحث من الأبعد أولاً. إذا كانت r تُمثل المسافة بين النقطة k وجميع النقاط السابقة، فإن كل نقطة في الفضاء المتري أو مجموعة النقاط المرشحة تقع ضمن مسافة r من أول k - 1   نقطة. بحسب مبدأ التوزيع ، يجب أن تقع نقطتان من الحل الأمثل (مهما كان) ضمن مسافة r من نفس النقطة بين أول k − 1   نقطة مختارة، و(بحسب متباينة المثلث ) ضمن مسافة 2r من بعضهما البعض. لذلك، فإن الحل الاستدلالي المُعطى بواسطة اجتياز الأبعد أولاً يقع ضمن عامل اثنين من الحل الأمثل . [ 8 ] [ 9 ] [ 10 ]

تشمل التطبيقات الأخرى لخوارزمية البحث من الأبعد أولاً: تكميم الألوان (تجميع الألوان في صورة ضمن مجموعة أصغر من الألوان التمثيلية)، [ 11 ] والمسح التدريجي للصور (اختيار ترتيب لعرض وحدات البكسل في الصورة بحيث تُنتج بادئات الترتيب نسخًا جيدة منخفضة الدقة من الصورة بأكملها بدلاً من ملء الصورة من الأعلى إلى الأسفل)، [ 12 ] واختيار النقاط في طريقة خريطة الطريق الاحتمالية لتخطيط الحركة ، [ 13 ] وتبسيط سحب النقاط ، [ 14 ] وإنشاء أقنعة لصور نصفية ، [ 15 ] [ 16 ] والتجميع الهرمي ، [ 1 ] وإيجاد أوجه التشابه بين شبكات المضلعات ذات الأسطح المتشابهة، [ 17 ] واختيار أهداف مراقبة متنوعة وعالية القيمة لاستكشاف الروبوتات تحت الماء، [ 18 ] واكتشاف الأعطال في شبكات الاستشعار ، [ 19 ] ونمذجة التنوع الوراثي ، [ 20 ] ومطابقة المركبات في أسطول غير متجانس مع تسليم العملاء الطلبات، [ 21 ] التوزيع المنتظم للمراصد الجيوديسية على سطح الأرض [ 22 ] أو أنواع أخرى من شبكات الاستشعار، [ 23 ] توليد أضواء نقطية افتراضية في طريقة عرض رسومات الحاسوب للإشعاعية الفورية، [ 24 ] وهياكل بيانات البحث عن النطاق الهندسي . [ 25 ]

الخوارزميات

خوارزمية جشعة دقيقة

يمكن حساب اجتياز مجموعة نقاط محدودة من الأبعد أولاً بواسطة خوارزمية جشعة تحافظ على مسافة كل نقطة من النقاط المختارة مسبقًا، وذلك بتنفيذ الخطوات التالية: [ 3 ]

  • قم بتهيئة تسلسل النقاط المختارة إلى تسلسل فارغ، وقم بتعيين المسافات بين كل نقطة والنقاط المختارة إلى ما لا نهاية.
  • مع العلم أنه لم يتم اختيار جميع النقاط، كرر الخطوات التالية:
    • قم بمسح قائمة النقاط التي لم يتم تحديدها بعد للعثور على نقطة p التي تبعد أقصى مسافة عن النقاط المحددة.
    • قم بإزالة p من النقاط التي لم يتم تحديدها بعد وأضفها إلى نهاية سلسلة النقاط المحددة.
    • لكل نقطة متبقية لم يتم تحديدها بعد q ، استبدل المسافة المخزنة لـ q بالحد الأدنى لقيمتها القديمة والمسافة من p إلى q .

بالنسبة لمجموعة من n نقطة، تتطلب هذه الخوارزمية O(n²) خطوة و O ( n² ) عملية حساب المسافة . [ 3 ]

التقريبات

تُطبَّق خوارزمية تقريب أسرع ، قدمها هار-بيليد ومندل (2006) ، على أي مجموعة جزئية من النقاط في فضاء متري ذي بُعد مضاعف محدود ، وهو فئة من الفضاءات تشمل الفضاءات الإقليدية ذات البُعد المحدود. تجد خوارزميتهم سلسلة من النقاط بحيث تكون المسافة بين كل نقطة وأخرى ضمن عامل 1 − ε   من أبعد مسافة عن النقطة المختارة سابقًا، حيث يمكن اختيار ε كأي عدد موجب. تستغرق هذه الخوارزمية وقتًايا(نسجل⁡ن){\displaystyle O(n\log n)}[ 2 ]​

لا تنطبق نتائج الأبعاد المضاعفة المحدودة على الفضاءات الإقليدية عالية الأبعاد، لأن العامل الثابت في ترميز Big O لهذه الخوارزميات يعتمد على البُعد. بدلاً من ذلك، توجد طريقة تقريبية مختلفة تعتمد على مبرهنة جونسون-ليندنستراوس والتجزئة الحساسة للموقع، ولها وقت تشغيليا(ε-2ن1+1/(1+ε)2+o(1)).{\displaystyle O(\varepsilon ^{-2}n^{1+1/(1+\varepsilon )^{2}+o(1)}).} بالنسبة للمقاييس المحددة بأقصر المسارات على الرسوم البيانية غير الموجهة الموزونة، فإن البناء التزايدي العشوائي القائم على خوارزمية ديكسترا يحقق وقتًايا(ε-1مسجل⁡نسجل⁡نε){\displaystyle O(\varepsilon ^{-1}m\log n\log {\tfrac {n}{\varepsilon }})}حيث يمثل n و m عدد رؤوس وحواف الرسم البياني المدخل، على التوالي. [ 26 ]

إدخال فورونوي التدريجي

لاختيار النقاط من فضاء متصل كالمستوى الإقليدي ، بدلاً من مجموعة محدودة من النقاط المرشحة، لن تنجح هذه الطرق مباشرةً، نظرًا لوجود عدد لا نهائي من المسافات التي يجب مراعاتها. بدلاً من ذلك، يجب اختيار كل نقطة جديدة كمركز لأكبر دائرة فارغة مُحددة بمجموعة النقاط المختارة سابقًا. [ 12 ] يقع هذا المركز دائمًا على رأس من رؤوس مخطط فورونوي للنقاط المختارة، أو عند نقطة يتقاطع فيها أحد أضلاع مخطط فورونوي مع حدود المجال. في هذه الصيغة، تُسمى طريقة إنشاء مسارات البحث من الأبعد أولاً أيضًا بإدخال فورونوي التزايدي . [ 27 ] وهي تُشبه تحسين ديلاوناي لتوليد شبكة العناصر المحدودة ، لكنها تختلف في اختيار رأس فورونوي الذي يُدرج في كل خطوة. [ 28 ]

انظر أيضاً

  • خوارزمية لويد ، وهي طريقة مختلفة لتوليد نقاط متباعدة بانتظام في الفضاءات الهندسية

مراجع

  1. 1 2 داسغوبتا، س.؛ لونغ، ب.م. (2005)، "ضمانات الأداء للتجميع الهرمي"، مجلة علوم الحاسوب والنظم ، 70 (4): 555-569 ، doi : 10.1016/j.jcss.2004.10.006 ، MR 2136964 
  2. 1 2 3 هار-بيليد، س .؛ مندل، م. (2006)، "البناء السريع للشبكات في المقاييس منخفضة الأبعاد، وتطبيقاتها"، مجلة SIAM للحوسبة ، 35 (5): 1148-1184 ، arXiv : cs/0409057 ، doi : 10.1137/S0097539704446281 ، MR 2217141 ، S2CID 37346335  
  3. 1 2 3 4 5 غونزاليس، تي إف (1985)، "التجميع لتقليل أقصى مسافة بين المجموعات"، علوم الحاسوب النظرية ، 38 ( 2-3 ): 293-306 ، Bibcode : 1985TComS..38..293G ، doi : 10.1016/0304-3975(85)90224-5 ، MR 0807927 
  4. ↑ روزنكرانتز، دي جيه؛ ستيرنز، آر إي؛ لويس، بي إم الثاني (1977)، "تحليل لعدة طرق استدلالية لمسألة البائع المتجول"، مجلة SIAM للحوسبة ، 6 (3): 563-581 ، doi : 10.1137/0206041 ، MR 0459617 ، S2CID 14764079  
  5. 1 2 داير، إم إي ؛ فريز، إيه إم (1985)، "طريقة استدلالية بسيطة لمسألة المركز p " (ملف PDF) ، رسائل بحوث العمليات ، 3 (6): 285-288 ، doi : 10.1016/0167-6377(85)90002-1 ، MR 0797340 
  6. 1 2 هوشباوم، دوريت س .؛ شمويس، ديفيد ب. (1985)، "أفضل طريقة استدلالية ممكنة لمسألة المركز k "، رياضيات بحوث العمليات ، 10 (2): 180-184 ، doi : 10.1287/moor.10.2.180 ، MR 0793876 
  7. ↑ للاطلاع على أمثلة بارزة على الإسناد غير الصحيح لقاعدة البحث من الأبعد إلى هوشباوم وشمويز (1985) ، انظر، على سبيل المثال،
    • داسغوبتا، سانجوي (2002)، "ضمانات الأداء للتجميع الهرمي"، في كيفينين، يركي؛ سلون، روبرت هـ. (محرران)، نظرية التعلم الحسابي، المؤتمر السنوي الخامس عشر حول نظرية التعلم الحسابي، COLT 2002، سيدني، أستراليا، 8-10 يوليو 2002، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد  2375، سبرينغر، الصفحات 351-363 ، doi : 10.1007/3-540-45435-7_24 ، ISBN  978-3-540-43836-6(تم تصحيحها في نسخة المجلة لعام 2005 من نفس الورقة البحثية)
    • أغاروال، سمير؛ رامامورثي، رافي؛ بيلونجي، سيرج جيه؛ جنسن، هنريك وان (2003)، "أخذ عينات الأهمية المنظمة لخرائط البيئة"، معاملات ACM للرسومات ، 22 (3): 605-612 ، doi : 10.1145/882262.882314
    • بارام، يورام؛ اليانيف، ران؛ لوز، كوبي (2004)، " الاختيار عبر الإنترنت لخوارزميات التعلم النشط" (ملف PDF) ، مجلة أبحاث التعلم الآلي ، 5 : 255-291
    • باسو، سوغاتو؛ بيلينكو، ميخائيل؛ بانيرجي، أريندام؛ موني، ريموند ج. (2006)، "التجميع شبه الموجه الاحتمالي مع القيود"، في شابيل، أوليفييه؛ شولكوف، برنارد؛ زين، ألكسندر (محررون)، التعلم شبه الموجه ، مطبعة معهد ماساتشوستس للتكنولوجيا، ص 73-102 ، doi : 10.7551/mitpress/9780262033589.003.0005 ، ISBN  978-0-262-03358-9
    • ليما، كريستيان فيريرا ليموس؛ أسيس، فرانسيسكو م.؛ دي سوزا، كليونيلسون بروتاسيو (2011)، "دراسة مقارنة لاستخدام إنتروبيا شانون، وريني، وتساليس لاختيار السمات في كشف اختراق الشبكة"، ورشة عمل IEEE الدولية حول القياس والشبكات، M&N 2011، أنا كابري، إيطاليا، 10-11 أكتوبر 2011 ، IEEE، الصفحات 77-82 ، doi : 10.1109/IWMN.2011.6088496 ، ISBN  978-1-4577-0455-0، S2CID 7510040 
    • "Class FarthestFirst" ، برنامج Weka ، الإصدار 3.9.5 ، جامعة وايكاتو، 21 ديسمبر 2020 ، تم الاطلاع عليه بتاريخ 6 نوفمبر 2021 – عبر SourceForge
  8. ↑ وايت، دوغلاس ج. (1991)، "مسألة التشتت الأقصى"، مجلة IMA للرياضيات التطبيقية في الأعمال والصناعة ، 3 (2): 131-140 (1992)، doi : 10.1093/imaman/3.2.131 ، MR 1154657 ينسب وايت استخدام خوارزمية البحث من الأبعد أولاً كطريقة استدلالية لحل هذه المشكلة إلى ستوير، ر. إي. (1986)، تحسين المعايير المتعددة: النظرية والحساب والتطبيقات ، نيويورك: وايلي
  9. ↑ تامر، آري (1991)، "تحديد موقع المرافق المزعجة على الرسوم البيانية"، مجلة SIAM للرياضيات المتقطعة ، 4 (4): 550-567 ، doi : 10.1137/0404048 ، MR 1129392 
  10. ↑ رافي، إس إس؛ روزنكرانتز، دي جيه؛ تايي، جي كي (1994)، "خوارزميات استدلالية وحالات خاصة لمسائل التشتت"، بحوث العمليات ، 42 (2): 299-310 ، doi : 10.1287/opre.42.2.299 ، JSTOR 171673 ، S2CID 16489402  
  11. ↑ شيانغ، ز. (1997)، "تكميم الصور الملونة عن طريق تقليل أقصى مسافة بين المجموعات"، معاملات ACM في الرسومات ، 16 (3): 260-276 ، doi : 10.1145/256157.256159 ، S2CID 17713417 
  12. 1 2 إيلدار، ي.؛ ليندنبوم، م.؛ بورات، م.؛ زيفي، ي.ي. (1997)، "استراتيجية أبعد نقطة لأخذ عينات الصور التدريجي"، معاملات IEEE في معالجة الصور ، 6 (9): 1305-1315 ، Bibcode : 1997ITIP....6.1305E ، doi : 10.1109/83.623193 ، PMID 18283019 
  13. ^ مازر، إي. أهواكتزين، جي إم؛ Bessiere، P. (1998)، “خوارزمية Ariadne’s clew”، مجلة أبحاث الذكاء الاصطناعي ، 9 : 295–316 ، أرخايف : 1105.5440 ، دوى : 10.1613/jair.468
  14. ↑ مونينغ، سي.؛ دودجسون، إن إيه (2003)، "خوارزمية جديدة لتبسيط سحابة النقاط"، المؤتمر الدولي الثالث لجمعية IASTED حول التصور والتصوير ومعالجة الصور
  15. ↑ غوتسمان، كريغ؛ أليباخ، جان ب. (1996)، "حدود وخوارزميات لشاشات التمويه" (ملف PDF) ، في روغوفيتز، بيرنيس إي.؛ أليباخ، جان ب. (محرران)، الرؤية البشرية والتصوير الإلكتروني ، وقائع SPIE، المجلد 2657، الصفحات 483-492 ، doi : 10.1117/12.238746 ، S2CID 10608234   
  16. ↑ شهيدي، ر.؛ مولوني، س.؛ رامبوني، ج. (2004)، "تصميم أقنعة أبعد نقطة لتظليل الصور"، مجلة EURASIP لمعالجة الإشارات التطبيقية ، 2004 (12): 1886-1898 ، Bibcode : 2004EJASP2004...45S ، doi : 10.1155/S1110865704403217
  17. ↑ ليبمان، ي.؛ فانكهاوزر، ت. (2009)، "التصويت باستخدام موبيوس لتحديد تطابق الأسطح"، وقائع مؤتمر ACM SIGGRAPH ، الصفحات 72:1–72:12، doi : 10.1145/1576246.1531378 ، ISBN  978-1-60558-726-4، S2CID 6001942 
  18. ↑ جيردهار، ي.؛ جيغير، ب.؛ دوديك، ج. (2012)، "الاستكشاف التكيفي المستقل تحت الماء باستخدام نمذجة المواضيع عبر الإنترنت" (ملف PDF) ، وقائع الندوة الدولية للروبوتات التجريبية
  19. ↑ ألتينيسيك، يو.؛ يلدريم، م.؛ إركان، ك. (2012)، "عزل أعطال المستشعرات غير المحددة مسبقًا باستخدام خوارزمية اجتياز الأبعد أولًا"، مجلة الهندسة الكيميائية والبحوث الصناعية ، 51 (32): 10641-10648 ، doi : 10.1021/ie201850k
  20. ↑ بوردويتش، ماغنوس؛ رودريغو، ألين؛ سيمبل، تشارلز (2008)، "اختيار التصنيفات لحفظها أو تسلسلها: معايير مرغوبة وحل جشع"، علم الأحياء المنهجي ، 57 (6): 825-834 ، doi : 10.1080/10635150802552831 ، PMID 19085326 
  21. ↑ فيشر، مارشال ل.؛ جايكومار، رامشاندرا (1981)، "طريقة استدلالية معممة لتخصيص مسارات المركبات"، الشبكات ، 11 (2): 109-124 ، doi : 10.1002/net.3230110205 ، MR 0618209 كما ورد في غيسينز، فيليب؛ غولدن، بروس؛ أسعد، أرجانج (1986)، "طريقة استدلالية جديدة لتحديد حجم الأسطول وتكوينه"، في غالو، جورجيو؛ ساندي، كلاوديو (محرران)، Netflow at Pisa ، دراسات البرمجة الرياضية، المجلد 26، سبرينغر، الصفحات 233-236 ، doi : 10.1007/bfb0121103 ، ISBN   978-3-642-00922-8
  22. ↑ هاس، هايو (2000)، "طريقة جديدة لاختيار مواقع إضافية لتجانس توزيع نقطي كروي غير متجانس"، في روميل، راينهارد؛ دريوز، هيرمان؛ بوش، فولفغانغ؛ وآخرون (محررون)، نحو نظام رصد جيوديسي عالمي متكامل (IGGOS): ندوة القسم الثاني من الرابطة الدولية للجيوديسيا، ميونيخ، 5-9 أكتوبر 1998، ملصقات - الجلسة ب ، ندوات الرابطة الدولية للجيوديسيا، المجلد 120، سبرينغر، الصفحات 180-183 ، doi : 10.1007/978-3-642-59745-9_35 ، ISBN    978-3-642-64107-7
  23. ^ فييرا، لويز فيليبي م. فييرا، ماركوس أوغوستو م.؛ الأماكن القريبة : لوريرو، أنطونيو AF. سيلفا، ديوجينيس سيسيليو؛ فرنانديز، أنطونيو أوتافيو (2004)، “خوارزمية نشر شبكة الاستشعار التزايدية الفعالة” (PDF) ، بروك. سيمب البرازيلي شبكات الكمبيوتر ، ص 3–14 ، أرشفة من النسخة الأصلية (PDF) بتاريخ 2015-07-16 ، استرجاعها 2015-07-16 
  24. ^ لين ، سامولي. سارانساري، هانو؛ كونتكانين، جان؛ ليهتينن، جاكو؛ Aila، Timo (2007)، “Incremental Instant radiosity for real-time indirect Illumination”، وقائع مؤتمر Eurographics الثامن عشر حول تقنيات العرض (EGSR'07) ، Aire-la-Ville، Switzerland، Switzerland: Eurographics Association، الصفحات من 277 إلى 286، دوى : 10.2312/EGWR/EGSR07/277-286 ، ISBN  978-3-905673-52-4، S2CID 18626929 
  25. ↑ عبار، س.؛ عامر يحيى، س.؛ إنديك، ب .؛ مهابادي، س.؛ فاراداراجان، ك. ر. (2013)، "مشكلة الجوار المتنوع"، وقائع الندوة السنوية التاسعة والعشرين حول الهندسة الحسابية ، ص 207-214 ، doi : 10.1145/2462356.2462401 ، hdl : 1721.1/87000 ، ISBN  978-1-4503-2031-3، S2CID 6286186 
  26. ↑ إبستين، ديفيد ؛ هار-بيليد، سارييل ؛ سيديروبولوس، أناستاسيوس (2020)، "التجميع الجشع التقريبي واختيار المسافة لمقاييس الرسم البياني"، مجلة الهندسة الحسابية ، 11 (1): 629-652 ، doi : 10.20382/jocg.v11i1a25 ، MR 4194877 ، S2CID 18316279  
  27. ↑ تيراموتو، ساتشيو؛ أسانو، تيتسو ؛ كاتوه، ناوكي؛ دوير، بنجامين (2006)، "إدراج النقاط بشكل موحد في كل لحظة" ، مجلة IEICE للمعاملات في المعلومات والأنظمة ، E89-D (8): 2348–2356 ، Bibcode : 2006IEITI..89.2348T ، doi : 10.1093/ietisy/e89-d.8.2348 ، hdl : 2433/84849
  28. ↑ روبرت، جيم (1995)، "خوارزمية تحسين ديلاوناي لتوليد شبكة ثنائية الأبعاد عالية الجودة"، مجلة الخوارزميات ، 18 (3): 548-585 ، Bibcode : 1995JAlgo..18..548R ، doi : 10.1006/jagm.1995.1021