fa تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم فناوری اطلاعات و ارتباطات ICT پژوهشي Research چکیده N گره را روی N دراین مقاله در نظر داریم تا یک درخت با رأس تعبیه کنیم این تعبیه باید n نقطه داخل یک چند ضلعی با به گونهای باشد که تعداد خمهای درخت حاصل حداقل شود . ایدهی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئلهی تطبیقدهی گرافها واستفاده از الگوریتمهای تطبیقدهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیهی گرافها، تطبیقدهی گراف ها ر ا با حداقل هزینه برای به حداقل رساندن تعداد خم انجام میدهیم است. O(N2n+N و الگوریتم دارای پیچیدگی محاسباتی ( 4 کلیدواژگان: تعبیه ی هندسی، تعبیه ی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف. In this paper we consider to embed a tree T with N vertices on a set of N points inside a simple polygon on n vertices and the goal is to minimize the number of bends. The main idea of our algorithm is modeling the problem into graph matching problem and uses the graph matching algorithms. We apply the concept of error-correction transformation and find the appropriate cost function then we perform the graph matching with the minimum cost for minimizing the number of bends. The time complexity of the proposed algorithm is found to be O (N2n+N4). تعبیه ی هندسی، تعبیه ی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف. 1 7 http://jor.iranaict.ir/browse.php?a_code=A-10-354-8&slc_lang=fa&sid=1 اکرم سپهری akram_sepehri@yahoo.com 1003194753284600578 1003194753284600578 Yes دانشکدهی مهندسی برق، رایانه و فنآوری اطلاعات، دانشگاه آزاد اسلامی قزوین علیرضا باقری 1003194753284600579 1003194753284600579 No دانشکدهی مهندسی کامپیوتروفنآوری اطلاعات، دانشگاه صنعتی امیرکبیر