سال انتشار: ۱۳۸۴

محل انتشار: سیزدهیمن کنفرانس مهندسی برق ایران

تعداد صفحات: ۸

نویسنده(ها):

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

چکیده:

در این مقاله الگوریتمی برای تولید نمودار ورونوی مبتنی بر اتوماتای سلولی (CA) و در مقیاس متریک L2 ارائه گردیده است. در این الگوریتم از هر یک از نقاط امواج دایره ای شکل با سرعت یکسان منتشر شده و از تقاطع امواج بایکدیگر نمودار ورونوی تولید می شود. الگوریتم ارائه شده ساده بوده و دارای محاسبات اندکی میباشد. در ضمن به علت استفاده نمودن از مقیاس متریک L2 دارای کاربردهای فراوان میباشد. پیچیدگی زمانی این الگوریتم مستقل از تعداد نقاط بوده و نمودار ورونوی n نقطه را با استفاده از CA دو بعدی m´m در O(m) گام زمانی تولید می نماید.