|
مضلع نجمي الشكل المضلع نجمي الشكل (بالإنجليزية: Star-shaped polygon) هو منطقة مضلع في المستوى تمثل مجالًا نجميًا، أي مضلع يحتوي على نقطة يمكن من خلالها رؤية حدود المضلع بالكامل. يكون المضلع P على شكل نجمة إذا كانت هناك نقطة z لكل نقطة p من P بحيث يقع الجزء zp بالكامل داخل P.[1] تسمى مجموعة النقاط z بهذه الخاصية نواة P. إذا كان المضلع على شكل نجمة محدبًا، فإن مسافة الارتباط بين أي نقطتين من نقاطه (الحد الأدنى لعدد مقاطع الخط المتسلسلة الكافية لربط هذه النقاط) هي 1، وبالتالي فإن قطر ارتباط المضلع (أقصى مسافة ارتباط على جميع أزواج النقاط) هي 1. إذا لم يكن مضلع على شكل نجمة محدبًا، فإن مسافة الارتباط بين نقطة في النواة وأي نقطة أخرى في المضلع هي 1، بينما مسافة الارتباط بين أي نقطتين في المضلع ولكن خارج النواة هي إما 1 أو 2؛ في هذه الحالة، تكون مسافة الارتباط القصوى 2. أمثلة
الخوارزميةاختبار ما إذا كان المضلع نجمي الشكل، وإيجاد نقطة واحدة في النواة، يمكن حلها في تعقيد الوقت عن طريق صياغة المشكلة كبرنامج خطي وتطبيق تقنيات للبرمجة الخطية منخفضة الأبعاد. تحدد كل حافة من مضلع نصف مستوى داخلي، نصف المستوى الذي تقع حدوده على الخط الذي يحتوي على الحافة والذي يحتوي على نقاط المضلع في جوار أي نقطة داخلية للحافة. نواة المضلع هي تقاطع جميع المستويات النصفية الداخلية. يمكن العثور على تقاطع مجموعة عشوائية من أنصاف المستويات N في زمن Θ (N log N) باستخدام خوارزمية فرق تسد. ومع ذلك، بالنسبة لحالة نواة المضلعات، يمكن استخدام طريقة أسرع: قدم لي وبوراتا (1979) خوارزمية لبناء النواة في الوقت الخطي.[2] التطبيقاتيعتبر المضلع نجمي الشكل ذو أهمية في الهندسة الحسابية وتطبيقاتها، مثل تخطيط الحركة، بسبب العلاقة بين المضلع نجمي الشكل ومفهوم الرؤية: يمكن تعريف المضلع نجمي الشكل بشكل غير رسمي على أنه المضلع، الذ يكون الجزء الداخلي بأكمله مرئيًا من نقطة واحدة، إذا افترضنا أن حدود المضلع ليست شفافة. مراجع
 في كومنز مواد ذات صلة بـ مضلع نجمي الشكل. |
