التثليث ديلاوناي

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

سُميت عملية التثليث نسبة إلى بوريس ديلوناي لعمله عليها منذ عام 1934. ^{[ 2 ]}

إذا كانت جميع النقاط تقع على خط مستقيم، يصبح مفهوم التثليث غير دقيق ، ولا يوجد تثليث ديلاوناي. أما بالنسبة لأربع نقاط أو أكثر على نفس الدائرة (مثل رؤوس المستطيل)، فإن تثليث ديلاوناي ليس فريدًا: فكل من التثليثين الممكنين اللذين يقسمان الشكل الرباعي إلى مثلثين يحقق "شرط ديلاوناي"، أي الشرط الذي ينص على أن الدوائر المحيطة بجميع المثلثات تكون فارغة من الداخل.

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

العلاقة مع مخطط فورونوي

التثليث ديلاوناي مع جميع الدوائر المحيطة ومراكزها (باللون الأحمر).

يؤدي توصيل مراكز الدوائر المحيطة إلى إنتاج مخطط فورونوي (باللون الأحمر).

يُقابل تثليث ديلاوناي لمجموعة نقاط منفصلة $P$ في الوضع العام الرسم البياني الثنائي لمخطط فورونوي الخاص بـ $P.$ وتُمثل مراكز الدوائر المحيطة لمثلثات ديلاوناي رؤوس مخطط فورونوي. في الحالة ثنائية الأبعاد، تتصل رؤوس فورونوي عبر حواف يمكن استنتاجها من علاقات التجاور لمثلثات ديلاوناي: إذا اشترك مثلثان في حافة في تثليث ديلاوناي، فيجب توصيل مراكز دوائرهما المحيطة بحافة في تبليط فورونوي.

تشمل الحالات الخاصة التي لا تنطبق عليها هذه العلاقة، أو التي تكون غامضة، حالات مثل:

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

ديلاوناي ذو الأبعاد د

بالنسبة لمجموعة $P$ من النقاط في الفضاء الإقليدي ذي البعد $d$ ، فإن التثليث الدلوناي هو تثليث $DT($ $P$ $)$ بحيث لا تقع أي نقطة في $P$ داخل الكرة الفائقة المحيطة بأي مُجَسَّم بسيط ذي البعد d $في$ DT $($ $P$ $)$ . من المعروف ^[²^] أنه يوجد تثليث دلوناي وحيد لـ $P$ إذا كانت $P$ مجموعة نقاط في وضع عام ؛ أي أن الغلاف الأفيني لـ $P$ ذو بعد $d$ ، ولا تقع أي مجموعة من $d$ $+ 2$ نقطة في $P$ على حدود كرة لا يتقاطع باطنها مع $P.$

يمكن تحويل مسألة إيجاد تثليث ديلاوناي لمجموعة من النقاط في فضاء إقليدي ذي بُعد $d$ إلى مسألة إيجاد الغلاف المحدب لمجموعة من النقاط في فضاء ذي بُعد ( $d$ $+ 1$ ). يُمكن تحقيق ذلك بإعطاء كل نقطة $p$ إحداثية إضافية تساوي $|$ $p$ $|$ $²$ ، ما يحولها إلى سطح مكافئ فائق (يُسمى هذا "الرفع")؛ ثم أخذ الجانب السفلي من الغلاف المحدب (لأن الغطاء العلوي مُتجه للأعلى بعيدًا عن نقطة الأصل، ويجب استبعاده)؛ ثم إعادة إسقاطه إلى الفضاء ذي البُعد $d$ بحذف الإحداثية الأخيرة. بما أن الغلاف المحدب فريد، فإن التثليث كذلك، بافتراض أن جميع أوجه الغلاف المحدب عبارة عن مُجسمات بسيطة . لا تظهر الأوجه غير البسيطة إلا عندما تقع $d$ $+ 2$ من النقاط الأصلية على نفس الكرة الفائقة ذات البُعد d $،$ أي أن النقاط ليست في وضع عام. ^[³^]

ملكيات

