تقسيم متعدد الأضلاع

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

في الهندسة ، يُعرَّف تقسيم المضلع بأنه مجموعة من الوحدات الأولية (مثل المثلثات والمستطيلات وغيرها) التي لا تتداخل، ويكون اتحادها مساوياً للمضلع. وتكمن مشكلة تقسيم المضلع في إيجاد تقسيم يكون أصغر ما يمكن، كأن يكون التقسيم بأقل عدد من الوحدات أو بوحدات ذات أقصر مجموع أطوال أضلاع (مجموع محيطات).

يُعدّ تقسيم المضلعات فئةً مهمةً من المسائل في الهندسة الحسابية . وتوجد العديد من مسائل تقسيم المضلعات المختلفة، وذلك تبعاً لنوع المضلع المراد تقسيمه وأنواع الوحدات المسموح بها في التقسيم.

يُستخدم مصطلح " تجزئة المضلعات " غالبًا كمصطلح عام يشمل كلًا من تقسيم المضلعات وتغطية المضلعات ، مما يسمح بتداخل الوحدات. [ 1 ]

التطبيقات

يتم تطبيق تجزئة المضلعات في عدة مجالات: [ 1 ]

  • تستخلص تقنيات التعرف على الأنماط المعلومات من جسم ما لوصفه أو تحديده أو تصنيفه. وتتمثل إحدى الاستراتيجيات الراسخة للتعرف على جسم متعدد الأضلاع في تقسيمه إلى مكونات أبسط، ثم تحديد هذه المكونات وعلاقاتها المتبادلة، واستخدام هذه المعلومات لتحديد شكل الجسم.
  • في معالجة بيانات تصميم الدوائر المتكاملة واسعة النطاق (VLSI) ، تُمثَّل التخطيطات على شكل مضلعات، وإحدى طرق التحضير للطباعة الحجرية باستخدام حزمة الإلكترونات هي تقسيم هذه المناطق المضلعة إلى أشكال أساسية. كما يُستخدم تقسيم المضلعات في عملية تقسيم منطقة التوجيه إلى قنوات.
  • في الهندسة الحسابية ، غالبًا ما تكون خوارزميات حل مسائل المضلعات العامة أكثر تعقيدًا من تلك الخاصة بأنواع محددة من المضلعات، مثل المضلعات المحدبة أو النجمية. تُعد مسألة تحديد نقطة داخل مضلع مثالًا على ذلك. تتمثل إحدى استراتيجيات حل بعض هذه المسائل على المضلعات العامة في تقسيم المضلع إلى أجزاء بسيطة، ثم حل المسألة على كل جزء باستخدام خوارزمية متخصصة، ثم دمج الحلول الجزئية.
  • وتشمل التطبيقات الأخرى ضغط البيانات ، وأنظمة قواعد البيانات ، ومعالجة الصور ، ورسومات الحاسوب .

تقسيم المضلع إلى مثلثات

تُعدّ مسألة تقسيم المضلعات إلى أقل عدد ممكن من المثلثات، والتي تُسمى أيضًا بالتثليث ، من أكثر مسائل تقسيم المضلعات دراسةً . بالنسبة لمضلع خالٍ من الثقوب معن{\displaystyle n}يمكن حساب التثليث باستخدام الرؤوس في وقتΘ(ن){\displaystyle \Theta (n)}بالنسبة للمضلع ذي الثقوب ، يوجد حد أدنى لـΩ(نسجل⁡ن){\displaystyle \Omega (n\log n)}.

تتمثل إحدى المشكلات ذات الصلة في تقسيم المثلثات إلى مثلثات ذات طول إجمالي أدنى للحواف، وتسمى أيضًا التثليث ذو الوزن الأدنى .

تقسيم المضلع إلى مثلثات زائفة

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

تقسيم مضلع مستطيل إلى مستطيلات

تنشأ فئة فرعية مهمة من مسائل تقسيم المضلعات عندما يكون المضلع الكبير مستطيلاً ، والهدف هو تقسيمه إلى مستطيلات. [ 1 ] تُعرف هذه التقسيمات بالتقسيمات المستطيلة . ولها تطبيقات عملية في مجالات متنوعة، بما في ذلك تصميم الدوائر المتكاملة واسعة النطاق (VLSI) ومعالجة الصور . [ 2 ]

تقليل عدد المكونات

