کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414677 681003 2014 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing homotopic line simplification
ترجمه فارسی عنوان
محاسبه ساده خط همتوتیک
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In this paper, we study a variant of the well-known line-simplification problem. For this problem, we are given a polygonal path P=p1,p2,…,pnP=p1,p2,…,pn and a set SS of m   point obstacles in the plane, with the goal being to determine an optimal homotopic simplification of PP. This means finding a minimum subsequence Q=q1,q2,…,qkQ=q1,q2,…,qk (q1=p1q1=p1 and qk=pnqk=pn) of PP that approximates PP within a given error ε   that is also homotopic to PP. In this context, the error is defined under a distance function that can be a Hausdorff or Fréchet distance function, sometimes referred to as the error measure. In this paper, we present the first polynomial-time algorithm that computes an optimal homotopic simplification of PP in O(n6m2)+TF(n)O(n6m2)+TF(n) time, where TF(n)TF(n) is the time to compute all shortcuts pipjpipj with errors of at most ε under the error measure F  . Moreover, we define a new concept of strongly homotopic simplification where every link qlql+1qlql+1 of QQ corresponding to the shortcut pipjpipj of PP is homotopic to the sub-path pi,…,pjpi,…,pj. We present a method that in O(n(m+n)log(n+m))O(n(m+n)log(n+m)) time identifies all such shortcuts. If PP is x  -monotone, we show that this problem can be solved in O(mlog(n+m)+nlognlog(n+m)+k) time, where k is the number of such shortcuts. We can use Imai and Iri's framework [24] to obtain the simplification at the additional cost of TF(n)TF(n).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 7, August 2014, Pages 728–739
نویسندگان
, , , , ,