ليكن $n$ عدد النقاط و $d$ عدد الأبعاد.

اتحاد جميع الأشكال البسيطة في عملية التثليث هو الغلاف المحدب للنقاط.
يحتوي التثليث ديلاوناي على $\textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}$ ⁠ simplices.^{[ 4 ]}
في المستوى ( $d = 2$ )، إذا كان هناك $b$ رأسًا على الغلاف المحدب، فإن أي تثليث للنقاط يحتوي على $2n - 2 - b$ مثلثًا على الأكثر، بالإضافة إلى وجه خارجي واحد (انظر خاصية أويلر ).
إذا وُزِّعت النقاط وفقًا لعملية بواسون في المستوى بكثافة ثابتة، فإن لكل رأس ستة مثلثات محيطة به في المتوسط. وبشكل أعم، بالنسبة للعملية نفسها في $d$ بُعد، يكون متوسط عدد الجيران ثابتًا ويعتمد فقط على $d$ . ^{[ 5 ]}
في المستوى، تُعظّم عملية التثليث ديلاوناي الزاوية الصغرى. وبالمقارنة مع أي عملية تثليث أخرى للنقاط، فإن أصغر زاوية في عملية التثليث ديلاوناي لا تقل عن أصغر زاوية في أي عملية تثليث أخرى. مع ذلك، لا تُقلّل عملية التثليث ديلاوناي بالضرورة الزاوية العظمى. ^{[ 6 ]} كما أنها لا تُقلّل بالضرورة طول الحواف.
الدائرة المحيطة بأي مثلث ديلاوناي لا تحتوي على أي نقاط إدخال أخرى في داخلها.
إذا لم تحتوي الدائرة التي تمر عبر نقطتين من نقاط الإدخال على أي نقاط إدخال أخرى في داخلها، فإن القطعة المستقيمة التي تربط النقطتين هي حافة من مثلث ديلاوناي للنقاط المعطاة.
يتوافق كل مثلث من مثلثات ديلاوناي لمجموعة من النقاط في الفضاءات ذات الأبعاد $d مع وجه من$ الغلاف المحدب لإسقاط النقاط على قطع مكافئ ذي أبعاد ( $d + 1$ ) ، والعكس صحيح.
أقرب جار $b$ لأي نقطة $p$ يقع على حافة $bp$ في تثليث ديلاوناي لأن الرسم البياني لأقرب جار هو رسم بياني فرعي من تثليث ديلاوناي.
يُعدّ تثليث ديلاوناي أداةً هندسيةً لتوسيع المسافة : في المستوى ( $d = 2$ )، من المعروف أن أقصر مسار بين رأسين، على طول حواف ديلاوناي، لا يزيد طوله عن 1.998 ضعف المسافة الإقليدية بينهما. ^{[ 7 ]}

تعريف ديلاوناي البصري: الانعكاس

من الخصائص المذكورة أعلاه تظهر ميزة مهمة: بالنظر إلى مثلثين $△ ABD و △ BCD$ مع الحافة المشتركة $BD$ (انظر الأشكال)، إذا كان مجموع الزوايا $α + γ \leq 180 درجة$ ، فإن المثلثات تحقق شرط ديلاوناي.

هذه خاصية مهمة لأنها تسمح باستخدام تقنية الانعكاس . إذا لم يستوفِ مثلثان شرط ديلاوناي، فإن تبديل الضلع المشترك $BD$ بالضلع المشترك $AC$ ينتج عنه مثلثان يستوفيان شرط ديلاوناي.

لا يفي هذا التثليث بشرط ديلاوناي (مجموع $α$ و $γ$ أكبر من 180 درجة).
لا يفي هذا الزوج من المثلثات بشرط ديلاوناي (توجد نقطة داخل الدائرة المحيطة).
يؤدي قلب الحافة المشتركة إلى إنشاء مثلث ديلاوناي صالح للنقاط الأربع.

تُسمى هذه العملية بالقلب ، ويمكن تعميمها على ثلاثة أبعاد أو أكثر. ^{[ 8 ]}

الخوارزميات

