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

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

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

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

خوازمية البحث الشامل

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

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

حالة الإستواء

المسألة يمكن حلها في ( $O (n log n$ من الوقت باستخدام الاستدعاء ذاتي وخوارزمية فرق تسد، مثل:^[1]

ترتيب النقاط بالنسبة إلى إحداثيات س.
تقسيم مجموعة من النقاط إلى مجموعتين فرعيتين متساوية الحجم عن طريق خط عمودي $س = س mid$ .
حل المسألة بالاستدعاء ذاتي في المجموعات الفرعية اليمنى واليسرى، ينتج هذا الجانب الأيسر والجانب الأيمن $d Lmin$ و $d Rmin$ ، على التوالي
العثور على مسافة الحد الأدنى $d LRmin$ من بين مجموعة من أزواج من النقاط حيث نقطة واحدة تقع على الجهة اليسرى من تقسيم الرأسي والنقطة الثانية تكمن في الجهة اليمنى.
الجواب النهائي هو الحد الأدنى بين $d Lmin$ ، $d Rmin$ ، و $d LRmin$ .

Divide-and-conquer: sparse box observation

تبين أن الخطوة الرابعة يمكن تحقيقه في الزمن الخطي، مرة أخرى فإن نهج الطريقة الساذجة يتطلب حساب المسافات لجميع أزواج اليسار واليمين، كمثال في وقت تربيعي. وتستند الملاحظة الرئيسية على تبعثر الممتلكات التالية من مجموعة نقطة. نحن نعلم بالفعل أن أقرب زوج من النقاط هو أبعد عن بعضهما البعض من $المسافة = min(d Lmin, d Rmin)$ لذلك، لدينا لكل نقطة $ن$ إلى يسار الخط الفاصل لمقارنة المسافات إلى النقاط التي تقع في المستطيل الأبعاد $(المسافة , 2 \cdot المسافة )$ لى اليمين من الخط الفاصل، كما هو مبين في الشكل. وما هو أكثر من ذلك، هذا المستطيل يمكن أن يحتوي على ستة نقاط كحد أعلى مع أزواج ذوي المسافة $d Rmin$ . ولذلك، فإنه يكفي لحساب المسافات في معظم $6 ن$ بين اليسار واليمين في الخطوة الرابعة.^[5] العلاقة تكرار لعدد من الخطوات التي يمكن أن تكتب كالآتي $T (n) = 2 T (n /2) + O (n)$ والتي يمكن أن تحل باستخدام النظرية الرئيسة للحصول على $O (n log n)$ .

كما أن أقرب زوج من النقاط يعرف كحافة في تثليث ديلاوني وتتوافق مع اثنين من الخلايا المجاورة في مخطط فورونوي أقرب زوج من النقاط يمكن تحديده في الزمن الخطي نظرا لاننا عندما واحد من هذين الهيكلين. حساب تثليث ديلاوني أو مخطط فورونوي تأخذ من الوقت $O (n log n)$ . هذه الأساليب ليست فعالة ل البعد $d >2$ في حين أن خوارزمية فرق - تسد يمكن تعميمها على اتخاذ $O (n log n)$ من الوقت لأي قيمة ثابتة من $d$ .

ديناميكية مشكلة أقرب - زوج

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

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

إذا كان مستطيل الإحاطة الأصغر لجميع النقاط معروفة مسبقا والوقت ثابت باستخام دلتا الجزء الصحيح متوافرة، فإن من المتوقع تنفيذ (O(n من هيكل البيانات المقترح الذي يدعم (O(log n من الوقت المتوقع للحذف والإضافة. عندما تعدل نموذج شجرة القرارات الجبرية، الإضافة والحذف تستغرق (O(log² n من الوقت المتوقع.^[6] ومن الجدير بالذكر، على الرغم من أن تعقيد ديناميكية الخوارزمية أقرب الزوج المذكور أعلاه هو الأسي في البعد د، وبالتالي مثل خوارزمية يصبح أقل مناسبة لمشاكل الأبعاد العالية.

الملاحظات

^ ^ا ^ب 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) نسخة محفوظة 18 مايو 2015 على موقع واي باك مشين.
^ 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
^ Richard Lipton (24 سبتمبر 2011). "Rabin Flips a Coin". مؤرشف من الأصل في 2019-02-16.
^ Cormen, Leiserson, Rivest, and Stein, 2001.
^ 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.
Jon Kleinberg; Éva Tardos (2006). Algorithm Design. Addison Wesley.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link)
UCSB Lecture Notes
rosettacode.org - Closest pair of points implemented in multiple programming languages
Line sweep algorithm for the closest pair problem

[sh-1] ا ^ب 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) نسخة محفوظة 18 مايو 2015 على موقع واي باك مشين.

[fh-2] S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979

[km-3] S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995

[rl-4] Richard Lipton (24 سبتمبر 2011). "Rabin Flips a Coin". مؤرشف من الأصل في 2019-02-16.

[5] Cormen, Leiserson, Rivest, and Stein, 2001.

[6] 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)

[1]

بحاجة لمصدر

[2]

[3]

[4]

[5]

[6]