مشاكل التقارب

تُعد مسائل التقارب فئة من المسائل في الهندسة الحسابية التي تتضمن تقدير المسافات بين الأجسام الهندسية.

تُعرف مجموعة فرعية من هذه المشكلات التي يتم تحديدها من حيث النقاط فقط أحيانًا باسم مشكلات أقرب نقطة ، ^{[ 1 ]} على الرغم من أن مصطلح "مشكلة أقرب نقطة" يستخدم أيضًا بشكل مرادف للبحث عن أقرب جار .

تتمثل السمة المشتركة للعديد من هذه المشكلات في إمكانية تحديد الحد الأدنى Θ ( n log n ) لتعقيدها الحسابي عن طريق الاختزال من مشكلة تفرد العنصر استنادًا إلى ملاحظة أنه إذا كانت هناك خوارزمية فعالة لحساب نوع من المسافة الدنيا لمجموعة من الكائنات، فمن السهل التحقق مما إذا كانت هذه المسافة تساوي 0.

على الرغم من أن هذه المشاكل لا تشكل تحديًا من حيث التعقيد الحسابي، إلا أن بعضها جدير بالذكر بسبب انتشارها الواسع في تطبيقات الهندسة الحاسوبية.

• المسافة بين قطعتين مستقيمتين . لا يمكن التعبير عنها بصيغة واحدة، على عكس، مثلاً، المسافة من نقطة إلى خط . يتطلب حسابها حصرًا دقيقًا للتكوينات الممكنة، خاصة في الأبعاد الثلاثية وما فوقها. ^{[ 2 ]}
• المربع المحيط ، وهو أصغر مستطيل فائق محاذٍ للمحاور يحتوي على جميع البيانات الهندسية

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

• أقصر مسار بين العوائق
• مسافة أقرب اقتراب

• فرانكو ب. بريباراتا ومايكل إيان شاموس (1985). الهندسة الحسابية - مقدمة . سبرينغر-فيرلاغ . ISBN 0-387-96131-3الطبعة الأولى: ISBN 0-387-96131-3الطبعة الثانية، منقحة وموسعة، 1988: ISBN 3-540-96131-3ترجمة روسية، 1989: ISBN 5-03-001041-6.تُغطى مشاكل التقارب في الفصلين 6 و7.