تعتمد العديد من خوارزميات حساب مثلثات ديلاوناي على عمليات سريعة للكشف عن وجود نقطة داخل الدائرة المحيطة بالمثلث، وعلى بنية بيانات فعّالة لتخزين المثلثات وحوافها. في بُعدين، تتمثل إحدى طرق الكشف عما إذا كانت النقطة $D$ تقع داخل الدائرة المحيطة بالمثلثات $A وB وC$ في حساب قيمة المحدد : ^{[ 9 ]}

{\begin{محاذاة}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{ x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix} A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}

عندما يتم ترتيب $A و B و C بترتيب$ عكس اتجاه عقارب الساعة ، يكون هذا المحدد موجبًا فقط إذا كان $D$ يقع داخل الدائرة المحيطة.

خوارزميات القلب

كما ذُكر سابقًا، إذا كان المثلث غير ديلاوناي، يُمكننا قلب أحد أضلاعه. وهذا يُؤدي إلى خوارزمية بسيطة: إنشاء أي تثليث للنقاط، ثم قلب الأضلاع حتى لا يكون أي مثلث غير ديلاوناي. لسوء الحظ، قد يتطلب هذا $Ω(n²)$ ^من عمليات قلب الأضلاع. ^[ $10$ ^] مع أن هذه الخوارزمية قابلة للتعميم على ثلاثة أبعاد أو أكثر، إلا أن تقاربها غير مضمون في هذه الحالات، لأنه مشروط باتصال الرسم البياني الأساسي للقلب : هذا الرسم البياني متصل لمجموعات النقاط ثنائية الأبعاد، ولكنه قد يكون غير متصل في الأبعاد الأعلى. ^{[ 8 ]}

إدخال نقطتين أثناء الخوارزمية التزايدية التي توضح اختبارات الدائرة المحيطة وانعكاسات الحواف المستخدمة للحفاظ على خاصية ديلاوناي بعد إعادة التثليث.

تدريجي

أبسط طريقة لحساب تثليث ديلاوناي بكفاءة هي إضافة رأس واحد في كل مرة، وإعادة تثليث الأجزاء المتأثرة من الرسم البياني. عند إضافة رأس $v$ ، نقسم المثلث الذي يحتوي على $v$ إلى ثلاثة أجزاء ، ثم نطبق خوارزمية القلب. بهذه الطريقة البسيطة، يستغرق الأمر زمنًا قدره $O(n)$ : نبحث في جميع المثلثات للعثور على المثلث الذي يحتوي على $v$ ، ثم نقلب كل مثلث على حدة. وبالتالي، يكون زمن التشغيل الإجمالي $O$ $(n²)$ .

إذا أدخلنا الرؤوس بترتيب عشوائي، يتضح (من خلال برهان معقد نوعًا ما) أن كل إدخال سيقلب، في المتوسط، $O(1)$ مثلثًا فقط - على الرغم من أنه في بعض الأحيان سيقلب عددًا أكبر بكثير. ^{[ 11 ]} هذا لا يزال يترك مجالًا لتحسين وقت تحديد موقع النقطة. يمكننا تخزين سجل عمليات التقسيم والقلب التي تم إجراؤها: يخزن كل مثلث مؤشرًا إلى المثلثين أو الثلاثة التي حلت محله. للعثور على المثلث الذي يحتوي على $v$ ، نبدأ من مثلث الجذر، ونتبع المؤشر الذي يشير إلى مثلث يحتوي على $v$ ، حتى نجد مثلثًا لم يتم استبداله بعد. في المتوسط، سيستغرق هذا أيضًا وقتًا قدره $O(log n)$ . على جميع الرؤوس، إذن، يستغرق هذا وقتًا قدره $O(n log n) .$ ^{[ 12 ]} في حين أن هذه التقنية قابلة للتمديد إلى أبعاد أعلى (كما أثبت إيدلسبرونر وشاه ^{[ 13 ]} )، يمكن أن يكون وقت التشغيل أُسّيًا في البُعد حتى لو كان تثليث ديلاوناي النهائي صغيرًا.

