مضلع على شكل نجمة

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

بصورة رسمية، يكون المضلع P على شكل نجمة إذا وُجدت نقطة z بحيث يكون لكل نقطة p من P قطعة مستقيمة ⁠${\displaystyle {\overline {zp}}}$يقع بالكامل داخل P. ^{[ 1} ]تسمىمجموعةجميع النقاط z التي ^تتمتع بهذه الخاصية (أي مجموعة النقاط التي يمكن رؤية كل P منها ) نواة P.

إذا كان المضلع النجمي محدبًا ، فإن المسافة الرابطة بين أي نقطتين منه (أقل عدد من القطع المستقيمة المتتالية الكافية لربط هاتين النقطتين) تساوي 1، وبالتالي فإن قطر المضلع الرابط (أقصى مسافة رابطة بين جميع أزواج النقاط) يساوي 1. أما إذا لم يكن المضلع النجمي محدبًا، فإن المسافة الرابطة بين نقطة في النواة وأي نقطة أخرى في المضلع تساوي 1، بينما المسافة الرابطة بين أي نقطتين داخل المضلع ولكن خارج النواة تساوي إما 1 أو 2؛ وفي هذه الحالة تكون أقصى مسافة رابطة تساوي 2.

المضلعات المحدبة لها شكل نجمي، والمضلع المحدب يتطابق مع نواته الخاصة.

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

يمكن حل اختبار ما إذا كان المضلع على شكل نجمة، وإيجاد نقطة واحدة في النواة، في وقت خطي عن طريق صياغة المشكلة كبرنامج خطي وتطبيق تقنيات البرمجة الخطية منخفضة الأبعاد (انظر http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf ، الصفحة 16).

يُحدد كل ضلع من أضلاع المضلع نصف مستوى داخلي ، وهو نصف المستوى الذي يقع حده على الخط الذي يحتوي على الضلع، ويحتوي على نقاط المضلع في جوار أي نقطة داخلية للضلع. نواة المضلع هي تقاطع جميع أنصاف مستوياته الداخلية. يمكن إيجاد تقاطع أي مجموعة من N نصف مستوى في زمن قدره Θ ( N log N ) باستخدام أسلوب فرق تسد . ^{[ 1 ]} مع ذلك، في حالة نوى المضلعات، توجد طريقة أسرع: فقد قدم لي وبريباراتا (1979) ^{[ 2 ]} خوارزمية لإنشاء النواة في زمن خطي.

• مضلع أحادي اللون