توجد عدة خوارزميات ذات زمن حسابي متعدد الحدود لحساب تقسيم مستطيل يقلل من عدد المستطيلات المكونة له. انظر [ 1 ] : 10-13 و [ 2 ] : 3-5 للاطلاع على الدراسات الاستقصائية.

تُعد مشكلة تقسيم المضلع المستقيم إلى أصغر عدد من المربعات (بدلاً من المستطيلات العشوائية) مشكلة صعبة من نوع NP . [ 3 ]

تقليل طول الحافة الكلي

في بعض التطبيقات، يكون تقليل الطول الإجمالي للقطع أكثر أهمية (على سبيل المثال، لتقليل تكلفة إجراء التقسيم، أو لتقليل كمية الغبار). تُسمى هذه المسألة بتقسيم المستطيل ذي الحد الأدنى لطول الحافة . ​​وقد دُرست لأول مرة من قِبل لينغاس، وبينتر، وريفست، وشامير في عام 1982. [ 4 ] [ 5 ] يعتمد تعقيد وقت تشغيل هذه المسألة بشكل حاسم على ما إذا كان يُسمح للمضلع الأصلي بوجود ثقوب.

إذا كان المضلع الخام خالياً من الثقوب ، فإنه يمكن إيجاد تقسيم أمثل في وقتيا(ن4){\displaystyle O(n^{4})}حيث n هو عدد رؤوس المضلع. في الحالة الخاصة لـ " مضلع المدرج التكراري "، يتحسن التعقيد إلىيا(ن3){\displaystyle O(n^{3})}[ 4 ] تستخدم الخوارزمية البرمجة الديناميكية وتعتمد على الحقيقة التالية: إذا كان المضلع خاليًا من الثقوب، فإنه يحتوي على تجزئة ذات طول أدنى بحيث تحتوي كل قطعة مستقيمة قصوى على رأس من رؤوس الحدود. والسبب هو أنه في أي تجزئة ذات طول أدنى، يمكن "دفع" كل قطعة مستقيمة قصوى حتى تصل إلى أحد رؤوس الحدود، دون تغيير الطول الإجمالي. لذلك، لا يوجد سوىيا(ن2){\displaystyle O(n^{2})}يمكن تحديد المرشحين لقطعة مستقيمة في التقسيم الأمثل، ويمكن التحقق منهم بكفاءة باستخدام البرمجة الديناميكية. [ 5 ] : 166-167

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

  • تقريب زمني (3+√3))يا(ن2){\displaystyle O(n^{2})}; [ 6 ]
  • تقريب زمني (3+√3))يا(نسجل⁡ن){\displaystyle O(n\log {n})}; [ 7 ]
  • تقريب زمني من الدرجة الرابعةيا(نسجل⁡ن){\displaystyle O(n\log {n})}(بشكل عام، في الأبعاد d ، هو2د{\displaystyle 2d}التقريب في الزمنيا(دنسجل⁡ن){\displaystyle O(dn\log {n})}), [ 8 ]
  • تقريب زمني من الدرجة الثالثةيا(ن4){\displaystyle O(n^{4})}؛
  • تقريب زمني قدره 1.75يا(ن5){\displaystyle O(n^{5})}(بشكل عام، في الأبعاد d ، هو2د-4+4/د{\displaystyle 2d-4+4/d}التقريب في الزمنيا(دن2د+1){\displaystyle O(dn^{2d+1})}); [ 9 ] يستخدم التقريب الأخير شكلاً مقيدًا من المشكلة يسمى تقسيم المقصلة ، حيث يجب أن تكون القطع قطع المقصلة (قطع من الحافة إلى الحافة).
  • تتضمن هذه الدراسة عدة مخططات تقريبية متعددة الحدود باستخدام عمليات قطع المقصلة المتطورة. [ 10 ] [ 11 ] [ 5 ]

تقليل عدد الفراغات

في هذا السياق، يحتوي المضلع الكبير بالفعل على بعض المستطيلات المنفصلة. الهدف هو إيجاد تقسيم للمضلع إلى مستطيلات بحيث يحتوي كل جزء على مستطيل أصلي، مع مراعاة أن يكون عدد "الفراغات" (الأجزاء التي لا تحتوي على مستطيل أصلي) في أدنى حد ممكن. النتائج التالية معروفة: [ 12 ]

  • إذا كان المضلع الكبير مستطيلاً، ففي أي ترتيب أقصى مكون من n مستطيلاً، تكون جميع الثقوب مستطيلات، ويكون عددها على الأكثرن-⌈2ن-1⌉{\displaystyle n-\lceil 2{\sqrt {n}}-1\rceil }وهذا ضيق.
  • إذا كان المضلع الكبير مضلعًا مستقيمًا له T رأسًا منعكسة، فإنه في أي ترتيب أقصى لـ n مستطيلًا، يمكن تقسيم الثقوب إلى عدد أقصى منتي+ن-⌈2ن-1⌉{\displaystyle T+n-\lceil 2{\sqrt {n}}-1\rceil }المستطيلات، وهذا ضيق.

