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

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

کلیدواژه ها:

چندضلعی متعامد ، گرید ، چندضلعی ساده تصادفی ، لایه های محدب ، هندسه محاسباتی