شروین دانش پژوه - دانشجوی کارشناسی ارشد کامپیوتر - نرم افزار، دانشگاه صنعتی شریف، دانشک
محمد قدسی - استاد دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف

مساله برچسب گذاری نقشه ها یکی از مساله های قدیمی نقشه کشی است. نقشه ای حاوی مجموعه ای از نقاط داریم و هر نقطه در این مجموعه نقاط دارای تعدادی کاندیدا(مربع) است. هدف یافتن اندازه بهینه کاندیداها است. بنحوی که کاندیدا ها با یکدیگر تداخل نداشته باشند و هر نقطه دارای حداقل یک کاندیدا باشد. نقشه می تواند یک نقشه معمولی (نقشه یک کشور)، نمودار، گراف یا هر شکل دیگری که نیاز به برچسب گذاری دارد، باشد . چند الگوریتم تقریبی برای این مساله وجود دارند. یکی از این الگوریتم ها دارای زمان اجرا و تقریب بهینه است و در عمل هم خوب کار می کند . دراین مقاله ما زا این الگوریتم بعنوان الگوریتم پایه استفاده کرده و یک الگوریتم موازی برای مساله برچسب گذاری نقشه ها ارائه می کنیم. الگوریتم موازی که ارایه می شود اولین الگوریتم موازی برای مساله برچسب گذاری نقشه هاست. این الگوریتم دارای افزایش سرعت برابر با log p2 نسبت به الگوریتم غیر موازی است.

برچسب گذاری نقشه ها ، پردازش موازی ، هندسه محاسباتی ، الگوریتم های تقریبی