مسیریابی در شبکه Voronoiبا استفاده از الگوریتم Dijkstra

شبکهVoronoi و مثلثبندی همتای آن یعنی مثلثبندی Delaunay یکی از پرکاربردترین شبکههای هندسی در حوزههای گوناگون علم بویژه مهندسی پزشکی و مدلسازی تومور میباشد. مسیر یابی مسئلهای مهم با کاربردهای مختلف در شبکهها است. در این مقاله ابتدا گراف همتای مثلثبندیDelaunay معرفی میشود. سپس دو الگوریتم جدید برای مسیر یابی در شبکهVoronoi ارائه میگردد. الگوریتم اول به حل مسئلهی "کوتاهترین مسیر از مبدأ واحد" در شبکه میپردازد. الگوریتم دوم نیز پس از تشکیل گراف همتا با استفاده از الگوریتم اول، نزدیکترین مکان خالی قابل دسترس به هر سلول شبکه را پیدا میکند.

Keywords:

مسیریابی , Delaunay مثلثبندی , Voronoi شبکه , Dijkstra الگوریتم