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

در هندسه محاسباتی، به تقسیم بندی چند ضلعی ها به چندین مثلث، مثلث بندی چند ضلعی ها می گویند.
مثلث بندی به گونه ای است که، هیچ دو مثلثی روی هم نمی افتند و هر نقطه از چند ضلعی فقط و فقط در یک مثلث قرار می گیرد. به عبارت دیگر، اجتماع مثلث ها، چند ضلعی اولیه را تشکیل می دهد.
طبق یک تعریف سخت گیرانه برای مثلث بندی، تمام راس های مثلث ها باید منطبق بر راس های چند ضلعی باشد، در غیر این صورت راس های مثلث ها هر کجا بروی محیط یا داخل چند ضلعی می توانند باشند.
مثلث بندی حالت خاصی از گراف مسطح با خطوط مستقیم است.
چند ضلعی های محدب به سادگی با پیچیدگی زمانی ( O ( n مثلث بندی می شوند. به این شکل که یک راس را به همه رئوس دیگر وصل می کنیم.
چند ضلعی های یکنوا نیز به سادگی همانطورکه توسط A. Fournier و D. Y. Montuno توضیح داده شده اند، با پیچیدگی زمانی ( O ( n مثلث بندی می شوند.
مثلث بندی یک چند ضلعی ساده با پیچیدگی زمانی ( O ( n برای یک مدت طولانی مسئله ای حل نشده بود. سرانجام Bernad Chazelle در سال ۱۹۹۱ نشان داد که هر چند ضلعی ساده ای را می شود با پیچیدگی زمانی ( O ( n مثلث بندی کرد. با این وجود الگوریتم ارائه شده بسیار پیچیده است. به همین دلیل Chazelle و دیگران هنوز به دنبال پیدا کردن الگوریتم ساده تری هستند.
پیچیدگی زمانی مثلث بندی یک چند ضلعی حفره دار دارای حد پایین ( Ω ( nlogn است.
تا کنون الگوریتم های بسیاری برای مثلث بندی چند ضلعی ها ارائه شده است.
با فرض اینکه هر چند ضلعی سادهٔ بی حفره ای حداقل دو گوش دارد می توان آن را مثلث بندی کرد. گوش یک چند ضلعی به مثلثی می گویند که دو ضلع آن روی دو ضلع چند ضلعی باشد و ضلع دیگر آن به طور کامل درون چند ضلعی قرار بگیرد. الگوریتم به این صورت است که در هر مرحله یک گوش چند ضلعی را پیدا کرده و آن را حذف می کند. در پایان هر مرحله شکل حاصل همچنان شرایط اولیه را دارد. این کار تا جایی ادامه پیدا می کند که فقط یک مثلث باقی بماند. پیاده سازی این الگوریتم آسان است، ولی کارایی این الگوریتم محدود است و فقط بروی چند ضلعی های بدون حفره کار می کند. پیچیدگی زمانی این الگوریتم O ( n۲ ) است. به این الگوریتم ear clipping یا ear trimming نیز می گویند.