قسّم المضلع إلى أشباه منحرفات

في أنظمة معالجة الرسومات في الدوائر المتكاملة واسعة النطاق (VLSI)، غالبًا ما يكون من الضروري تقسيم منطقة مضلعة إلى أقل عدد ممكن من أشباه المنحرفات ذات ضلعين أفقيين. يُعتبر المثلث ذو الضلع الأفقي شبه منحرف ذو ضلعين أفقيين، أحدهما منعدم. بالنسبة لمضلع خالٍ من الثقوب معن{\displaystyle n}من الجوانب، يمكن إيجاد أصغر تقسيم من هذا القبيل في الوقتيا(ن2){\displaystyle O(n^{2})}[ 13 ]​

إذا لم يكن عدد أشباه المنحرفات بالضرورة ضئيلاً، فيمكن إيجاد عملية تحويل إلى شبه منحرف في الوقت المناسب.يا(ن){\displaystyle O(n)}[ 14 ]​​​

إذا كان المضلع يحتوي على ثقوب، فإن المشكلة تُصنف ضمن فئة NP-complete، ولكن يمكن إيجاد تقريب من الدرجة 3 في وقتيا(نسجل⁡ن){\displaystyle O(n\log n)}[ 13 ]​

قسّم مضلعًا إلى أشكال رباعية محدبة

التربيع أو التثليث الرباعي هو تقسيم إلى أشكال رباعية .

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

توجد خوارزميات خطية الزمن لتقسيم المضلعات الخالية من الثقوب إلى رباعيات باستخدام نقاط شتاينر، لكنها لا تضمن إيجاد أصغر تقسيم. [ 15 ] [ 16 ]

قسّم مضلعًا إلى m ضلعًا

تتمثل إحدى تعميمات المسائل السابقة في تقسيم المضلعات إلى مضلعات ذات عدد m من الأضلاع بالضبط، أو على الأكثر m من الأضلاع. والهدف هنا هو تقليل إجمالي طول الأضلاع. يمكن حل هذه المسألة في وقت متعدد الحدود بالنسبة إلى n و m . [ 17 ] [ 18 ]

قسّم مضلعًا إلى مضلعات محدبة

عند تقسيم مضلع عام إلى مضلعات محدبة، تمت دراسة العديد من الأهداف.

تقليل عدد المكونات

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

تقليل عدد الفراغات

يحتوي المضلع الأصلي بالفعل على بعض الأشكال المحدبة المنفصلة، ​​والهدف هو تقسيمه إلى مضلعات محدبة بحيث يحتوي كل جزء منها على أحد الأشكال الأصلية، مع مراعاة أن يكون عدد "الفراغات" (الأجزاء التي لا تحتوي على شكل أصلي) أصغر ما يمكن. إذا كان المضلع الكبير محدبًا، ففي أي ترتيب أقصى لـ n شكل محدب، تكون جميع الثقوب محدبة، ويكون عددها على الأكثر2ن-5{\displaystyle 2n-5}وهذا ضيق. [ 12 ]

مساواة المساحة والمحيط

تتمثل مسألة تقسيم المضلع العادل [ 20 ] في تقسيم مضلع (محدب) إلى أجزاء (محدبة) متساوية في المحيط والمساحة (وهي حالة خاصة من مسألة تقطيع الكعكة العادل ). يمكن تقسيم أي مضلع محدب بسهولة إلى أي عدد n من الأجزاء المحدبة بمساحة تساوي 1/n بالضبط . ومع ذلك، فإن ضمان تساوي مساحة ومحيط الأجزاء يُعدّ أكثر صعوبة. توجد خوارزميات لحل هذه المسألة عندما يكون عدد الأجزاء قوة من قوى العدد 2. [ 21 ]

