التضليع

في الهندسة الحسابية ، يُعرف تحويل مجموعة محدودة من النقاط في المستوى الإقليدي إلى مضلع بأنه مضلع بسيط رؤوسه هي تلك النقاط. ^{[ 1 ]} ويُطلق على هذا التحويل أيضًا اسم تحويل مضلعي ، ^{[ 2 ]} أو تحويل مضلعي بسيط ، ^{[ 3 ]} أو مضلع هاميلتوني ، ^{[ 4 ]} أو دورة هاميلتونية غير متقاطعة ، ^{[ 5 ]} أو دورة ممتدة ذات حواف مستقيمة خالية من التقاطعات . ^{[ 6 ]}

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

المضلع هو مضلع بسيط له مجموعة معينة من النقاط في المستوى الإقليدي تمثل رؤوسه. يمكن وصف المضلع بترتيب دوري لرؤوسه، حيث تتصل هذه الرؤوس في أزواج متتالية بقطع مستقيمة، وهي أضلاع المضلع. يكون المضلع، وفقًا لهذا التعريف، "بسيطًا" إذا كانت نقاط التقاطع الوحيدة لهذه القطع المستقيمة هي نقاط مشتركة. ^{[ 2 ]}

يقتصر بعض المؤلفين على دراسة تحويل النقاط إلى مضلعات في مواقع عامة ، أي لا تقع أي ثلاث نقاط على خط مستقيم. ^{[ 7 ]} وبناءً على هذا الافتراض، لا يمكن أن تكون الزاوية بين أي قطعتين متتاليتين من المضلع 180 درجة. مع ذلك، عند دراسة مجموعات النقاط ذات الاستقامة الخطية، يُسمح عمومًا بأن تكون زوايا تحويلها إلى مضلعات 180 درجة عند بعض النقاط. في هذه الحالة، تُعتبر هذه النقاط رؤوسًا، وليست نقاطًا داخلية للأضلاع. ^{[ 8 ]}

لاحظ شتاينهاوس (1964) أن كل مجموعة نقاط منتهية لا تقع ثلاث نقاط منها على خط مستقيم تُشكّل رؤوس مضلع بسيط. ^{[ 10 ]} مع ذلك، فإن اشتراط عدم وقوع ثلاث نقاط على خط مستقيم يُعدّ شرطًا مُبالغًا فيه. بدلًا من ذلك، كل ما هو مطلوب لوجود مضلع (مع السماح بزوايا 180 درجة) هو ألا تقع جميع النقاط على خط مستقيم واحد. إذا لم تقع جميعها على خط مستقيم واحد، فإنه يُمكن إنشاء مضلع لها في وقت متعدد الحدود . إحدى طرق إنشاء المضلع هي اختيار أي نقطة.${\displaystyle q}$في الغلاف المحدب لـ${\displaystyle P}$(ليس بالضرورة إحدى النقاط المعطاة). ثم ترتيب النقاط شعاعيًا حول${\displaystyle q}$(بكسر التعادلات حسب المسافة من q) ينتج الترتيب الدوري لمضلع على شكل نجمة يمر بجميع النقاط المعطاة، مع${\displaystyle q}$في نواتها. ^{[ 7 ]} تُستخدم نفس فكرة فرز النقاط شعاعيًا حول نقطة مركزية في بعض إصدارات خوارزمية غراهام للمسح المحدب، ويمكن تنفيذها في${\displaystyle O(n\log n)}$^{[ 11 ]} لا توجد دائمًا أشكال مضلعة تتجنب الزوايا 180 درجة. على سبيل المثال، بالنسبة للشبكات المربعة 3 × 3 و 5 × 5 ، تستخدم جميع الأشكال المضلعة زوايا 180 درجة. ^{[ 9 ]}

