مشاهده مشخصات مقاله
Touring a Sequence of Polygons in Weighted Regions
|
نویسنده (ها) |
-
Amir Hedayaty
-
Salman Parsa
|
|
مربوط به کنفرانس |
دوازدهمین کنفرانس بینالمللی سالانه انجمن کامپیوتر ایران |
|
چکیده |
Given a subdivision of plane into convex polygon regions, a sequence of polygons to meet,
a start point s, and a target point t, we are interested in determining the shortest weighted
path on this plane which starts at s, visits each of the polygons in the given order, and ends
at t. The length of a path in weighted regions is de¯ned as the sum of the lengths of the
sub-paths within each region. We will present an approximation algorithm with maximum
± cost additive. Our algorithm is based on the shortest weighted path algorithm proposed
by Mata and Mitchel [2]. The algorithm runs in O(((n3LW +RW) k
± )3) time, where n is the
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 [3]. We will give an approximation algorithm to solve the general case of
the problem (with non-convex intersecting polygons). |
|
قیمت |
-
برای اعضای سایت : ۱٠٠,٠٠٠ ریال
-
برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
-
برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال
|
خرید مقاله
|
|
.gif){kind=icon}