يتمثل أحد أشكال هذه المسألة في تعميمها عندما يتم استبدال قياسات المساحة والمحيط بقياس على جسم المضلع وعلى حدوده، على التوالي. وقد دُرست هذه المسألة في حالتي وجود قطعتين وثلاث قطع. [ 22 ]

وهناك تعميم إضافي للتعامل مع أي عدد من التدابير.

أشكال المكونات الأكثر عمومية

تمت دراسة أشكال أكثر عمومية للقطع، بما في ذلك: الأشكال الحلزونية ، والمضلعات النجمية ، والمضلعات الرتيبة . انظر [ 1 ] للاطلاع على دراسة شاملة.

انظر أيضاً

مراجع

  1. 1 2 3 4 5 مارك كيل، ج. (2000). "تحليل المضلعات". دليل الهندسة الحسابية . ص 491-518 . doi : 10.1016/B978-044482537-7/50012-7 . ISBN  9780444825377.
  2. 1 2 إبستين، ديفيد (2010). "حلول نظرية الرسم البياني لمسائل الهندسة الحسابية". مفاهيم نظرية الرسم البياني في علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 5911. الصفحات 1-16 . CiteSeerX 10.1.1.249.5965 . doi : 10.1007/978-3-642-11409-0_1 . ISBN    978-3-642-11408-3. S2CID 16353114 . 
  3. ↑ ريلز سلاو. "تبليط مضلع متعامد بالمربعات" . موقع تبادل المعلومات في علوم الحاسوب . تم الاطلاع عليه بتاريخ 19 أكتوبر 2015 .
  4. 1 2 3 أندريه لينغاس ورون واي بينتر ورون إل ريفست وآدي شامير (1982). "تقسيم المضلعات المستقيمة إلى أطوال حواف دنيا" (ملف PDF) . وقائع المؤتمر العشرين لأليرتون للاتصالات والتحكم والحوسبة : 53-63 .
  5. 1 2 3 دو، دينغ-تشو؛ كو، كير-آي؛ هو، شياودونغ (2012). تصميم وتحليل خوارزميات التقريب . سبرينغر: التحسين وتطبيقاته. نيويورك: سبرينغر-فيرلاغ. ص 165-209 . doi : 10.1007/978-1-4614-1701-9_5 . ISBN  978-1-4614-1700-2.
  6. 1 2 غونزاليس، تيوفيلو؛ تشنغ، سي-تشينغ (1985-06-01). "حدود تقسيم المضلعات المستقيمة" . وقائع الندوة السنوية الأولى حول الهندسة الحسابية - SCG '85 . بالتيمور، ماريلاند، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. ص 281-287 . doi : 10.1145/323233.323269 . ISBN  978-0-89791-163-4. S2CID 12588297 . 
  7. ↑ ليفكوبولوس، سي (1986-08-01). "طرق استدلالية سريعة لتقسيم المضلعات إلى أجزاء مستطيلة بأقصر طول". وقائع الندوة السنوية الثانية حول الهندسة الحسابية - SCG '86 . يوركتاون هايتس، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 100-108 . doi : 10.1145/10515.10526 . ISBN  978-0-89791-194-8. S2CID 16106423 . 
  8. ↑ غونزاليس، تيوفيلو ف.؛ رزازي، محمد رضا؛ تشنغ، سي تشينغ (1993-12-01). "خوارزمية تقريبية فعالة لتقسيم البيانات إلى مربعات ذات أبعاد d باستخدام أسلوب فرق تسد" . المجلة الدولية للهندسة الحسابية وتطبيقاتها . 3 (4): 417-428 . doi : 10.1142/S0218195993000269 . ISSN 0218-1959 . 
  9. ↑ غونزاليس، تيوفيلو؛ تشنغ، سي-تشينغ (1989-06-01). "حدود محسّنة للتقسيمات المستطيلة والمقصلة" . مجلة الحساب الرمزي . 7 (6): 591-610 . doi : 10.1016/S0747-7171(89)80042-2 . ISSN 0747-7171 . 
  10. ↑ أرورا، س. (أكتوبر 1996). "مخططات تقريبية متعددة الحدود لمسألة البائع المتجول الإقليدية وغيرها من المسائل الهندسية". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . ص 2-11 . doi : 10.1109/SFCS.1996.548458 . ISBN  0-8186-7594-2. S2CID 1499391 . 
  11. ↑ ميتشل، جوزيف إس بي (1999-01-01). "تقسيمات المقصلة تقارب التقسيمات المضلعية: مخطط تقريبي بسيط ذو زمن متعدد الحدود لمسائل البائع المتجول الهندسية، ومسألة الشجرة الممتدة الدنيا k، والمسائل ذات الصلة" . مجلة SIAM للحوسبة . 28 (4): 1298-1309 . doi : 10.1137/S0097539796309764 . ISSN 0097-5397 . 
  12. 1 2 أكوبيان، أرسيني؛ سيغال هاليفي ، إيريل (2018/01/01). "عد الفراغات في الترتيبات المضلعة" . مجلة SIAM للرياضيات المنفصلة . 32 (3): 2242– 2257. أرخايف : 1604.00960 . دوى : 10.1137/16M110407X . ISSN 0895-4801 . S2CID 123397485 .  
  13. 1 2 أسانو، تاكاو؛ أسانو، تيتسو؛ إيماي، هيروشي (1986). "تقسيم منطقة مضلعة إلى أشباه منحرفات". مجلة ACM . 33 (2): 290. doi : 10.1145/5383.5387 . hdl : 2433/98478 . S2CID 15296037 . 
  14. ↑ شازيل، برنارد (2007). "تثليث مضلع بسيط في زمن خطي" . الهندسة المنفصلة والحسابية . 6 (3): 485-524 . doi : 10.1007/bf02574703 .
  15. ↑ هـ. إيفريت؛ و. لينارت؛ م. أوفرمارس؛ ت. شيرمر؛ ج. أوروتيا. (1992). "تحويلات رباعية محدبة تمامًا للمضلعات" (ملف PDF) . وقائع المؤتمر الكندي الرابع للهندسة الحاسوبية . الصفحات 77-83 . 
  16. ↑ راماسوامي، سونيتا؛ راموس، بيدرو؛ توسان، غودفريد (1998). "تحويل المثلثات إلى رباعيات" . الهندسة الحسابية . 9 (4): 257. doi : 10.1016/s0925-7721(97)00019-9 .
  17. ↑ لينغاس، أندريه؛ ليفكوبولوس، كريستوس؛ ساك، يورغ (1987). "خوارزميات لتقسيم المضلعات إلى أجزاء ذات طول أدنى". مجلة BIT للرياضيات العددية . 27 (4): 474. doi : 10.1007/bf01937272 . S2CID 30936524 . 
  18. ↑ ليفكوبولوس، كريستوس؛ لينغاس، أندريه؛ ساك، يورغ-ر. (1989). "طرق استدلالية لأشجار البحث الثنائية المثلى ومسائل التثليث ذات الوزن الأدنى" . علوم الحاسوب النظرية . 66 (2): 181. doi : 10.1016/0304-3975(89)90134-5 .
  19. ↑ هيرتل، ستيفان؛ ميلهورن، كورت (1983). "التثليث السريع للمضلعات البسيطة" . في كاربينسكي، ماريك (محرر). أسس نظرية الحوسبة . سلسلة محاضرات في علوم الحاسوب. المجلد 158. برلين، هايدلبرغ: سبرينغر. الصفحات 207-218 . doi : 10.1007/3-540-12689-9_105 . ISBN   978-3-540-38682-7.
  20. ^ نانداكومار، ر. راو، ن. رامانا (أغسطس 2012). ""تقسيمات "عادلة" للمضلعات - مقدمة". وقائع - العلوم الرياضية . 122 (3): 459-467 . arXiv : 0812.2241 . doi : 10.1007/s12044-012-0076-5 . ISSN 0253-4142 . S2CID 189909962 .  
  21. ↑ أرماسيلو، بوغدان؛ دايسكو، أوفيديو (23-11-2015). "خوارزميات للتقسيم العادل للمضلعات المحدبة" . علوم الحاسوب النظرية . 607 : 351-362 . doi : 10.1016/j.tcs.2015.08.003 . ISSN 0304-3975 . 
  22. ↑ بيسبامياتنيخ، سيرجي (2003). "حول تقسيم الكعكة". في: أكياما، جين؛ كانو، ميكيو (محرران). الهندسة المنفصلة والحسابية: المؤتمر الياباني، JCDCG 2002، طوكيو، اليابان، 6-9 ديسمبر 2002، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد 2866. برلين، هايدلبرغ: سبرينغر. الصفحات 60-71 . doi : 10.1007/978-3-540-44400-8_7 . ISBN   978-3-540-44400-8.