موضوع مقاله: مثلث‌بندی دیلانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مثلث‌بندی دیلانی | مقدمه: این مثلث‌بندی کمینهٔ زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری می‌کند. | ## بخش 1: مثلث‌بندی دیلانی | با در نظر گرفتن کره‌های محاطی ایدهٔ تثلیث دیلانی به سه یا تعداد بیشتری بعد تعمیم می یابد . تعمیم به سیستم متریک نسبت به سیستم اقلیدسی ترجیح داده می‌شود ولی در این موارد (اقلیدسی) تثلیث دیلانی الزاماً وجود ندارد یا یکتا نیست. ارتباط با دیاگرام ورونی تثلیث دیلانی در فضای گسسته مجموعه p در جنرال پوزیشن مربوط به گراف‌های دوگانه از دیاگرام ورونی از مجموعه p. موردهای خاصی که شامل سه نقطه‌ای که روی یک خط اند و چهار نقطهای که روی یک دایره‌اند. دیلانی d بعدی دیلانی d بعدی برای مجموع نقاط p در فضای فضای اقلیدسی اقلیدسی d بعدی تثلیث دیلانی( DT( p است به‌طوری‌که هیچ نقطهای در P درون ابر کره محیطی هر سیمپلکس در (DT(P نباشد . اثبات شده که در برای هر p یک تثلیث دیلانی یکتا وجود دارد که p گروهی از نقاط در جنرال پوزیشن باشند که نتیجه می‌دهد هیچ زیر فضای k بعدی آن شامل k + 2 نقطه یا کره k بعدی شامل k + 3 نقطه نباشد برای 1 ≤ k ≤ d − 1 (برای مثال برا ی یک مجموعه نقاط در ℝ3 هیچ سه نقطه‌ای روی یک خط وجود ندارند، هیچ چهار نقطه‌ای روی یک صفحه، هیچ چهار نقطه‌ای روی یک دایره و هیچ 5 نقطه‌ای روی یک کره وجود ندارد) مسئله پیدا کردن تثلیث دیلانی برای گروهی از نقاط در فضای ی بعدی اقلیدسی قابل تبدیل به مسئلهٔ یافتن پوش محدب برای یک مجموعه نقاط در فضای d + 1 بعدی با دادن مختصات اضافی p|2|، به هر نقطه p و گرفتن گوشه پایین پوش محدب و نگاشتن مجدد به فضای d بعدی با حذف مختصات اخیر است. چون پوش محدب یکتاست بنابراین تثلیث نیز یکتاست با فرض اینکه تمام اضلاع پوش محدب سیمپلکس هستند . اضلاع غیر سیمپلکس تنها زمانی پدید می آیند که d + 2 تا از نقاط اصلی روی یک ابر کرهابر کره دی بعدی باشند به عنوان مثال نقاط در جنرال پوزیشن نباشند. 3- در صفحه (d =2) اگر b راس در پوش محدب باشند هر تثلیثی از آن نقاط حدااکثر 2n - 2 - b مثلث دارد به علاوه یک وجه بیرونی در صفحه. 5- در صفحه، تثلیث دیلانی مینمم زاویه را بیشینه می‌کند در مقایسه با هر تثلیث دیگری ازنقاط کوچکترین زاویه در تثلیث دیلانی حداقل به بزرگی کوچکترین زاویه در بقیه است اما تثلیث دیلانی الزاماً ماکسیمم زاویه را کمینه نمی‌کند تثلیث دیلانی همچنین الزاماً طول اضلاع را مینمم نمی‌کند. 7- اگر یک دایره که از دو تا از نقاط داده شده بگذرد هیچ نقطه دیگری درون خود ندارد بنابراین بخشی که دو نقطه را به هم متصل می‌کند یک ضلع تثلیث دیلانی نقاط داده شده‌است. 8- هر مثلث تثلیث دیلانی برای نقاط فضای d بعدی در یک وجه پوش محدب تصویر نقاط روی سهمی وار d + 1 بعدی صدق می‌کند و بلعکس. 9- نزدیک‌ترین همسایگی b به هر نقطه p روی یک ضلع در تثلیث دیلانی قرار دارد چون نزدیک‌ترین گراف همسایه یک زیر گراف از تثلیث دیلانی است. 10- تثلیث دیلانی یک اسپنر هندسی است :کوتاه‌ترین مسیر بین دو راس در طول اضلاع دیلانی بیشتر از برابر فاصله اقلیدسی بین آن‌ها نیست. با نگاه کردن به دومثلث ABD و BCD با ضلع مشترک BD اگر زوایای α و γ کوچکتر مساوی 180 شود مثلث‌ها شرط دیلانی را براورده می‌کنند. | ## بخش 2: مثلث‌بندی دیلانی | اگر دو مثلث شرط دیلانی را برآورده نکنند جا به جا کردن ضلع مشترک BD با ضلع مشترک AC دو مثلث تولید می‌کند که شرط دیلانی را براورده می‌کند. الگوریتم‌ها الگوریتم‌های زیادی برای محاسبهٔ تثلیث دیلانی بر اساس عملیات سریع برای یافتن نقطه‌ای درون دایره محیطی مثلث و یک داده ساختار کارامد برای ذخیره سای مثلث‌ها و اضلاع وجود دارد. در دو بعد یک راه برای فهمیدن اینکه آیا نقطه d درون دایره محیطی A و B و C قرار دارد محاسبه دترمینان این ماتریس به ما نشان می‌دهد. وقتی A و B و C به ترتیب پاد ساعت گرد مرتب شوند این دترمینان مثبت است اگر و تنها اگر d درون دایره محیطی باشد . الگوریتم چرخاندن همان طور که در بالا ذکر شد اگر یک مثلث غیر دیلانی باشد ما می‌توانیم یکی از ضلع‌های ان را بچرخانیم کنیم. این منجر به یک الگوریتم راحت می‌شود : هر تثلیث از نقاط را بسازید و سپس اضلاع را بچرخانید تا زمانی که هیچ مثلثی غیر دیلانی نباشد. متأسفانه این عملیات ازین (O(n2 چرخاندن ضلع لازم دارد و به سه یا بیش از آن قابل تعمیم نیست.. افزایشی آسان‌ترین‌ترین راه برای محاسبه کارامد تثلیث دیلانی افزودن مکرر راس در یک زمان و تثلیث مجدد قسمت‌های تغییر یافته گراف است. وقتی یک راس v اضافه می‌شود ما مثلث شامل v را به سه قسمت تقسیم می‌کنیم سپس الگوریتم چرخاندن را اعمال می‌کنیم اگر اینکار به صورت اشتباه انجام شود از (O(n مرتبه زمان میبرد. ما بین تمام مثلث‌ها جستجو کرده تا v را پیدا کنیم سپس هر مثلث را یکبار میچرخانیم پس زمان اجرا کلی از اردر (O(n2 است . اگر ما راس‌هایی به صورت تصادفی وارد کنیم معلوم می‌شود (با شواهد پیچیده) که هر ورود به‌طور متوسط فقط (O(1 مثلث را میچرخاند - با و جود اینکه امکان دارد گاهی اوقات تعداد بیشتری را بچرخاند. ما می‌توانیم تاریخچه تقسیم‌ها و چرخاندن‌های انجام شده را ذخیره کنیم: هر مثلث یک اشاره گر به دو یا سه مثلث که جایگزین آن شده‌اند را ذخیره می‌کند . برای یافتن مثلثی که v را در بر دارد ما از مثلث پایه شروع می‌کنیم و اشاره‌گری که به مثلث شامل v اشاره می‌کند را دنبال می‌کنیم تا جایی که به مثلثی برسیم که هنوز جایگزین نشده‌است به‌طور متوسط این عملیات (O(log n زمان می‌برد . در حینی که این تکنیک به ابعاد بالاتر تعمیم می یابد (همانطور که توسط ادلزبرونر و شاح ثابت شده) ) زمان اجرا می‌تواند نسبت به بعد نمایی رشد کند اگر تثلیث دیلانی نهایی کوچک باشد. الگوریتم بویر واتسون یک رویکرد ساختار افزایشی دیگر را ارائه می‌دهد این رویکرد جایگزینی برای ضلع چرخان برای محاسبهٔ مثلث‌های دیلانی شامل یک راس تازه وارد شده می‌باشد. | ## بخش 3: مثلث‌بندی دیلانی | تبدیل به زیر مسئله‌ها الگوریتم تبدیل به زیر مسئله ها برای تثلیث‌ها در ابعاد دو توسط لیی و شاختر ابداع شد و توسط گی باس و استولفی بهبود داده شد و بعدها توسط دویر. تثلیث دیلانی برای هر مجموعه محاسبه می‌شود و سپس دو مجموعه در طول خط تقسیم ترکیب می‌شوند با استفاده چند شگرد هوشمندانه عملیات ترکیب می‌تواند در زمان (O(n انجام شود بنابراین زمان اجرا کل این (O(n logn است . برای گونه خاصی مشخصی از مجموعه نقاط از قبیل توزیع یکنواخت تصادفی با انتخاب هوشمند خطوط تقسیم زمان مورده انتظار می‌تواند به (O(nlog logn کاهش یابد در حالی که هنوز اجرای بدترین حالت را در اختیار دارد. الگوریتم تبدیل به زیر مسئله‌ها برای اجرای یک تثلیث در d بعد در قالب "دی وال : یک الگوریتم سریع تقسیم وغلبه تثلیث دیلانی در Ed"" توسط سیگنونی و منتانی و اسکوپینو ارائه شده‌است . پوش جاروب پوش جاروبS-hull یک تکنیک ترکیبی برای تثلیث دیلانی دو بعدی است که از یک جاروب تکثیر شعاعی (به ترتیب به وجود امده از مجموعه نقاط دو بعدی مرتب شده با فرض تثلیث بدون تداخل ) استفاده می‌کند که با یک قدم چرخاندن مثلث مکرر تزویج شده‌است . تثلیث دیلانی برای مدل‌سازی زمینه و اشیای دیگر که به عنوان مجموعه‌ای از نقاط داده شده‌اند یک مجموعهٔ خوبی از مثلث‌ها را می‌دهد که می‌تواند به عنوان چند ضلعی در مدل استفاده شود. به‌طور خاص تثلیث دیلانی سعی دارد از مثلث‌های باریک استفاده نکند(که آن‌ها درمقایسه با مساحت شان دایره محیطی‌های بزرگی دارند). تثلیث دیلانی به دلیل تضمین زاویه و به دلیل الگوریتم‌های مثلث بندی سریع توسعه یافته اغلب مورد استفاده برای ایجاد شبکه برای حل فضای گسسته مانند روش المان محدود و روش حجم محدود که از روش‌های شبیه‌سازی فیزیکی قرار می‌گیرند. به‌طور معمول، دامنه شبکه بندی به عنوان یک مجموعه مختلط ساده ی درشت مشخص شده‌است، برای شبکه به صورت عددی پایدار، باید آن خالص‌سازی کرد. افزایش محبوبیت استفاده از روش المان محدود و تکنیک‌های روش المان مرزی انگیزه برای بهبود الگوریتم‌های ی درگیر به صورت خودکار را افزایش می‌دهد. با این حال، همهٔ این الگوریتم‌ها می‌توانند عناصر شبکه نامنظم و حتی غیرقابل استفاده ایجاد کند. خوشبختانه، چندین روش وجود دارد که می‌تواند یک شبکه بندی موجود را بگیرد و آن را بهبود کیفیت بدهد. به عنوان مثال، صاف کردن ( همچنین به عنوان پالایش شبکه بندی نیز نامیده می‌شود) یکی از این روش هاست، که انباشتگی‌های محل گره‌ها را به منظور به حداقل رساندن اعوجاج عنصر می‌باشد . | ## جمع‌بندی | روش شبکه کشیده اجازه می‌دهد تا نسلی از شبکه شبه منظم که با ضوابط دیلانی سنخیت دارند و راه حل‌های یک مرحله ا ی دارند رشد کنند.