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

كلمات كليدي:

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