[ تعرٌف على ] مضلع نجمي الشكل

تم النشر اليوم 13-12-2025 | [ تعرٌف على ] مضلع نجمي الشكل
تم النشر اليوم [dadate] | مضلع نجمي الشكل

الخوارزمية

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

التطبيقات

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

أمثلة

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

شرح مبسط

المضلع نجمي الشكل (بالإنجليزية: Star-shaped polygon)‏ هو منطقة مضلع في المستوى تمثل مجالًا نجميًا، أي مضلع يحتوي على نقطة يمكن من خلالها رؤية حدود المضلع بالكامل.