کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414677 | 681003 | 2014 | 12 صفحه PDF | دانلود رایگان |
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).
Journal: Computational Geometry - Volume 47, Issue 7, August 2014, Pages 728–739