إلى جانب المضلعات النجمية الشكل، فإن كل مجموعة نقاط غير متوازية لها مضلع رتيب . وهذا يعني أنه بالنسبة لخط مستقيم ما (والذي يمكن اعتباره...${\displaystyle x}$(المحور -) يتقاطع كل خط عمودي على خط المرجع مع المضلع في فاصل زمني واحد، أو لا يتقاطع معه على الإطلاق. يبدأ بناء غرونباوم (1994) بفرز النقاط حسب موقعها${\displaystyle x}$باستخدام الإحداثيات، ورسم خط يمر بنقطتيها القصوى. ولأن النقاط لا تقع جميعها على خط مستقيم، فلا بد أن يكون أحد نصفي المستوي المفتوحين المحددين بهذا الخط غير فارغ. تُنشئ طريقة غرونباوم سلسلتين مضلعيتين رتيبتين تربطان النقطتين القصوى عبر متواليات فرعية مُرتبة من النقاط: إحداهما للنقاط الموجودة في نصف المستوى المفتوح غير الفارغ، والأخرى للنقاط المتبقية. اتحادهما هو المضلع الرتيب المطلوب. بعد خطوة الترتيب، يمكن إتمام باقي عملية الإنشاء في زمن خطي . ^{[ 4 ]}

يُعدّ تحديد ما إذا كانت مجموعة من النقاط تمتلك شكلًا مضلعًا باستخدام الحواف الموازية للمحاور فقط مسألةً كاملةً من نوع NP . ^{[ 12 ]} مع ذلك، فإنّ الأشكال المضلعة التي تتضمن قيدًا إضافيًا يتمثل في الانعطاف يمينًا عند كل رأس، إن وُجدت، تُحدّد بشكلٍ فريد. يجب أن يمر كل خط موازٍ للمحور يمر بنقطة ما عبر عدد زوجي من النقاط، ويجب أن يربط هذا الشكل المضلع أزواجًا متناوبة من النقاط على هذا الخط. يمكن إيجاد الشكل المضلع في زمن .${\displaystyle O(n\log n)}$عن طريق تجميع النقاط حسب الإحداثيات المتساوية وفرز كل مجموعة حسب الإحداثي الآخر. ^{[ 13 ]} بالنسبة لأي مجموعة نقاط، يمكن أن يكون لدوران واحد على الأكثر شكل مضلع من هذا النوع، ويمكن إيجاد هذا الدوران مرة أخرى في وقت متعدد الحدود. ^{[ 14 ]}

غالبًا ما تكون مسائل إيجاد المضلع الأمثل (لمعايير مثالية مختلفة) غير قابلة للحل حسابيًا. على سبيل المثال، لا يحتوي حل مسألة البائع المتجول ، بالنسبة للنقاط المعطاة، على أي تقاطعات. لذلك، فهو دائمًا مضلع ذو محيط أدنى . ^{[ 15 ]} وهو من المسائل الصعبة حسابيًا (NP-hard ). وبالمثل، من المعروف أن إيجاد المضلع البسيط ذي المساحة الدنيا أو القصوى من المسائل الصعبة حسابيًا (NP-hard)، ^{[ 3 ]} وقد كان موضوعًا لبعض الجهود الحسابية. ^{[ 16 ] [ 17 ]} دائمًا ما تكون المساحة القصوى أكبر من نصف مساحة الغلاف المحدب ، مما يعطي نسبة تقريب تبلغ 2. ^{[ 18 ]} لا يزال التعقيد الدقيق للمضلع البسيط ذي المحيط الأقصى، ووجود نسبة تقريب ثابتة لهذه المسألة، غير معروفين. ^{[ 5 ]} إن إيجاد المضلع الذي يقلل طول أطول ضلع فيه هو أيضًا مسألة صعبة من نوع NP، ويصعب تقريبه بنسبة تقريب أفضل من${\displaystyle {\sqrt {3}}}$لا توجد تقريبية ذات عامل ثابت معروفة. ^{[ 19 ]}

قد يحتوي الحل غير الأمثل لمسألة البائع المتجول على نقاط تقاطع، ولكن من الممكن إزالة جميع نقاط التقاطع من خلال خطوات تحسين محلية تقلل الطول الإجمالي. باستخدام خطوات تُزيل نقاط التقاطع في كل خطوة، يمكن إنجاز ذلك في وقت متعدد الحدود ، ^{[ 20 ]} ولكن بدون هذا القيد، توجد متواليات تحسين محلية تستخدم عددًا أُسّيًا من الخطوات. ^{[ 21 ]}

أقصر مسار ثنائي الاتجاه (المضلع الرتيب ذو المحيط الأدنى الذي يمر عبر النقاط المعطاة) هو دائمًا مضلع، ويمكن إيجاده في وقت متعدد الحدود. ^{[ 22 ]}

تُصنَّف مسألة حساب جميع أشكال المضلعات لمجموعة نقاط معينة ضمن فئة #P ، وهي فئة مسائل العد المرتبطة بمسائل القرار في NP . مع ذلك، لا يُعرف ما إذا كانت هذه المسألة كاملة في فئة #P ، أو إن لم تكن كذلك، فما هو تعقيدها الحسابي. ^{[ 23 ] [ 24 ]} تحتوي مجموعة من النقاط على شكل مضلع واحد فقط إذا وفقط إذا كانت في وضع محدب . ^{[ 1 ]} توجد مجموعات من${\displaystyle n}$النقاط التي يكون فيها عدد عمليات التضليع كبيرًا مثل${\displaystyle 4.64^{n}}$[ ^{25 ]} وكل مجموعة ^من${\displaystyle n}$النقاط لها على الأكثر${\displaystyle 54.6^{n}}$[ ^{6 ]​}

يمكن استخدام الطرق التي تطبق نظرية الفاصل المستوي على التثليثات المصنفة للنقاط لحساب جميع عمليات تحويل مجموعة من المضلعات${\displaystyle n}$نقاط في زمن شبه أسي،${\displaystyle n^{O({\sqrt {n}})}}$[ ^{26 ]} يمكن استخدام البرمجة الديناميكية لحساب جميع عمليات تحويل المضلعات الرتيبة في وقت متعدد الحدود، ويمكن بعد ذلك استخدام نتائج هذه العملية الحسابية لإنشاء عملية تحويل مضلعات رتيبة عشوائية ^{. [ 27 ]}

من غير المعروف ما إذا كان من الممكن لنظام جميع أشكال المضلعات أن يُشكّل فضاء حالة متصلًا عند إجراء حركات محلية تُغيّر عددًا محدودًا من حواف هذه الأشكال. إذا كان ذلك ممكنًا، فيمكن استخدامه كجزء من خوارزمية لتوليد جميع أشكال المضلعات، وذلك بتطبيق عملية اجتياز الرسم البياني على فضاء الحالة. في هذه المسألة، لا يكفي النظر في عمليات القلب التي تُزيل حافتين من شكل المضلع وتستبدلهما بحافتين أخريين، أو عمليات القلب الرأسي التي تُزيل ثلاث حواف، اثنتان منها تشتركان في رأس واحد، وتستبدلها بثلاث حواف أخرى. توجد أشكال مضلعة لا يُمكن إجراء أي قلب لها، سواءً كان قلبًا عاديًا أو قلبًا رأسيًا، حتى وإن كانت مجموعة النقاط نفسها تحتوي على أشكال مضلعة أخرى. ^{[ 28 ]}

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

تتضمن ألغاز توصيل النقاط الكلاسيكية توصيل النقاط بالتسلسل لتشكيل شكل غير متوقع، غالبًا دون تقاطعات. ^{[ 30 ]} ولمسألة البائع المتجول ومتغيراتها تطبيقات عديدة. ^{[ 31 ]} كما أن للتشكيل المضلعي تطبيقات في إعادة بناء خطوط الكفاف من نقاط البيانات المتناثرة، وفي تتبع الحدود في تحليل الصور . ^{[ 32 ]}

• نظرية دينجوي-ريز ، حول مجموعات من عدد لا نهائي من النقاط التي يمكن ربطها بقوس جوردان