الگوریتم هایی بهینه برای تولید چندضلعی های تصادفی مارپیچی و چندبخشی

  • سال انتشار: 1390
  • محل انتشار: هفتمین کنفرانس ماشین بینایی و پردازش تصویر ایران
  • کد COI اختصاصی: ICMVIP07_027
  • زبان مقاله: فارسی
  • تعداد مشاهده: 1843
دانلود فایل این مقاله

نویسندگان

لعیا محمدی

دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین

علی نوراله

دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین و دانشکده م

سمیرا حسینی

دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین

چکیده

یکی از مسائل مهم در گرافیک کامپیوتری و هندسه محاسباتی تولید چندضلعی های تصادفی است. از آنجا که برای ارزیابی الگوریتم های گرافیکی و هندسی غالبا ممکن نیست تا مجموعه داده ای واقعی داشت، یک مجموعه داده تصادفی می تواند جایگزین مناسبی باشد. در این مقاله مسأله تولید چندضلعی های تصادفی ساده بر روی یک مجموعه از رئوس در نظر گرفته می شود که از پوسته های محدب فرضی و افراز فضایی برای تولید آنها استفاده می شود. از این چندضلعی ها می توان برای ارزیابی بسیاری از مسائل گرافیک کامپیوتری و هندسه محاسباتی مانند روشن سازی و موزه هنری استفاده کرد. از آنجا که تاکنون هیچ راه حلی با زمان چندجمله ای برای تولید تصادفی یکنواخت چندضلعی ها شناخته نشده است، می توان ثابت کرد تولید چندضلعی در زمان کمتر از O(nlogn) امکان پذیرنیست، لذا الگوریتم های ارائه شده بهینه می باشند. در این مقاله دو الگوریتم ابتکاری جدید برای تولید چندضلعی های مارپیچی و چندبخشی با پیچیدگی زمانی O(nlogn) ارائه شده است که بهینه هستند.

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.