مثلث‌بندی چندضلعی‌ها

در هندسه محاسباتی، به تقسیم‌بندی چند ضلعی‌ها به چندین مثلث، مثلث بندی چند ضلعی‌ها می‌گویند.

مثلث بندی به گونه‌ای است که، هیچ دو مثلثی روی هم نمی‌افتند و هر نقطه از چند ضلعی فقط و فقط در یک مثلث قرار می‌گیرد. به عبارت دیگر، اجتماع مثلث‌ها، چند ضلعی اولیه را تشکیل می‌دهد.

طبق یک تعریف سخت گیرانه برای مثلث بندی، تمام راس‌های مثلث‌ها باید منطبق بر راس‌های چند ضلعی باشد، در غیر این صورت راس‌های مثلث‌ها هر کجا بروی محیط یا داخل چند ضلعی می‌توانند باشند.

مثلث بندی حالت خاصی از گراف مسطح با خطوط مستقیم است.

چند ضلعی‌های محدب به سادگی با پیچیدگی زمانی (O(n مثلث بندی می‌شوند. به این شکل که یک راس را به همه رئوس دیگر وصل می‌کنیم.

چند ضلعی‌های یکنوا نیز به سادگی همانطورکه توسط A. Fournier و D.Y. Montuno توضیح داده شده‌اند، با پیچیدگی زمانی (O(n مثلث بندی می‌شوند.

مثلث بندی یک چند ضلعی ساده با پیچیدگی زمانی (O(n برای یک مدت طولانی مسئله‌ای حل نشده بود. سرانجام Bernad Chazelle در سال ۱۹۹۱ نشان داد که هر چند ضلعی ساده‌ای را می‌شود با پیچیدگی زمانی (O(n مثلث بندی کرد. با این وجود الگوریتم ارائه شده بسیار پیچیده‌است. به همین دلیل Chazelle و دیگران هنوز به دنبال پیدا کردن الگوریتم ساده‌تری هستند.

پیچیدگی زمانی مثلث بندی یک چند ضلعی حفره دار دارای حد پایین (Ω(nlogn است.

الگوریتم‌ها

تا کنون الگوریتم‌های بسیاری برای مثلث بندی چند ضلعی‌ها ارائه شده‌است.

روش کم کردن گوش‌ها

گوش چندضلعی

با فرض اینکه هر چند ضلعی سادهٔ بی حفره‌ای حداقل دو گوش دارد می‌توان آن را مثلث بندی کرد. گوش یک چند ضلعی به مثلثی می‌گویند که دو ضلع آن روی دو ضلع چند ضلعی باشد و ضلع دیگر آن به‌طور کامل درون چند ضلعی قرار بگیرد. الگوریتم به این صورت است که در هر مرحله یک گوش چند ضلعی را پیدا کرده و آن را حذف می‌کند. در پایان هر مرحله شکل حاصل همچنان شرایط اولیه را دارد. این کار تا جایی ادامه پیدا می‌کند که فقط یک مثلث باقی بماند. پیاده‌سازی این الگوریتم آسان است، ولی کارایی این الگوریتم محدود است و فقط بروی چند ضلعی‌های بدون حفره کار می‌کند. پیچیدگی زمانی این الگوریتم O(n۲) است. به این الگوریتم ear clipping یا ear trimming نیز می‌گویند.

جستارهای وابسته

• دنباله کاتالان
• Point set triangulation

منابع

• Amato, ‎Nancy M. (2001), Goodrich, Michael T. ; Ramos, Edgar A., "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry (به انگلیسی), vol. 26, p. 245–265, archived from the original on 23 July 2018, retrieved 17 May 2009 {{citation}}: External link in |شاپا= (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)