الگوریتمی برای تولید نمودار ورنوی در اتوماتای سلولی دو بعدی
عنوان مقاله: الگوریتمی برای تولید نمودار ورنوی در اتوماتای سلولی دو بعدی
شناسه ملی مقاله: ICEE13_172
منتشر شده در سیزدهمین کنفرانس مهندسی برق ایران در سال 1384
شناسه ملی مقاله: ICEE13_172
منتشر شده در سیزدهمین کنفرانس مهندسی برق ایران در سال 1384
مشخصات نویسندگان مقاله:
شهرام گلزاری - گروه برق و کامپیوتر، دانشگاه هرمزگان
محمدرضا میبدی - دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر
خلاصه مقاله:
شهرام گلزاری - گروه برق و کامپیوتر، دانشگاه هرمزگان
محمدرضا میبدی - دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر
در این مقاله الگوریتمی برای تولید نمودار ورونوی مبتنی بر اتوماتای سلولی (CA) و در مقیاس متریک L2 ارائه گردیده است. در این الگوریتم از هر یک از نقاط امواج دایره ای شکل با سرعت یکسان منتشر شده و از تقاطع امواج با یکدیگر نمودار ورونوی تولید می شود. الگوریتم ارائه شده ساده بوده و دارای محاسبات اندکی میباشد. در ضمن به علت استفاده نمودن از مقیاس متریک L2 دارای کاربردهای فراوان میباشد. پیچیدگی زمانی این الگوریتم مستقل از تعداد نقاط بوده و نمودار ورونوی n نقطه را با استفاده از CA دو بعدی m´m در O(m) گام زمانی تولید می نماید.
کلمات کلیدی: اتوماتای سلولی ، هندسه محاسباتی ، نمودار ورنوی ، الگوریتم موازی
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/42048/