دو الگوریتم ابتکاری بهینه جدید برای تولید چند ضلعی های تصادفی

یکی از مسائل مهم در گرافیک کامپیوتری و هندسه محاسباتی تولید چندضعلی های تصادفی است. چون برای ارزیابی الگوریتم های گرافیکی و هندسی غالباً ممکن نیست تا مجموعه واقعی داشت، یک مجموعه دده تصادفی می تواند جایگزین مناسبی باشد. در این مقاله مسئله تولید چند ضلعی های تصادفی ساده بر روی یک مجموعه از رئوس در نظر گرفته می شود که از پوسته های محدب فرضی و افزار فضایی برای تولید آن ها استفاده می شود. در واقع ما دو الگوریتم ابتکاری جدید برای تولید چند ضلعی های ساده تصادفی و حفره دار با پیچیدگی زمانی O(nlogn) ارائه می کنیم.

کلیدواژه ها:

چندضلعی ساده تصادفی ، چندضلعی حفره دار ، پوسته محدب ، پیمایش زاویه ای