مضلع نجمي الشكل
المضلع نجمي الشكل (بالإنجليزية: Star-shaped polygon) هو منطقة مضلع في المستوى تمثل مجالًا نجميًا، أي مضلع يحتوي على نقطة يمكن من خلالها رؤية حدود المضلع بالكامل.
يكون المضلع P على شكل نجمة إذا كانت هناك نقطة z لكل نقطة p من P بحيث يقع الجزء zp بالكامل داخل P.[1] تسمى مجموعة النقاط z بهذه الخاصية نواة P.
إذا كان المضلع على شكل نجمة محدبًا، فإن مسافة الارتباط بين أي نقطتين من نقاطه (الحد الأدنى لعدد مقاطع الخط المتسلسلة الكافية لربط هذه النقاط) هي 1، وبالتالي فإن قطر ارتباط المضلع (أقصى مسافة ارتباط على جميع أزواج النقاط) هي 1. إذا لم يكن مضلع على شكل نجمة محدبًا، فإن مسافة الارتباط بين نقطة في النواة وأي نقطة أخرى في المضلع هي 1، بينما مسافة الارتباط بين أي نقطتين في المضلع ولكن خارج النواة هي إما 1 أو 2؛ في هذه الحالة، تكون مسافة الارتباط القصوى 2.
أمثلة
عدل- المضلعات المحدبة على شكل نجمة، ويتزامن المضلع المحدب مع النواة الخاصة به.
- المضلعات النجمية المنتظمة هي على شكل نجمة، ومركزها دائمًا في النواة.
- ضد متوازي أضلاع ومسدسات ليموين ذاتية التقاطع هي على شكل نجمة، وتتكون النواة من نقطة واحدة.
- مضلعات الرؤية تكون على شكل نجمة حيث يجب أن تكون كل نقطة بداخلها مرئية للمركز بحكم التعريف.
الخوارزمية
عدلاختبار ما إذا كان المضلع نجمي الشكل، وإيجاد نقطة واحدة في النواة، يمكن حلها في تعقيد الوقت عن طريق صياغة المشكلة كبرنامج خطي وتطبيق تقنيات للبرمجة الخطية منخفضة الأبعاد.
تحدد كل حافة من مضلع نصف مستوى داخلي، نصف المستوى الذي تقع حدوده على الخط الذي يحتوي على الحافة والذي يحتوي على نقاط المضلع في جوار أي نقطة داخلية للحافة. نواة المضلع هي تقاطع جميع المستويات النصفية الداخلية. يمكن العثور على تقاطع مجموعة عشوائية من أنصاف المستويات N في زمن Θ (N log N) باستخدام خوارزمية فرق تسد. ومع ذلك، بالنسبة لحالة نواة المضلعات، يمكن استخدام طريقة أسرع: قدم لي وبوراتا (1979) خوارزمية لبناء النواة في الوقت الخطي.[2]
التطبيقات
عدليعتبر المضلع نجمي الشكل ذو أهمية في الهندسة الحسابية وتطبيقاتها، مثل تخطيط الحركة، بسبب العلاقة بين المضلع نجمي الشكل ومفهوم الرؤية: يمكن تعريف المضلع نجمي الشكل بشكل غير رسمي على أنه المضلع، الذ يكون الجزء الداخلي بأكمله مرئيًا من نقطة واحدة، إذا افترضنا أن حدود المضلع ليست شفافة.
مراجع
عدل- ^ Franco P. (1985). Computational geometry : an introduction. New York: Springer-Verlag. ISBN:0-387-96131-3. OCLC:11970840. مؤرشف من الأصل في 2017-02-02.
- ^ Lee, D. T.; Preparata, F. P. (July 1979), "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM, 26 (3): 415–421, doi:10.1145/322139.322142, hdl:2142/74090, S2CID 6156190
