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

مسألة أقرب زوج من النقاط  هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليديةM. I. Shamos and D. Hoey. "Closest-point problems." In Proc. 16th Annual جمعية مهندسي الكهرباء والإلكترونيات Symposium on Foundations of Computer Science (FOCS), pp. 151—162, 1975 (DOI 10.1109/SFCS.1975.8)  كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية.

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

في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (.S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979 إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995

 خوازمية البحث الشامل 
مسألة أقرب زوج من النقاط يمكن حسابه في (رمز O الكبير(n2 من خلال استخدام بحث شامل. ولإتمام ذلك يجب حساب المسافة بين كل زوج من النقاط المختلفة حيث أن عدد هذه النقاط يساوي ن (ن-1)/2، وإيجاد زوج من النقاط بأقصر مسافة، كالآتي.

 أقل مسافة = لانهاية
 من س = 1 إلى الطول (ط) - 1
 من ص = ص + 1 إلى الطول (ط)
 دع ب = ب[س], ق = ب[ص]
 إذا المسافة(ب, ق) < أقل مسافة:
 أقل مسافة = المسافة(ب, ق)
 أقرب زوج = (ب, ق)
 أرجع أقرب زوج

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

يمين|تصغير|Divide-and-conquer: sparse box observation

تبين أن الخطوة الرابعة يمكن تحقيقه في الزمن الخطي، مرة أخرى فإن نهج الطريقة الساذجة يتطلب حساب المسافات لجميع أزواج اليسار واليمين، كمثال في وقت تربيعي. وتستند الملاحظة الرئيسية على تبعثر الممتلكات التالية من مجموعة نقطة. نحن نعلم بالفعل أن أقرب زوج من النقاط هو أبعد عن بعضهما البعض من  لذلك، لدينا لكل نقطة  إلى يسار الخط الفاصل لمقارنة المسافات إلى النقاط التي تقع في المستطيل الأبعاد  لى اليمين من الخط الفاصل، كما هو مبين في الشكل. وما هو أكثر من ذلك، هذا المستطيل يمكن أن يحتوي على ستة نقاط كحد أعلى مع أزواج ذوي المسافة . ولذلك، فإنه يكفي لحساب المسافات في معظم  بين اليسار واليمين في الخطوة الرابعة.Cormen, Leiserson, Rivest, and Stein, 2001. العلاقة تكرار لعدد من الخطوات التي يمكن أن تكتب كالآتي  والتي يمكن أن تحل باستخدام النظرية الرئيسة للحصول على .

كما أن أقرب زوج من النقاط يعرف كحافة في تثليث ديلاوني وتتوافق مع اثنين من الخلايا المجاورة في مخطط فورونوي أقرب زوج من النقاط يمكن تحديده في الزمن الخطي نظرا لاننا عندما واحد من هذين الهيكلين. حساب تثليث ديلاوني أو مخطط فورونوي تأخذ من الوقت . هذه الأساليب ليست فعالة ل البعد  في حين أن خوارزمية فرق - تسد يمكن تعميمها على اتخاذ  من الوقت لأي قيمة ثابتة من .

 ديناميكية مشكلة أقرب - زوج 
النسخة الديناميكي لهذه المشكلة أقرب الزوج تذكر على النحو التالي:
 بالنظر إلى مجموعة ديناميكية من الأشياء تجد الخوارزميات وهياكل البيانات لإعادة الحساب كفاءة أقرب زوج من الأشياء في كل مرة يتم إدراج الأشياء أو حذفها.

إذا كان مستطيل الإحاطة الأصغر لجميع النقاط معروفة مسبقا والوقت ثابت باستخام دلتا الجزء الصحيح متوافرة، فإن من المتوقع تنفيذ (O(n من هيكل البيانات المقترح الذي يدعم (O(log n من الوقت المتوقع للحذف والإضافة. عندما تعدل نموذج شجرة القرارات الجبرية، الإضافة والحذف تستغرق (O(log2 n من الوقت المتوقع.Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid, "Randomized Data Structures For The Dynamic Closest-Pair Problem", SIAM J. Comput., vo. 26, no. 4, 1998, preliminary version reported at the 4th Annu. ACM-SIAM Symp. on Discrete Algorithms, pp. 301–310 (1993) ومن الجدير بالذكر، على الرغم من أن تعقيد ديناميكية الخوارزمية أقرب الزوج المذكور أعلاه هو الأسي في البعد د، وبالتالي مثل خوارزمية يصبح أقل مناسبة لمشاكل الأبعاد العالية.

 الملاحظات 

 المراجع 

 Thomas H. Cormen, Charles E. Leiserson, رونالد ريفست، and كليفورد شتاين. مقدمة في الخوارزميات (كتاب), Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.

 UCSB Lecture Notes
 rosettacode.org - Closest pair of points implemented in multiple programming languages
 Line sweep algorithm for the closest pair problem

تصنيف:خوارزميات هندسة رياضية