سال انتشار: ۱۳۸۵
محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران
تعداد صفحات: ۷
Amir Hedayaty – Department of Computer Engineering Sharif University of Technology
Salman Parsa – Department of Mathematical Scince Sharif University of Technology
Mohammad Ghodsi – Department of Computer Engineering Sharif University of Technology IPM School of Computer Science
number of vertices of the region boundaries, L is the longest boundary, W is the maximum weight in the region, R is the sum of the perimeters of the regions, and k is the number of polygons. The main idea in the algorithm is to add Steiner points on the region boundaries and polygon edges. In addition, we will also present a solution to the query version of this problem. We will extend our result in unweighted version of the Touring a Sequence of Polygons" problem . We will give an approximation algorithm to solve the general case of the problem (with non-convex intersecting polygons).