مشاهده مشخصات مقاله
تولید چندضلعی های تصادفی مبتنی بر دوگان مثلث بندی
|
نویسنده (ها) |
-
علی نوراله
-
مجتبی بنایی نوبندگانی
-
جمشید نوری فرد
-
کامران مهران فر
|
|
مربوط به کنفرانس |
بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر |
|
چکیده |
در این مقاله الگوریتمی جدید برای تولید چندضلعی‌های ساده تصادفی برگرفته شده از معکوس دوگان مثلث‌بندی، ارائه می‌دهیم. دوگان مثلث‌بندی یک ساختار درختی است که نحوه مثلث‌بندی چندضلعی ساده را نمایش می‌دهد. این الگوریتم قادر به تولید چندضلعی است که دوگان مثلث‌بندی آن برابر با درخت داده شده در ورودی است. به بیانی دیگر از روی یک درخت شبه دودویی تصادفی با توزیع یکنواخت، یک چندضلعی ساده تولید می‌شود. این چندضلعی نماینده تمامی چندضلعی‌هایی است که دوگان مثلث‌بندی آن‌ها با درخت ایجادشده یکسان است. این روش اولین بار است که در تولید چندضلعی‌های تصادفی ارائه می‌شود. این الگوریتم دارای پیچیدگی زمانی O(n^2 logn) است. |
|
قیمت |
-
برای اعضای سایت : ۱٠٠,٠٠٠ ریال
-
برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
-
برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال
|
خرید مقاله
|
|
.gif){kind=icon}