فك شفرة مسألة أقرب زوج من النقاط

مسألة أقرب زوج من النقاط (بالإنجليزية: Closest pair of points problem) هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية.

الخوارزمية الأكثر معرفة لإيجاد المسافة بين جميع أزواج النقاط في مساحة من البعد د واختيار الحد الأدنى تتطلب من الوقت (O(n log n في مسافة إقليدية في بعد ثابت د. في نموذج شجرة القرارات الجبرية الخوارزمية (O(n log n هي المثالية.المثالية يتبع من ملاحظتها أن مشكلة تفرد العنصر (مع الحد الأدنى ل (Ω(n log n) قابلة للاختزال لمسألة أقرب زوج من النقاط سواءٌ الحد الأدنى هو صفر بعد حل مسألة أقرب زوج من النقاط نستطيع الإجابة على سؤال عما إذا كان هنالك نوعان من نقاط متطابقة.

في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n. إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n