الوضع المحدب

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

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

يمكن أن يُسهّل افتراض الموقع المحدب حلّ بعض المسائل الحسابية. على سبيل المثال، تُعدّ مسألة البائع المتجول ، وهي مسألة صعبة الحل (NP-hard) لأي مجموعة نقاط في المستوى، مسألةً بسيطةً بالنسبة للنقاط ذات الموقع المحدب: فالمسار الأمثل هو الغلاف المحدب. [ 3 ] وبالمثل، فإنّ مسألة التثليث بأقل وزن لمجموعات النقاط المستوية هي مسألة صعبة الحل (NP-hard) لأي مجموعة نقاط، [ 4 ] ولكن يمكن حلّها في وقت متعدد الحدود باستخدام البرمجة الديناميكية للنقاط ذات الموقع المحدب. [ 5 ]

تضمن نظرية Erdős-Szekeres أن كل مجموعة منن{\displaystyle n}تحتوي النقاط في الوضع العام (لا توجد ثلاث نقاط في خط مستقيم) في بعدين أو أكثر على عدد لوغاريتمي على الأقل من النقاط في الوضع المحدب. [ 6 ] إذان{\displaystyle n}يتم اختيار النقاط بشكل عشوائي منتظم في مربع وحدة ، واحتمالية وجودها في وضع محدب هي [ 7 ].((2ن-2ن-1)/ن!)2.{\displaystyle \left({\binom {2n-2}{n-1}}/n!\right)^{2}.}

تطلب مسألة ماكمولين إيجاد العدد الأقصىν(د){\displaystyle \nu (d)}بحيث أن كل مجموعة منν(د){\displaystyle \nu (d)}النقاط في الموقع العام فيد{\displaystyle d}للفضاء الإسقاطي ذي الأبعاد n تحويل إسقاطي إلى مجموعة في وضع محدب. الحدود المعروفة هي2د+1≤ν(د)≤2د+⌈(د+1)/2⌉{\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }[ 8 ]​

مراجع

  1. 1 2 ماتوسيك، جيري (2002)، محاضرات في الهندسة المنفصلة ، ​​نصوص الدراسات العليا في الرياضيات ، Springer-Verlag، ص.  30، ردمك 978-0-387-95373-1
  2. ↑ توث، جيزا؛ فالتر، بافيل (2005)، "نظرية إردوش-سيكيريس: حدود عليا ونتائج ذات صلة"، الهندسة التوافقية والحسابية ، منشورات معهد أبحاث العلوم الرياضية، المجلد 52، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 557-568 ، MR 2178339   
  3. ↑ دينيكو، فلاديمير ج.؛ هوفمان، مايكل؛ أوكاموتو، يوشيو؛ ووجينجر، جيرهارد ج. (2006)، "مسألة البائع المتجول مع عدد قليل من النقاط الداخلية"، رسائل بحوث العمليات ، 34 (1): 106-110 ، doi : 10.1016/j.orl.2005.01.002 ، MR 2186082 
  4. ↑ مولزر، فولفغانغ؛ روت، غونتر (2008)، "التثليث ذو الوزن الأدنى هو مسألة صعبة من نوع NP"، مجلة ACM ، 55 (2)، المقالة A11، arXiv : cs.CG/0601002 ، doi : 10.1145/1346330.1346336
  5. ↑ كلينسيك، جي تي (1980)، "التثليثات الدنيا للمجالات المضلعة"، في هامر، بيتر إل (محرر)، التوافقية 79 ، حوليات الرياضيات المتقطعة، المجلد 9، الصفحات 121-123 ، doi : 10.1016/s0167-5060(08)70044-x ، ISBN   9780444861115
  6. ^ اردوس، بول ؛ Szekeres، George (1935)، “مشكلة اندماجية في الهندسة” ، Compositio Mathematica ، 2 : 463– 470
  7. ↑ فالتر، ب. (1995)، "احتمالية وجود n نقطة عشوائية في وضع محدب"، الهندسة المنفصلة والحسابية ، 13 ( 3-4 ): 637-643 ، doi : 10.1007/BF02574070 ، MR 1318803 
  8. ↑ فورج، ديفيد؛ لاس فيرغناس، ميشيل ؛ شوخرت، بيتر (2001)، "10 نقاط في البعد 4 غير مكافئة إسقاطيًا لرؤوس متعدد السطوح المحدب"، الهندسة التوافقية (لوميني، 1999)، المجلة الأوروبية للتوافقية ، 22 (5): 705-708 ، doi : 10.1006/eujc.2000.0490 ، MR 1845494