کیوان برنا - استادیار دانشکده علوم ریاضی و کامپیوتر، دانشگاه خوارزمی، تهران، ایران
عصمت رشوند نجفی - دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین، ایران

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

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