مروری بر الگوریتم های مثلث بندی و پارامترهای موثر بر آن

فراگیرترین روش برای بیان سطح مثلث بندی نقاط نمونه برداری شده به منظور ایجاد شبکه نامنظم مثلثی است. مسئله اصلی ایجاد یک شبکه مثلث بندی است که وابسته به نقطه شروع با توجیه نقاط نباشد و همچنین در کمترین زمان بتواند مثلثها را ایجاد کند. برای تهیه مثلث بندی نقاط نمونه برداری شده باید به نحوی به هم متصل شوند که بتواند سطح مورد نظر را به بهترین وجه مدل کند و نتایج باید با آسانی قابل تکرار و قابل پیش بینی باشد. در این مقاله الگوریتمهای مثلث بندیو بخصوص الگوریتمهای مثلث بندی دلونی در فضای اقلیدسی مورد بررسی قرار می گیرد. مثلث بندی دلونی جزء مباحث مهم در هندسه محاسباتی است و همواره از نقطه نظر سرعت ، قابلیت گستنرش به هر بعد و آسانی پیاده سازی آن مورد بحث قرار می گیرد. تا کنون الگوریتم های مختلفی جهت بهبود زمانی ایجاد مثلث بنذی و همچنین مثلث بندی دلونی مطرح شده است. این الگوریتم ها دارای پیچیدگی زمانی متفاوتی هستند در این تحقیق از میان الگوریتم های موجود به تعدادی از آنها اشاره شده و راندمان برخی از الگوریتم ها به کمک یک مجموعه نقاط بررسی شه است.

کلیدواژه ها:

الگوریتم ، دلونی ، دیارام Voronoi ، شبکه نامنظم مثلثی ، مثلث بندی