علی نوراله - استادیار دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی تهران
مجتبی بنایی نوبندگانی - دانشجوی کارشناسی ارشد دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی تهران

در اینمقاله دو الگوریتمی جدید ارائه شده است اولین الگوریتم تولید چندضلعی های ساده متعامد تصادفی برگرفته شده از معکوس درخت کاستی تحدب است ورودی الگوریتم یک درخت تصادفی با توزیع یکنواخت می باشد که این درخت بیانگر درخت کاستی تحدب می باشد. این الگوریتم دارای پیچیدگی زمانی(فرمول درمتن اصلی مقاله) است که در آنK تعداد گره های درخت و N تعداد اضلاع چندضلعی میباشد. که ورودی مسئله یک چندضلعی ساده متعامد است و خروجی ان جندضلعی محدب متعامد است این الگوریتم از مرتبه زمانی ON می باشد.

درخت تصادفی یکنواخت؛ درخت کاستی تحدب؛ چندضلعی ساده متعامد؛ چندضلعی محدب متعامد؛ چندضلعی های تصادفی