توفر خوارزمية بوير -واتسون نهجًا آخر للبناء التدريجي. فهي تقدم بديلاً لقلب الحواف لحساب مثلثات ديلاوناي التي تحتوي على رأس مُضاف حديثًا.

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

فرق تسد

طوّر لي وشاختر خوارزمية فرق تسد لإنشاء المثلثات في بُعدين ، ثم حسّنها غيباس وستولفي ^[⁹^]^[¹⁵^] ، ولاحقًا دوير ^[¹⁶^] . في هذه الخوارزمية، يُرسم خط بشكل متكرر لتقسيم الرؤوس إلى مجموعتين. تُحسب مثلثات ديلاوناي لكل مجموعة، ثم تُدمج المجموعتان على طول خط التقسيم. باستخدام بعض الحيل الذكية، يمكن إتمام عملية الدمج في زمن $O($ $n$ $)$ ، وبالتالي يكون زمن التشغيل الكلي $O($ $n$ $log$ $n$ $)$ ^[¹⁷^] .

بالنسبة لأنواع معينة من مجموعات النقاط، مثل التوزيع العشوائي المنتظم، من خلال اختيار خطوط التقسيم بذكاء، يمكن تقليل الوقت المتوقع إلى $O(n log log n)$ مع الحفاظ على أداء أسوأ الحالات.

تم تقديم نموذج فرق تسد لإجراء عملية التثليث في أبعاد $d$ في "DeWall: خوارزمية تثليث ديلاوناي سريعة بفرق تسد في E ^d " من تأليف P. Cignoni و C. Montani و R. Scopigno. ^{[ 18 ]}

لقد ثبت أن خوارزمية فرق تسد هي أسرع تقنية لتوليد شجرة القرار بشكل متسلسل. ^{[ 19 ]}^{[ 20 ]}

سويب هول

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

التطبيقات

إن الشجرة الممتدة الدنيا الإقليدية لمجموعة من النقاط هي مجموعة فرعية من تثليث ديلاوناي لنفس النقاط، ^{[ 22 ]} ويمكن استغلال ذلك لحسابها بكفاءة.

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

يمكن استخدام عمليات التثليث ديلاوناي لتحديد كثافة أو شدة أخذ عينات النقاط عن طريق مقدر مجال التبليط ديلاوناي (DTFE) .

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

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

وقد وجدت تقنية التثليث المقيد لديلوناي تطبيقات في تخطيط المسار في القيادة الآلية والمسح الطبوغرافي. ^{[ 23 ]}

انظر أيضاً

هيكل بيتا
تبليط فورونوي المركزي
خوارزميات الغلاف المحدب
صقل ديلاوناي
طقم ديلون - المعروف أيضاً باسم طقم ديلاوناي
فرط التجانس غير المنتظم
اجتياز الأبعد أولاً – إدخال فورونوي التدريجي
رسم بياني لغابرييل
تحليل نمط التدرج
مُقيدٌ بنمط هامينغ – مُقيدٌ بنمط تعبئة الكرات
خوارزمية ليندي-بوزو-غراي
خوارزمية لويد – تكرار فورونوي
مجموعة ماير
رقم بيسوت-فيجاياراغافان
تثليث بيتيواي
بليزيوهيدرون
شبه البلورة
التثليث شبه المثلثي
رقم سالم
نقطة شتاينر (مثلث)
شبكة مثلثة
رسم بياني أوركهارت
مخطط فورونوي

مراجع

