مشاهده مشخصات مقاله
تولید چندضلعی های تصادفی مبتنی بر دوگان مثلث بندی
|
Authors |
-
علی نوراله
-
مجتبی بنایی نوبندگانی
-
جمشید نوری فرد
-
کامران مهران فر
|
|
Conference |
بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر |
|
Abstract |
در این مقاله الگوریتمی جدید برای تولید چندضلعی‌های ساده تصادفی برگرفته شده از معکوس دوگان مثلث‌بندی، ارائه می‌دهیم. دوگان مثلث‌بندی یک ساختار درختی است که نحوه مثلث‌بندی چندضلعی ساده را نمایش می‌دهد. این الگوریتم قادر به تولید چندضلعی است که دوگان مثلث‌بندی آن برابر با درخت داده شده در ورودی است. به بیانی دیگر از روی یک درخت شبه دودویی تصادفی با توزیع یکنواخت، یک چندضلعی ساده تولید می‌شود. این چندضلعی نماینده تمامی چندضلعی‌هایی است که دوگان مثلث‌بندی آن‌ها با درخت ایجادشده یکسان است. این روش اولین بار است که در تولید چندضلعی‌های تصادفی ارائه می‌شود. این الگوریتم دارای پیچیدگی زمانی O(n^2 logn) است. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}