مثلث‌بندی دیلانی

یک نمایش مثلث بندی دیلانی با دوایر محیطی
در ریاضیات و هندسه محاسباتی، یک مثلث‌بندی دیلانی برای یک مجموعه از نقاط به نام P در یک صفحه، یک مثلث‌بندی به نام (DT(P است به نحوی که هیچ یک از نقاط P درون هیچ‌یک از دایره‌های محیطی مثلثهای (DT(P نباشد. این مثلث‌بندی کمینه زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری می‌کند. این مثلث‌بندی توسط بوریس دیلانی در سال ۱۹۳۴ ابداع شد.
برای چهار یا تعداد بیشتری نقطه روی یک دایره یکسان (به عنوان مثال راس‌های یک مستطیل) تثلیث دیلانی یکتا نیست : هر دو تثلیث ممکن که چهار ضلعی را به دو مثلث تقسیم می‌کند شرط دیلانی ارضا می‌کند به عنوان مثال فرض اینکه اگر تمام دایره‌های محیطی مثلث‌ها درون تهی باشند.
با در نظر گرفتن کره‌های محاطی ایده‌ی تثلیث دیلانی به سه یا تعداد بیشتری بعد تعمیم می‌یابد .تعمیم به سیستم متریک نسبت به سیستم اقلیدسی ترجیح داده می‌شود ولی در این موارد (اقلیدسی) تثلیث دیلانی الزاما وجود ندارد یا یکتا نیست.
ارتباط با دیاگرام ورونی
تثلیث دیلانی در فضای گسسته مجموعه p در جنرال پوزیشن مربوط به گراف‌های دوگانه از دیاگرام ورونی از مجموعه p.موردهای خاصی که شامل سه نقطه‌ای که روی یک خط اند و چهار نقطهای که روی یک دایره‌اند.
دیلانی d بعدی
دیلانی d بعدی برای مجموع نقاط p در فضای فضای اقلیدسی اقلیدسی d بعدی تثلیث دیلانی( DT( p است به‌طوری‌که هیچ نقطهای در P درون ابر کره محیطی هر سیمپلکس در (DT(P نباشد . اثبات شده که در برای هر p یک تثلیث دیلانی یکتا وجود دارد که p گروهی از نقاط در جنرال پوزیشن باشند که نتیجه می‌دهد هیچ زیر فضای k بعدی آن شامل k + 2 نقطه یا کره k بعدی شامل k + 3 نقطه نباشد برای
1 ≤ k ≤ d − 1 (برای مثال برا ی یک مجموعه نقاط در R 3 هیچ سه نقطه‌ای روی یک خط وجود ندارند ، هیچ چهار نقطه‌ای روی یک صفحه ، هیچ چهار نقطه‌ای روی یک دایره و هیچ 5 نقطه‌ای روی یک کره وجود ندارد)
مسئله پیدا کردن تثلیث دیلانی برای گروهی از نقاط در فضای ی بعدی اقلیدسی قابل تبدیل به مسئله‌ی یافتن پوش محدب برای یک مجموعه نقاط در فضای d + 1 بعدی با دادن مختصات اضافی p| 2 | ، به هر نقطه p و گرفتن گوشه پایین پوش محدب و نگاشتن مجدد به فضای d بعدی با حذف مختصات اخیر است.
چون پوش محدب یکتاست بنابراین تثلیث نیز یکتاست با فرض اینکه تمام اضلاع پوش محدب سیمپلکس هستند . اضلاع غیر سیمپلکس تنها زمانی پدید می‌آیند که d + 2 تا از نقاط اصلی روی یک ابر کرهابر کره دی بعدی باشند به عنوان مثال نقاط در جنرال پوزیشن نباشند.
ویژگی‌ها
قدم‌های مثال
انیمیشنی که نشان می‌دهد تثلیث دیلانی ضلع را کوتاه‌تر نمی‌کند حتما.
فرض کنید n تعداد نقاط و d تعداد بعد باشد.
1- اتحاد تمام سیمپلکس‌ها در تثلیث, پوش محدب تمام نقاط است.
2- تثلیث دیلانی شامل O(n ⌈d / 2⌉ )مثلث است.
3- در صفحه (d =2) اگر b راس در پوش محدب باشند هر تثلیثی از آن نقاط حدااکثر 2n - 2 - b مثلث دارد به علاوه یک وجه بیرونی در صفحه.
4- هر راس حداقل توسط شیش مثلث محاصره شده.
5- در صفحه، تثلیث دیلانی مینمم زاویه را بیشینه می‌کند در مقایسه با هر تثلیث دیگری ازنقاط کوچکترین زاویه در تثلیث دیلانی حداقل به بزرگی کوچکترین زاویه در بقیه است اما تثلیث دیلانی الزاما ماکسیمم زاویه را کمینه نمی‌کند تثلیث دیلانی همچنین الزاما طول اضلاع را مینمم نمی‌کند.
6- دایره‌ای که بر هر مثلث دیلانی محیط است هیچ نقطه داخلی دیگری درون خود ندارد.
7- اگر یک دایره که از دو تا از نقاط داده شده بگذرد هیچ نقطه دیگری درون خود ندارد بنا بر این بخشی که دو نقطه را به هم متصل می‌کند یک ضلع تثلیث دیلانی نقاط داده شده‌است.
8- هر مثلث تثلیث دیلانی برای نقاط فضای d بعدی در یک وجه پوش محدب تصویر نقاط روی سهمی وار d + 1 بعدی صدق می‌کند و بلعکس.
9- نزدیک‌ترین همسایگی b به هر نقطه p روی یک ضلع در تثلیث دیلانی قرار دارد چون نزدیک‌ترین گراف همسایه یک زیر گراف از تثلیث دیلانی است.
10- تثلیث دیلانی یک اسپنر هندسی است :کوتاه‌ترین مسیر بین دو راس در طول اضلاع دیلانی بیشتر از برابر فاصله اقلیدسی بین آن‌ها نیست.
تعبیر تصویری دیلانی : چرخاندن
از ویژگی‌های فوق یک ویژگی بدست می‌آید .با نگاه کردن به دومثلث ABD و BCD با ضلع مشترک BD اگر زوایای  و  کوچکتر مساوی 180 شود مثلث‌ها شرط دیلانی را براورده می‌کنند.
این یک ویژگی بسیار مهم است چون ما را قادر به استفاده از تکنیک چرخاندن می‌کند .اگر دو مثلث شرط دیلانی را برآورده نکنند جا به جا کردن ضلع مشترک BD با ضلع مشترک AC دو مثلث تولید می‌کند که شرط دیلانی را براورده میکند.
الگوریتم‌ها
الگوریتمهای زیادی برای محاسبه‌ی تثلیث دیلانی بر اساس عملیات سریع برای یافتن نقطه‌ای درون دایره محیطی مثلث و یک داده ساختار کارامد برای ذخیره سای مثلث‌ها و اضلاع وجود دارد. در دو بعد یک راه برای فهمیدن اینکه آیا نقطه d درون دایره محیطی A و B و C قرار دارد محاسبه دترمینان این ماتریس به ما نشان می‌دهد. .
\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 = \begin{vmatrix
A_x - D_x - A_y - D_y - (A_x^2 - D_x^2) + (A_y^2 - D_y^2) \\
B_x - D_x - B_y - D_y - (B_x^2 - D_x^2) + (B_y^2 - D_y^2) \\
C_x - D_x - C_y - D_y - (C_x^2 - D_x^2) + (C_y^2 - D_y^2)
\end{vmatrix> 0
وقتی A و B و C به ترتیب پاد ساعت گرد مرتب شوند این دترمینان مثبت است اگر و تنها اگر d درون دایره محیطی باشد .
الگوریتم چرخاندن
همان طور که در بالا ذکر شد اگر یک مثلث غیر دیلانی باشد ما می‌توانیم یکی از ضلع‌های ان را بچرخانیم کنیم.
این منجر به یک الگوریتم راحت می‌شود : هر تثلیث از نقاط را بسازید و سپس اضلاع را بچرخانید تا زمانی که هیچ مثلثی غیر دیلانی نباشد. متاسفانه این عملیات ازین (O(n 2 چرخاندن ضلع لازم دارد و به سه یا بیش از آن قابل تعمیم نیست. .
افزایشی
آسان‌ترین‌ترین راه برای محاسبه کارامد تثلیث دیلانی افزودن مکرر راس در یک زمان و تثلیث مجدد قسمت‌های تغییر یافته گراف است.
وقتی یک راس v اضافه می‌شود ما مثلث شامل v را به سه قسمت تقسیم می‌کنیم سپس الگوریتم چرخاندن را اعمال می‌کنیم اگر اینکار به صورت اشتباه انجام شود از (O(n مرتبه زمان میبرد. ما بین تمام مثلث‌ها جستجو کرده تا v را پیدا کنیم سپس هر مثلث را یکبار میچرخانیم پس زمان اجرا کلی از اردر (O(n 2 است .
اگر ما راس‌هایی به صورت تصادفی وارد کنیم معلوم می‌شود (با شواهد پیچیده) که هر ورود به‌طور متوسط فقط (O(1 مثلث را میچرخاند - با و جود اینکه امکان دارد گاهی اوقات تعداد بیشتری را بچرخاند . این هنوز زمان یافتن مکان نقطه را قابل بهبود می‌گذارد .ما می‌توانیم تاریخچه تقسیم‌ها و چرخاندن‌های انجام شده را ذخیره کنیم: هر مثلث یک اشاره گر به دو یا سه مثلث که جایگزین آن شده‌اند را ذخیره می‌کند .برای یافتن مثلثی که v را در بر دارد ما از مثلث پایه شروع می‌کنیم و اشاره گری که به مثلث شامل v اشاره می‌کند را
دنبال می‌کنیم تا جایی که به مثلثی برسیم که هنوز جایگزین نشده است به‌طور متوسط این عملیات (O(log n زمان می‌برد . برای تمام راس‌ها این عملیات ازین (O(n logn زمان می‌برد . در حینی که این تکنیک به ابعاد بالاتر تعمیم می‌یابد (همانطور که توسط ادلزبرونر و شاح ثابت شده ) ) زمان اجرا می‌تواند نسبت به بعد نمایی رشد کند اگر تثلیث دیلانی نهایی کوچک باشد.
الگوریتم بویر واتسون یک رویکرد ساختار افزایشی دیگر را ارائه می‌دهد این رویکرد جایگزینی برای ضلع چرخان برای محاسبه‌ی مثلث‌های دیلانی شامل یک راس تازه وارد شده می‌باشد.
تبدیل به زیر مسئله‌ها
الگوریتم تبدیل به زیر مسئله‌ها برای تثلیث‌ها در ابعاد دو توسط لیی و شاختر ابداع شد و توسط گی باس و استولفی بهبود داده شد و بعدها توسط دویر.در این الگوریتم مکررا خطی برای تقسیم راس‌ها به دو مجموعه رسم می‌شود.تثلیث دیلانی برای هر مجموعه محاسبه می‌شود و سپس دو مجموعه در طول خط تقسیم ترکیب می‌شوند با استفاده چند شگرد هوشمندانه عملیات ترکیب می‌تواند در زمان (O(n انجام شود بنا بر این زمان اجرا کل این (O(n logn است
برای گونه خاصی مشخصی از مجموعه نقاط از قبیل توزیع یکنواخت تصادفی با انتخاب هوشمند خطوط تقسیم زمان مورده انتظار می‌تواند به (O(nlog logn کاهش یابد در حالی که هنوز اجرای بدترین حالت را در اختیار دارد.
الگوریتم تبدیل به زیر مسئله‌ها برای اجرای یک تثلیث در d بعد در قالب "دی وال : یک الگوریتم سریع تقسیم وغلبه تثلیث دیلانی در E d "" توسط سیگنونی و منتانی و اسکوپینو ارائه شده است
تقسیم و غلبه نشان داده که سریع‌ترین تکنیک تولید DT است .
خط جاروب
الگوریتم شانس از تکنیک خط جاروب برای رسیدن به زمان اجرا (O(n logn در حالت صفحه‌ای استفاده می‌کنند.
پوش جاروب
پوش جاروب یک تکنیک ترکیبی برای تثلیث دیلانی دو بعدی است که از یک جاروب تکثیر شعاعی (به ترتیب بوجود امده از مجموعه نقاط دو بعدی مرتب شده با فرض تثلیث بدون تداخل ) استفاده می‌کند که با یک قدم چرخاندن مثلث مکرر تزویج شده‌است .همچنین یک متغیر منطقی صحیح دقیق برای الگوریتم ارائه می‌شود.
کاربردها
تثلیث دیلانی برای صد نقطه تصادفی در صفحه.درخت پوشای حداقل اقلیدسی یک مجموعه‌ای از نقطه‌ها زیرمجموعه‌ای از تثلیث دیلانی همان نقاط می‌باشد و این می‌تواند در کارایی محاسبات استفاده شود.
تثلیث دیلانی برای مدل‌سازی زمینه و اشیای دیگر که به عنوان مجموعه‌ای از نقاط داده شده‌اند یک مجموعه‌ی خوبی از مثلث‌ها را می‌دهد که می‌تواند به عنوان چند ضلعی در مدل استفاده شود.به‌طور خاص تثلیث دیلانی سعی دارد از مثلث‌های باریک استفاده نکند(که آن‌ها درمقایسه با مساحت شان دایره محیطی‌های بزرگی دارند).
تثلیث دیلانی می‌تواند برای مشخص کردن چگالی یا شدت نقاط در مدل‌سازی نقاط به معنی Delaunay tessellation field estimator استفاده شوند.
تثلیث دیلانی به دلیل تضمین زاویه و به دلیل الگوریتم‌های مثلث بندی سریع توسعه یافته اغلب مورد استفاده برای ایجاد شبکه برای حل فضای گسسته مانند روش المان محدود و روش حجم محدود که از روش‌های شبیه‌سازی فیزیکی قرار می‌گیرند. به‌طور معمول، دامنه شبکه بندی به عنوان یک مجموعه مختلط ساده‌ی درشت مشخص شده است، برای شبکه به صورت عددی پایدار ، باید آن خالص‌سازی کرد. به عنوان مثال با استفاده از الگوریتم راپرت.
افزایش محبوبیت استفاده از روش المان محدود و تکنیک‌های روش المان مرزی انگیزه برای بهبود الگوریتم‌های ی درگیر به صورت خودکار را افزایش می‌دهد. با این حال، همه این الگوریتم‌ها می‌توانند عناصر شبکه نامنظم و حتی غیر قابل استفاده ایجاد کند. خوشبختانه، چندین روش وجود دارد که می‌تواند یک شبکه بندی موجود را بگیرد و آن را بهبود کیفیت بدهد. به عنوان مثال، صاف کردن ( همچنین به عنوان پالایش شبکه بندی نیز نامیده می‌شود) یکی از این روش هاست، که انباشتگی‌های محل گره‌ها را به منظور به حداقل رساندن اعوجاج عنصر می‌باشد . روش شبکه کشیده اجازه می‌دهد تا نسلی از شبکه شبه منظم که با ضوابط دیلانی سنخیت دارند و راه حل‌های یک مرحله ا ی دارند رشد کنند.