↑ بشكل عام، المنطقة التي سيحيط بها شريط مطاطي ممتد حول النقاط.
1 2 ديلوناي، بوريس (1934). "Sur la spère vide" [ في الكرة الفارغة ] . نشرة أكاديمية العلوم في L'URSS، فئة علوم الرياضيات والطبيعة (باللغة الفرنسية). 6 : 793 – 800.
↑ فوكودا، كومي . "الأسئلة الشائعة في الحساب متعدد السطوح" . www.cs.mcgill.ca . تم الاطلاع عليه بتاريخ 29 أكتوبر 2018 .
↑ سيدل، رايموند (1995). "نظرية الحد الأعلى للمضلعات: برهان سهل لصيغتها التقاربية". الهندسة الحسابية . 5 (2): 115-116 . doi : 10.1016/0925-7721(95)00013-Y .
↑ ميجرينغ، جيه إل (1953). "مساحة السطح البيني، وطول الحافة، وعدد الرؤوس في التجمعات البلورية ذات التكوين العشوائي" (ملف PDF) . تقارير أبحاث فيليبس . 8 : 270-290 . مؤرشف من الأصل (ملف PDF) بتاريخ 2017-03-08.كما ورد في دواير، ريكس أ. (1991). "مخططات فورونوي متعددة الأبعاد في زمن خطي متوقع". الهندسة المنفصلة والحسابية . 6 (4): 343-367 . doi : 10.1007/BF02574694 . MR 1098813 .
↑ إيدلسبرونر، هربرت ؛ تان، تيو سينغ؛ واوبوتيتش، رومان (1992). "خوارزمية زمنية من رتبة ^O( n² log n ) لتثليث الزاوية الدنيا القصوى" (ملف PDF) . مجلة SIAM للحوسبة العلمية والإحصائية . 13 (4): 994-1008 . CiteSeerX 10.1.1.66.2895 . doi : 10.1137/0913058 . MR 1166172. مؤرشف من الأصل (ملف PDF) بتاريخ 9 فبراير 2017. تم الاطلاع عليه بتاريخ 24 أكتوبر 2017 . .
↑ شيا، جي (2013) . "معامل التمدد لتثليث ديلاوناي أقل من 1.998". مجلة SIAM للحوسبة . 42 (4): 1620-1659 . arXiv : 1103.4361 . doi : 10.1137/110832458 . MR 3082502. S2CID 6646528 .
1 2 دي لويرا، خيسوس أ .؛ رامباو، يورغ؛ سانتوس، فرانسيسكو (2010). التثليثات، هياكل الخوارزميات وتطبيقاتها . الخوارزميات والحساب في الرياضيات. المجلد 25. سبرينغر.
1 2 غيباس، ليونيداس ؛ ستولفي، خورخي (1985). "الأساسيات لمعالجة التقسيمات العامة وحساب فورونوي" . معاملات ACM في الرسومات . 4 (2): 74-123 . doi : 10.1145/282918.282923 . S2CID 52852815 .
↑ هورتادو، ف .؛ نوي، م.؛ أوروتيا، ج. (1999). "قلب الحواف في التثليثات" . الهندسة المنفصلة والحسابية . 22 (3): 333-346 . doi : 10.1007/PL00009464 .
↑ غيباس، ليونيداس ج .؛ كنوت، دونالد إي .؛ شارير، ميشا (1992). "البناء التزايدي العشوائي لمخططات ديلاوناي وفورونوي". Algorithmica . 7 ( 1-6 ): 381-413 . doi : 10.1007/BF01758770 . S2CID 3770886 .
^ دي بيرج، مارك. أوتفريد تشيونج ؛ مارك فان كريفيلد؛ مارك أوفرمارس (2008). الهندسة الحسابية: الخوارزميات والتطبيقات (PDF) . سبرينغر-فيرلاغ. رقم ISBN 978-3-540-77973-5أُرشف من النسخة الأصلية (PDF) بتاريخ 28-10-2009 . تم الاطلاع عليه بتاريخ 23-02-2010 .
↑ إيدلسبرونر، هربرت ؛ شاه، نيميش (1996). "القلب الطوبولوجي التدريجي يعمل مع التثليثات المنتظمة". Algorithmica . 15 (3): 223–241 . doi : 10.1007/BF01975867 . S2CID 12976796 .
↑ بليلوخ، غاي؛ غو، يان؛ شون، جوليان؛ وسون، ييهان. التوازي في الخوارزميات التزايدية العشوائية . مؤرشف بتاريخ 25 أبريل 2018 في أرشيف الإنترنت . SPAA 2016. doi:10.1145/2935764.2935766.
↑ بيترسون، صموئيل. "حساب مثلثات ديلاوناي المقيدة في المستوى" . www.geom.uiuc.edu . مؤرشف من الأصل في 22 سبتمبر 2017. تم الاطلاع عليه في 25 أبريل 2018 .
↑ دوير، ريكس أ. (نوفمبر 1987). "خوارزمية أسرع لتقسيم وحلّ المسائل لإنشاء مثلثات ديلاوناي". Algorithmica . 2 ( 1-4 ): 137-151 . doi : 10.1007/BF01840356 . S2CID 10828441 .
↑ ليتش، ج. (يونيو 1992). "تحسين خوارزميات التثليث الأمثل لديلوناي في أسوأ الحالات". المؤتمر الكندي الرابع للهندسة الحسابية . CiteSeerX 10.1.1.56.2323 .
↑ سيغنوني، ب.؛ سي. مونتاني؛ ر. سكوبينيو (1998). "ديوال: خوارزمية تثليث ديلاوناي سريعة تعتمد على أسلوب فرق تسد في E ^d ". التصميم بمساعدة الحاسوب . 30 (5): 333-341 . doi : 10.1016/S0010-4485(97)00082-1 .
↑ مقارنة بين خوارزميات التثليث المتسلسل لديلوناي "نسخة مؤرشفة" (PDF) . مؤرشفة من الأصل (PDF) بتاريخ 2012-03-08 . تم الاطلاع عليها بتاريخ 2010-08-18 .{{cite web}}: CS1 maint: archived copy as title ( link )
↑ "خوارزميات التثليث وهياكل البيانات" . www.cs.cmu.edu . مؤرشف من الأصل بتاريخ 10 أكتوبر 2017. تم الاطلاع عليه بتاريخ 25 أبريل 2018 .
↑ "S-hull" (ملف PDF) . s-hull.org . مؤرشف (ملف PDF) من الأصل بتاريخ 27-10-2013 . تم الاطلاع عليه بتاريخ 25 أبريل 2018 .
↑ فرانز أورينهامر؛ رولف كلاين؛ دير-تساي لي (26 يونيو 2013). مخططات فورونوي وتثليثات ديلاوناي . شركة وورلد ساينتيفيك للنشر. ص 197 وما بعدها. ISBN 978-981-4447-65-2.
↑ ستيرلينغ ج. أندرسون؛ سيسير ب. كارومانشي؛ كارل إياغنيما (5 يوليو 2012). "التخطيط والتحكم القائم على القيود لتشغيل المركبات بشكل آمن وشبه ذاتي" (ملف PDF) . ندوة IEEE للمركبات الذكية لعام 2012. IEEE. doi : 10.1109/IVS.2012.6232153 . مؤرشف من الأصل (ملف PDF) في 28 فبراير 2019. تم الاطلاع عليه في 27 فبراير 2019 .

