انجمن کامپیوتر ایران

در این مقاله الگوریتمی جدید برای تولید چندضلعی‌های ساده تصادفی برگرفته‌ شده از معکوس دوگان مثلث‌بندی، ارائه می‌دهیم. دوگان مثلث‌بندی یک ساختار درختی است که نحوه مثلث‌بندی چندضلعی ساده را نمایش می‌دهد. این الگوریتم قادر به تولید چندضلعی است که دوگان مثلث‌بندی آن برابر با درخت داده‌ شده در ورودی است. به بیانی دیگر از روی یک درخت شبه دودویی تصادفی با توزیع یکنواخت، یک چندضلعی ساده تولید می‌شود. این چندضلعی نماینده تمامی چندضلعی‌هایی است که دوگان مثلث‌بندی آن‌ها با درخت ایجادشده یکسان است. این روش اولین بار است که در تولید چندضلعی‌های تصادفی ارائه می‌شود. این الگوریتم دارای پیچیدگی زمانی O(n^2 logn) است.