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

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

اتوماتای سلولی ، هندسه محاسباتی ، نمودار ورنوی ، الگوریتم موازی