روابط خارجية

هنري، إيان (11 يوليو 2022). " تصور تثليث ديلاوناي ". منشور مدونة يشرح بالتفصيل خوارزميات تثليث ديلاوناي.
التثليث ديلاوناي في مكتبة خوارزميات الهندسة الحسابية CGAL :
- مارييت يفينيك . التثليث ثنائي الأبعاد . تم الاطلاع عليه في أبريل 2010.
- بيون، سيلفان؛ تيلو، مونيك . التثليث ثلاثي الأبعاد . تم الاطلاع عليه في أبريل 2010.
- هورنوس، صموئيل. ديفيلرز، أوليفييه؛ جامين، كليمان. د التثليث .
- هيرت، سوزان؛ سيل، مايكل. الأغلفة المحدبة ثلاثية الأبعاد وتثليثات ديلاوناي . تم الاطلاع عليه في أبريل 2010.
" Poly2Tri: تثليث ديلاوناي المقيد التدريجي . تطبيق مفتوح المصدر بلغة C++. تم الاطلاع عليه في أبريل 2019."
" بناء مثلثات ديلاوناي بتقنية فرق تسد ". تطبيق مفتوح المصدر بلغة C99. تم الاطلاع عليه في أبريل 2019.
" CDT: التثليث المقيد لديلوناي في لغة C++ ". تطبيق مفتوح المصدر بلغة C++. تم الاطلاع عليه في أغسطس 2022.

[1] بشكل عام، المنطقة التي سيحيط بها شريط مطاطي ممتد حول النقاط.

[Delaunay1934-2] 1 2 ديلوناي، بوريس (1934). "Sur la spère vide" [ في الكرة الفارغة ] . نشرة أكاديمية العلوم في L'URSS، فئة علوم الرياضيات والطبيعة (باللغة الفرنسية). 6 : 793 – 800.

[Fukuda-3] فوكودا، كومي . "الأسئلة الشائعة في الحساب متعدد السطوح" . www.cs.mcgill.ca . تم الاطلاع عليه بتاريخ 29 أكتوبر 2018 .

[Seidel1995-4] سيدل، رايموند (1995). "نظرية الحد الأعلى للمضلعات: برهان سهل لصيغتها التقاربية". الهندسة الحسابية . 5 (2): 115-116 . doi : 10.1016/0925-7721(95)00013-Y .

[Meijering-5] ميجرينغ، جيه إل (1953). "مساحة السطح البيني، وطول الحافة، وعدد الرؤوس في التجمعات البلورية ذات التكوين العشوائي" (ملف PDF) . تقارير أبحاث فيليبس . 8 : 270-290 . مؤرشف من الأصل (ملف PDF) بتاريخ 2017-03-08.كما ورد في دواير، ريكس أ. (1991). "مخططات فورونوي متعددة الأبعاد في زمن خطي متوقع". الهندسة المنفصلة والحسابية . 6 (4): 343-367 . doi : 10.1007/BF02574694 . MR 1098813 .

[ETW1992-6] إيدلسبرونر، هربرت ؛ تان، تيو سينغ؛ واوبوتيتش، رومان (1992). "خوارزمية زمنية من رتبة ^O( n² log n ) لتثليث الزاوية الدنيا القصوى" (ملف PDF) . مجلة SIAM للحوسبة العلمية والإحصائية . 13 (4): 994-1008 . CiteSeerX 10.1.1.66.2895 . doi : 10.1137/0913058 . MR 1166172. مؤرشف من الأصل (ملف PDF) بتاريخ 9 فبراير 2017. تم الاطلاع عليه بتاريخ 24 أكتوبر 2017 . .

[Xia-7] شيا، جي (2013) . "معامل التمدد لتثليث ديلاوناي أقل من 1.998". مجلة SIAM للحوسبة . 42 (4): 1620-1659 . arXiv : 1103.4361 . doi : 10.1137/110832458 . MR 3082502. S2CID 6646528 .

[DRS-8] 1 2 دي لويرا، خيسوس أ .؛ رامباو، يورغ؛ سانتوس، فرانسيسكو (2010). التثليثات، هياكل الخوارزميات وتطبيقاتها . الخوارزميات والحساب في الرياضيات. المجلد 25. سبرينغر.

[GS1985-9] 1 2 غيباس، ليونيداس ؛ ستولفي، خورخي (1985). "الأساسيات لمعالجة التقسيمات العامة وحساب فورونوي" . معاملات ACM في الرسومات . 4 (2): 74-123 . doi : 10.1145/282918.282923 . S2CID 52852815 .

[Hurtado-10] هورتادو، ف .؛ نوي، م.؛ أوروتيا، ج. (1999). "قلب الحواف في التثليثات" . الهندسة المنفصلة والحسابية . 22 (3): 333-346 . doi : 10.1007/PL00009464 .

[GKS1992-11] غيباس، ليونيداس ج .؛ كنوت، دونالد إي .؛ شارير، ميشا (1992). "البناء التزايدي العشوائي لمخططات ديلاوناي وفورونوي". Algorithmica . 7 ( 1-6 ): 381-413 . doi : 10.1007/BF01758770 . S2CID 3770886 .

[deBerg-12] دي بيرج، مارك. أوتفريد تشيونج ؛ مارك فان كريفيلد؛ مارك أوفرمارس (2008). الهندسة الحسابية: الخوارزميات والتطبيقات (PDF) . سبرينغر-فيرلاغ. رقم ISBN 978-3-540-77973-5أُرشف من النسخة الأصلية (PDF) بتاريخ 28-10-2009 . تم الاطلاع عليه بتاريخ 23-02-2010 .

[ES1996-13] إيدلسبرونر، هربرت ؛ شاه، نيميش (1996). "القلب الطوبولوجي التدريجي يعمل مع التثليثات المنتظمة". Algorithmica . 15 (3): 223–241 . doi : 10.1007/BF01975867 . S2CID 12976796 .

[Parallel-14] بليلوخ، غاي؛ غو، يان؛ شون، جوليان؛ وسون، ييهان. التوازي في الخوارزميات التزايدية العشوائية . مؤرشف بتاريخ 25 أبريل 2018 في أرشيف الإنترنت . SPAA 2016. doi:10.1145/2935764.2935766.

[Peterson-15] بيترسون، صموئيل. "حساب مثلثات ديلاوناي المقيدة في المستوى" . www.geom.uiuc.edu . مؤرشف من الأصل في 22 سبتمبر 2017. تم الاطلاع عليه في 25 أبريل 2018 .

[Dwyer1987-16] دوير، ريكس أ. (نوفمبر 1987). "خوارزمية أسرع لتقسيم وحلّ المسائل لإنشاء مثلثات ديلاوناي". Algorithmica . 2 ( 1-4 ): 137-151 . doi : 10.1007/BF01840356 . S2CID 10828441 .

[Leach1992-17] ليتش، ج. (يونيو 1992). "تحسين خوارزميات التثليث الأمثل لديلوناي في أسوأ الحالات". المؤتمر الكندي الرابع للهندسة الحسابية . CiteSeerX 10.1.1.56.2323 .

[CMS1998-18] سيغنوني، ب.؛ سي. مونتاني؛ ر. سكوبينيو (1998). "ديوال: خوارزمية تثليث ديلاوناي سريعة تعتمد على أسلوب فرق تسد في E ^d ". التصميم بمساعدة الحاسوب . 30 (5): 333-341 . doi : 10.1016/S0010-4485(97)00082-1 .

[19] مقارنة بين خوارزميات التثليث المتسلسل لديلوناي "نسخة مؤرشفة" (PDF) . مؤرشفة من الأصل (PDF) بتاريخ 2012-03-08 . تم الاطلاع عليها بتاريخ 2010-08-18 .{{cite web}}: CS1 maint: archived copy as title ( link )

[20] "خوارزميات التثليث وهياكل البيانات" . www.cs.cmu.edu . مؤرشف من الأصل بتاريخ 10 أكتوبر 2017. تم الاطلاع عليه بتاريخ 25 أبريل 2018 .

[21] "S-hull" (ملف PDF) . s-hull.org . مؤرشف (ملف PDF) من الأصل بتاريخ 27-10-2013 . تم الاطلاع عليه بتاريخ 25 أبريل 2018 .

[AK2013-22] فرانز أورينهامر؛ رولف كلاين؛ دير-تساي لي (26 يونيو 2013). مخططات فورونوي وتثليثات ديلاوناي . شركة وورلد ساينتيفيك للنشر. ص 197 وما بعدها. ISBN 978-981-4447-65-2.

[AKI2012-23] ستيرلينغ ج. أندرسون؛ سيسير ب. كارومانشي؛ كارل إياغنيما (5 يوليو 2012). "التخطيط والتحكم القائم على القيود لتشغيل المركبات بشكل آمن وشبه ذاتي" (ملف PDF) . ندوة IEEE للمركبات الذكية لعام 2012. IEEE. doi : 10.1109/IVS.2012.6232153 . مؤرشف من الأصل (ملف PDF) في 28 فبراير 2019. تم الاطلاع عليه في 27 فبراير 2019 .

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

من

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[

[

[

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